通用函数的重载是否可以为其他重载打开？

Question

我想实现一些通用算法,我有很多想法,如何根据算法使用的实体的某些特征来实现专门的算法.但是,似乎我没有提出所有特殊特性,我想实现通用版本,以便它们可以与另一个专用版本一起使用.

例如,考虑distance(begin, end)(是的,我知道它在标准库中;但是,它很好很简单,可以用来演示我的问题).一般版本可能看起来像这样(我正在使用std::ptrdiff_t而不是std::iterator_traits<It>::difference_type另一种简化):

template <typename It>
auto distance(It it, It end) -> std::ptrdiff_t {
    std::ptrdiff_t size{};
    while (it != end) {
        ++it;
        ++size;
    }
    return size;
}

当然,如果迭代器类型是随机访问迭代器,那么使用两个迭代器之间的差异来实现算法要好得多.天真地加入

template <typename It>
auto distance(It begin, It end)
     -> typename std::enable_if<is_random_access_v<It>, std::ptrdiff_t>::type {
    return end - begin;
}

并不是很有效:两个实现对于随机访问迭代器都是同样好的匹配,即编译器认为它们是不明确的.处理这种情况的简单方法是将一般实现更改为仅适用于非随机访问迭代器.也就是说,SFINAE的选择使得它们相互排斥,同时也覆盖整个空间.

不幸的是,这组实现仍然是关闭的:至少在没有改变签名的情况下,我不能添加另一个实现,以防我对利用特殊属性的泛型实现有另一个想法.例如,如果我想为分段范围添加特殊处理(想法:当基础序列按原样由段组成时,例如,std::deque<...>或者std::istreambuf_iterator<cT>单独处理段的情况),则有必要将一般实现更改为仅适用当序列不是随机访问且它不是分段序列时.当然,如果我控制可以完成的实现.用户将无法扩展通用实现集.

我知道可以为特殊迭代器类型重载函数.但是,这将要求每次添加具有特殊功能的迭代器时,都需要实现相应的功能.目标是允许添加通用实现,这些实现是在它们被使用的实体暴露额外设施的情况下改进的.它类似于不同的迭代器类别,尽管属性与迭代器类别正交.

因此,我的问题是:

• 可以实现通用算法,以便可以在不改变现有实现的情况下添加新的改进构思,如果是这样,如何实现？
• 可选的后续行动(我主要对上面的问题感兴趣,但这也可能很有趣):如果不可能,这个能力是否会添加概念？

Answer 1

一种方法是基于排名的过载机制.为每个重载分配一个等级,并让重载解析完成其余的工作.
这些是辅助特征:

template <unsigned i> struct rank : rank<i - 1> {};

template <> struct rank<0> {};

using call_ranked = rank<256>;

这是一个示例用法:

template <typename It>
auto distance_ranked(rank<0>, It it, It end) -> std::size_t {
    std::size_t size{};
    while (it != end) {
        ++it;
        ++size;
    }
    return size;
}

template <typename It>
auto distance_ranked(rank<1>, It begin, It end)
     -> typename std::enable_if<is_random_access_v<It>, std::size_t>::type {
    return end - begin;
}

// Delegating function template:
template <typename... Args>
auto distance(Args&&... args)
    -> decltype(distance_ranked(call_ranked(), std::forward<Args>(args)...)) {
    return      distance_ranked(call_ranked(), std::forward<Args>(args)...);
}

演示.
具有较高编号的等级比具有较低编号的等级更优先.即如果匹配将相同,则在rank<1>第一个(rank<0>)上选择第二个重载.

如果要添加基于段的实现,请将其用作条件enable_if.推测分段范围和随机访问范围将是互斥的,但如果不是,则为随机访问分配更高的优先级.一般准则可能是:实施效率越高,其排名越高.
使用此方法,在引入新实现时不应影响其他实现.必须确保任何两个具有非空交叉点的类别(不具有更高级别的类别所涵盖的)具有不同的等级 - 这构成了明显的劣势.

Answer 2

在较少约束的重载上,概念更喜欢受约束的重载,因此您不需要像使用SFINAE那样从无约束实现的域中排除受约束实现的域.您的基本实现可以写成:

template <typename It>
std::size_t distance(It it, It end) {
    std::size_t size{};
    while (it != end) {
        ++it;
        ++size;
    }
    return size;
}

template <typename It>
requires is_random_access_v<It>
std::size_t distance(It begin, It end) {
    return end - begin;
}

没有必要从无约束重载的域中排除随机访问迭代器(约束重载的域).

如果所有分段迭代器都是随机的或者所有随机迭代器都是分段的,那么Concepts会更喜欢更多约束的重载并且一切都很好.您只需添加新的约束重载:

template <typename It>
requires SegmentedIterator<It>
std::size_t distance(It begin, It end) {
    // ...
}

如果您具有重叠范围的约束重载但不包含另一个的约束,则重载决策与SFINAE一样不明确.然而,打破歧义有点简单,因为只需要添加一个新的重载来指定重叠区域中的行为:

template <typename It>
requires SegmentedIterator<It> && is_random_access_v<It>
std::size_t distance(It begin, It end) {
    // ...
}

SFINAE将要求您还排除其他重载领域的重叠,但概念会更喜欢这种更受限的过载,而无需更改重载SegmentedIterator和is_random_access_v.

概念允许用户使用正交重载轻松扩展通用实现.非正交重载需要更多努力来指定"重叠"中的行为,但不需要像SFINAE那样更改原始代码.