Can overloads for generic functions be open for other overloads?

Question

I want to implement some generic algorithms and I have a number of ideas how specialized algorithms could be implemented depending on certain traits of entities the algorithm is used with. However, it seems likely that I didn't come up with all special traits and I'd like to implement the generic version such that they could work with another specialized version.

For example, consider distance(begin, end) (yes, I know it is in the standad library; however, it is nice and simple and can be used to demonstrate my problem). A general version could look like this (I'm using std::ptrdiff_t instead of std::iterator_traits<It>::difference_type as another simplification):

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

Of course, if the iterator type is a random access iterator, it is much better to implement the algorithm using the difference between the two iterators. Naively just adding

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; } 

doesn't quite work: both implementation are equally good matches for random access iterators, i.e., the compiler considers them to be ambiguous. The easy approach to deal with the situation is to change the general implementation to be applicable only for non random access iterators. That is, the SFINAE choices are made such that they are mutually exclusive while also covering the entire space.

Unfortunately, the set of implementations is still closed: without changing the signature of, at least, one of the implementations I can't add another implementation in case I have another idea for a generic implementation taking advantage of special properties. For example, if I want to add special processing for segmented ranges (idea: when the underlying sequence consists of segments as is, e.g., the case for std::deque<...> or std::istreambuf_iterator<cT>, process segments individually) it would be necessary to change the general implementation to be applicable only when the sequences isn't a random access and it isn't a segmented sequence. Of course, if I control the implementation that can be done. A user wouldn't be able to extend the set of generic implementations.

I am aware that the functions can be overloaded for special iterator types. However, that would require that every time an iterator with special capabilities is added it would need to implement the respective functions. The goal is to enable adding generic implementations which areimprovements in case the entities they are used with expose additional facilities. It is similar to the different iterator categories, although the properties are orthogonal to the iterator categories.

Thus, my question is:

• Can generic algorithms be implemented such that new improvement idea can be added without changing the existing implementations and, if so, how?
• Optional follow-up (I'm primarily interested in the question above but this one could be interesting, too): If that isn't possible, would this ability be added with concepts?

Answer 1

One approach is a ranking-based overload mechanism. Assign each overload a rank and let overload resolution do the rest.
These are the helper traits:

template <unsigned i> struct rank : rank<i - 1> {};  template <> struct rank<0> {};  using call_ranked = rank<256>; 

And this is an example usage:

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)...); } 

Demo.
A rank with a higher number is more prioritized than one with a lower number. I.e. rank<1> causes the second overload to be selected over the first (rank<0>) if the matches would otherwise be identical.

If you wanted to add a segment-based implementation, use that as the condition for enable_if. Presumably segmented ranges and random-access ranges would be mutually exclusive, but if they aren't, assign the random-access one a higher priority. The general guideline could be: The more efficient an implementation is, the higher its rank.
Using this method, other implementations shouldn't be affected when introducing a new one. One has to make sure though that any two categories with non-empty intersections (that aren't covered by a category with higher rank) have a different rank - which constitutes a noticeable disadvantage.