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++?

Footstalk

Is this a homework assignment? – Jonquil

No. Does it matter at all? This an interesting question that should have an interesting solution. And the interest does not change whether it was asked during interview or it was given for a homework or I have just thought about that while drinking my coffe, does it? – Footstalk

@Footstalk The reason why it matters in this case is that we don’t do peoples’ homework. We help gladly but we don’t do it for them. In fact, I will downvote answers that do that since I consider it a first-class a**hole move. Your question, however, is quite interesting. – Dillondillow

@Kondrad Again, this is not homework. But this could be homework as well, and I don't share your opinion. – Footstalk

@Narek: Asking whether or not a question is a homework question isn't about the opinion of the person posting the SO question. It's about the person who might be responding to that SO question. He or she might want to answer in a different manner or maybe not answer at all if the SO question is homework (at least that's why I would ask if a question is homework). I think that it's reasonable for someone who is putting work into an answer to be able to know (or at least inquire) how that answer might be put to use. – Haemagglutinate

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.

Socle

Thanks for the answer, but there is something I cannot understand: implementation of iterator_category() – Footstalk

@Footstalk iterator_category is a type (one of std::input_iterator_tag etc.), so iterator_category() is constructing a temporary prvalue of that type. The appropriate overload of advance_impl is then selected by normal overload resolution. This is called tag dispatch. – Socle

@Footstalk How does iterator category in C++ work? – Jonquil

So iterator_category is a typedef? typedef std::bidirectional_iterator_tag iterator_category; and when yo u write iterator_category() in this particular example it calls the default constructor of std::bidirectional_iterator_tag? – Footstalk

@Narek: in principal the ctor for std::bidirectional_iterator_tag is called, however since these are inline functions and the tag is never used (except for overload resolution at compile time) it ends up having no impact on the generated code. – Haemagglutinate

@MichaelBurr what inline function and what impacdt you talk? – Footstalk

@Narek: the advance_impl<>() functions (as well as advance<>()) would be inline functions (they pretty much have to be since they are function templates). And the impact I'm talking about is any runtime impact for constructing an iterator category tag that would only get destroyed. (I see now that my prior comment was confusing, since the tag certainly has an impact on which function is chosen - that's the entire reason for the type to exist). – Haemagglutinate

Answer 2

I would imagine it may use std::iterator_traits::iterator_category to figure out what the type of the iterator is.

Based on that, it can decide how to advance things.

Oratory