There are different techniques for overloading on type requirements in C++. Lets take a look at comparing the different techniques. We’ll start by writing a simple implementation of std::advance, which increments an iterator by user-specified elements. However, if the iterator has random access traversal, it can be incremented in one step. Also, the iterator can advance backwards as well. So we need overloads for the three different iterator traversals. Lets use Tick to implement the traits for the these traversals:

TICK_TRAIT(is_incrementable)
{
    template<class T>
    auto require(T&& x) -> valid<
        decltype(x++),
        decltype(++x)
    >;
};

TICK_TRAIT(is_decrementable, is_incrementable<_>)
{
    template<class T>
    auto require(T&& x) -> valid<
        decltype(x--),
        decltype(--x)
    >;
};

TICK_TRAIT(is_advanceable)
{
    template<class T, class Number>
    auto require(T&& x, Number n) -> valid<
        decltype(x += n)
    >;
};

We don’t use the iterator category since it is not always related to traversal(ie an input iterator could have random access traversal). So to test our advance function we can test it against std::vector and std::list:

void check_list()
{
    std::list<int> l = { 1, 2, 3, 4, 5, 6 };
    auto iterator = l.begin();
    advance(iterator, 4);
    // Prints 5
    std::cout << *iterator << std::endl;
}

void check_reverse_list()
{
    std::list<int> l = { 1, 2, 3, 4, 5, 6 };
    auto iterator = l.end();
    advance(iterator, -4);
    // Prints 3
    std::cout << *iterator << std::endl;
}

void check_vector()
{
    std::vector<int> v = { 1, 2, 3, 4, 5, 6 };
    auto iterator = v.begin();
    advance(iterator, 4);
    // Prints 5
    std::cout << *iterator << std::endl;
}

So let’s look at the different ways to implement advance.

Function overloading

We can create separate functions for each overload, and use template constraints. However, we will need to negate the other overloads to avoid ambiguities:

template<class Iterator, TICK_REQUIRES(is_advanceable<Iterator, int>())>
void advance(Iterator& it, int n)
{
    it += n;
}

template<class Iterator, TICK_REQUIRES(is_decrementable<Iterator>() and 
                                        not is_advanceable<Iterator, int>())>
void advance(Iterator& it, int n)
{
    if (n > 0) while (n--) ++it;
    else 
    {
        n *= -1;
        while (n--) --it;
    }
}

template<class Iterator, TICK_REQUIRES(is_incrementable<Iterator>() and 
                                        not is_advanceable<Iterator, int>() and 
                                        not is_decrementable<Iterator>())>
void advance(Iterator& it, int n)
{
    while (n--) ++it;
}

Of course, negating the overloads can be a little difficult. Plus, it is not really maintainable. If a new overload needed to be added than the other overloads would possibly need to be negated as well.

Tag-dispatching

Tag dispatching works by creating tags that uses inheritance to order the functions:

struct incrementable_tag {};
struct decrementable_tag : incrementable_tag {};
struct advanceable_tag : decrementable_tag, incrementable_tag {};

template<class T, class=void>
struct get_advance_tag;

template<class Iterator>
void advance_impl(Iterator& it, int n, advanceable_tag)
{
    it += n;
}

template<class Iterator>
void advance_impl(Iterator& it, int n, decrementable_tag)
{
    if (n > 0) while (n--) ++it;
    else 
    {
        n *= -1;
        while (n--) --it;
    }
}

template<class Iterator>
void advance_impl(Iterator& it, int n, incrementable_tag)
{
    while (n--) ++it;
}

template<class Iterator>
void advance(Iterator& it, int n)
{
    advance_impl(it, n, typename get_advance_tag<Iterator>::type());
}

That is starting to look a little better. However, how do we implement get_advance_tag? We could require the user to specialize it for each iterator:

template<class T>
struct get_advance_tag<std::vector<T>::iterator>
{ using type = advanceable_tag; };

Of course that seems to be more work for the user. So instead we can deduce the tag:

template<class T>
struct get_advance_tag<T, TICK_CLASS_REQUIRES(is_advanceable<T, int>())>
{ using type = advanceable_tag; };

template<class T>
struct get_advance_tag<T, TICK_CLASS_REQUIRES(is_decrementable<T>() and 
                                            not is_advanceable<T, int>())>
{ using type = decrementable_tag; };

template<class T>
struct get_advance_tag<T, TICK_CLASS_REQUIRES(is_incrementable<T>() and 
                                        not is_advanceable<T, int>() and 
                                        not is_decrementable<T>())>
{ using type = incrementable_tag; };

Now, this is no better then the previous solution. However, this logic only needs to be written once, not for every function. Even so, this solution has other disadvantages. First, the dispatching boilerplate such as advance and advance_impl has to be written every time. Secondly, as it is currently written, it produces longer and more confusing compiler errors. Although this can be fixed, this extra work is required every time we want to do tag dispatching.

Ranking

In the post Beating overload resolution into submission, Xeo discusses how to rank each overload:

template<int N>
struct rank : rank<N-1> {};

template<>
struct rank<0> {};

template<class Iterator, TICK_REQUIRES(is_advanceable<Iterator, int>())>
void advance_impl(Iterator& it, int n, rank<3>)
{
    it += n;
}

template<class Iterator, TICK_REQUIRES(is_decrementable<Iterator>())>
void advance_impl(Iterator& it, int n, rank<2>)
{
    if (n > 0) while (n--) ++it;
    else 
    {
        n *= -1;
        while (n--) --it;
    }
}

template<class Iterator, TICK_REQUIRES(is_incrementable<Iterator>())>
void advance_impl(Iterator& it, int n, rank<1>)
{
    while (n--) ++it;
}

template<class Iterator>
void advance(Iterator& it, int n)
{
    advance_impl(it, n, rank<3>());
}

Of course, this is simpler than the previous solutions, however, it suffers from similar disadvantages: adding new overloads requires reordering the ranking, dispatching boilerplate is required every time, and it produces longer compiler errors.

Conditional Overloading

Conditional overloading allows us to order the functions, by picking the first function that is valid. We can use the conditional adaptor from Fit(or you can implement it yourself here):

const constexpr auto advance = fit::conditional(
    FIT_STATIC_LAMBDA(auto& it, int n, 
        TICK_PARAM_REQUIRES(tick::trait<is_advanceable>(it, n)))
    {
        it += n;
    },
    FIT_STATIC_LAMBDA(auto& it, int n, 
        TICK_PARAM_REQUIRES(tick::trait<is_decrementable>(it)))
    {
        if (n > 0) while (n--) ++it;
        else 
        {
            n *= -1;
            while (n--) --it;
        }
    },
    FIT_STATIC_LAMBDA(auto& it, int n, 
        TICK_PARAM_REQUIRES(tick::trait<is_incrementable>(it)))
    {
        while (n--) ++it;
    }
);

This has several advantages over the other solutions. First, additional overloads can be added easily. Secondly, it doesn’t produce long and confusing compile errors. Thirdly, it doesn’t require a lot of boilerplate every time.

The disadvantage to this over tag dispatching is the functions have to be ordered by their relationships for every function rather than being handle by the tag hierarchy once. Additionally, if generic lambdas can’t be used then function objects need to be used instead, which can be a little more boilerplate as well without some clever macros.