Overloading + operator for iterators and unsigned integers

Question

I'm trying to overload the + operator for list iterators and unsigned integers (for practice). The code below seems to work fine. To explain what it's supposed to do: if iter is an iterator and k an unsigned integer, then iter+k (or operator+(iter, k)) returns an iterator obtained from incrementing iter k-times.

list<int>::iterator operator+(list<int>::iterator iter, unsigned k)
{
    while (k != 0)
    {
        ++iter;
        --k;
    }
    return iter;
}

However, when I templatise thus:

template<typename T>
typename list<T>::iterator 
operator+(typename list<T>::iterator iter, unsigned k)
{
    while (k != 0)
    {
        ++iter;
        --k;
    }
    return iter;
}

and run something simple like

int main(){
    list<int> l{1,2};
    list<int>::iterator q = l.begin();
    q+1;
}

I get a large error that I cannot decipher. I have also tried to no avail:

int main(){
    list<int> l{1,2};
    list<int>::iterator q = l.begin();
    operator+<int>(q,1);
}

Any ideas as to why this is happening and how to fix it would be much appreciated!

In general you cannot overload `+` on list iterators because the implementation is allowed to use pointers in this role. — n. m. could be an AI, Sep 01 '18 at 18:54
@n.m. This is true for `std::vector` or `std::array`, which are contiguous containers. But how could an `std::list` iterator be a raw pointer? — Evg, Sep 01 '18 at 19:05
@Evg hmm you are right. If it's a pointer then +1 will work as with a pointer, no good for a linked list. My bad. — n. m. could be an AI, Sep 01 '18 at 20:29

Evg · Accepted Answer · 2018-09-02T12:08:10.410

The problem is that the template type parameter T is in the non-deduced context and cannot be deduced. To make it deducible you can do this:

template<typename T>
T operator+(T iter, unsigned k)
{ ... }

Note that this overload can potentially do a lot of harm, because T is not restricted to be std::list<T>::iterator. SFINAE can help:

template<typename T, typename = std::enable_if_t<
    std::is_same_v<T, typename std::list<
    typename std::iterator_traits<T>::value_type>::iterator>>>
T operator+(T iter, unsigned k)
{ ... }

Addition.

The question why operator+<int>(q, 1); fails is more subtle. First, a quotation from The Standard, [temp.arg.explicit]/8 (see also an example there):

But when a function template with explicit template arguments is used, the call does not have the correct syntactic form unless there is a function template with that name visible at the point of the call. If no such name is visible, the call is not syntactically well-formed and argument-dependent lookup does not apply. If some such name is visible, argument dependent lookup applies and additional function templates may be found in other namespaces.

We have such a function template here, it is our operator+. Hence, ADL tries to find operator+<int> in the std::. However, compilation fails when some operator+ template is instantiated with <int>. Which one and how it fails, depends on the particular std library implementation.

For example, gcc 8.1 tries to instantiate

template<class _Iterator> constexpr 
std::move_iterator<_IteratorL> std::operator+(
   typename std::move_iterator<_IteratorL>::difference_type,
   const std::move_iterator<_IteratorL>&)
[with _Iterator = int]

and fails somewhere inside with

error: no type named 'reference' in 'struct std::iterator_traits<int>'
...

If we disable ADL, it will work as expected:

::operator+<int>(q, 1);

or

(operator+<int>)(q, 1);

+1 thanks for this -- the link was helpful and the fix works! I understand now that `T` was in the non-deduced context. Out of curiosity: why is it that even when I specify `T` namely via `operator(q,1);`, I am still getting an error? — Bowditch, Sep 02 '18 at 10:04

score 2 · Answer 2 · answered Sep 01 '18 at 18:54

This has to do with how C++ template type deduction works. Due to how the language is set up, the compiler can’t deduce what T should be automatically in the context of list<T>::iterator. The reason why is that, because of template specialization, it’s theoretically possible that two different instantiations of list could have the same nested iterator type (say, list<Pizwkat> and list<Swibble>), in which case the compiler wouldn’t be able to determine whether T should be Pizkwat or Swibble because both options would plausibly work.

I don’t believe there’s an easy solution to the general problem of “add an operator + that only works for list iterators,” though you could consider using the std::next and std::advance functions, which work for all types of iterators. (As a note, it’s generally not considered a good idea to add custom overloads for library types, so even if you could do this, it probably wouldn’t be the best solution to whatever problem you are trying to solve.)

Overloading + operator for iterators and unsigned integers

2 Answers2