How is std::advance implemented to change behavior on iterator type?

Question

What we know about std::advance is the following:

template <class InputIterator, class Distance>
void advance (InputIterator& i, Distance n);

Purpose

Advances the iterator i by n elements.

If i is a Random Access Iterator, the function uses once operator+ or operator-, otherwise, the function uses repeatedly the increase or decrease operator (operator++ or operator--) until n elements have been advanced.

---

My question is the following: How is std::advance implemented such that it recognizes if it is a Random Access Iterator or not? How does it know it can use operator+ instead of operator++?

Answer 1

Through iterator_traits and tag dispatch:

template<class InputIterator, class Distance>
void advance_impl(InputIterator& i, Distance n, std::random_access_iterator_tag) {
  i += n;
}

template<class InputIterator, class Distance>
void advance_impl(InputIterator& i, Distance n, std::bidirectional_iterator_tag) {
  if (n < 0) {
    while (n++) --i;
  } else {
    while (n--) ++i;
  }
}

template<class InputIterator, class Distance>
void advance_impl(InputIterator& i, Distance n, std::input_iterator_tag) {
  assert(n >= 0);
  while (n--) ++i;
}

template<class InputIterator, class Distance>
void advance (InputIterator& i, Distance n) {
  advance_impl(i, n,
    typename std::iterator_traits<InputIterator>::iterator_category());
}

Note that iterator_category is a type (one of std::input_iterator_tag etc.), so iterator_category() is not a function call; it's an expression that constructs a temporary prvalue of that type. The appropriate overload of advance_impl is then selected by normal overload resolution. This is called tag dispatch. Equivalently one could write:

template<class InputIterator, class Distance>
void advance (InputIterator& i, Distance n) {
  typename std::iterator_traits<InputIterator>::iterator_category the_tag;
  advance_impl(i, n, the_tag);
}

The overloads of advance_impl are receiving as their third argument an unnamed argument that is an instance of their chosen tag type.