How std::advance iterator type is deduced?

  • A+
Category:Languages

Please take a look at the std::advance function. According to cppreference the complexity is:

Linear. However, if InputIt additionally meets the requirements of RandomAccessIterator, complexity is constant.

So if I pass an iterator and an integer, how does the program deduce what iterator it is and how it is implemented? So are there 2 overloads for the function or what?

 


how program deduce what iterator it and how it is implemented?

It uses std::iterator_traits<T>::iterator_category to determine iterator category and then does tag dispatching.

std::iterator_traits is specialised for raw pointers. Raw pointers are random-access iterators.

E.g.:

template<class I> void doadvance(I& i, size_t n, std::random_access_iterator_tag) {     i += n; }  template<class I, class Tag> void doadvance(I& i, size_t n, Tag) {     while(n--)         ++i; }  template<class I> void advance(I& i, size_t n) {     using Tag = typename std::iterator_traits<I>::iterator_category;     doadvance(i, n, Tag{}); } 

In C++17 instead of tag dispatching it can use if constexpr, but that would make the standard library not backward compatible. This is why it has to keep using tag dispatching.

IMO, std::next has a better interface than std::advance because it returns the iterator, so that the invocation does not have to occupy its own line of code.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: