Wie wird std :: advance implementiert, um das Verhalten des Iteratortyps zu ändern?

Question

Was wir über std::advance wissen, ist die folgende:

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

Zweck

Fortschritte der Iterator i durch n Elemente.

Wenn i ist ein Random Access Iterator, verwendet die Funktion einmal operator+ oder operator-, sonst wird die Funktion wiederholt die Erhöhung verwendet oder verringern Operator (operator++ oder operator--) bis n Elemente vorgeschoben wurden.

---

Meine Frage ist folgende: Wie wird std::advance so implementiert, dass er erkennt, wenn it ein Random Access Iterator ist oder nicht? Woher weiß es, dass es operator+ anstelle von operator++ verwenden kann?

Answer 1

Durch iterator_traits und 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()); 
} 

anzumerken, dass iterator_category ist ein Typ (ein std::input_iterator_tag etc.), so ist iterator_category() kein Funktionsaufruf; Es ist ein Ausdruck, der einen temporären Prvalue dieses Typs erstellt. Die entsprechende Überlast von advance_impl wird dann durch normale Überlastauflösung ausgewählt. Dies wird Tag Versand genannt. In äquivalenter Weise könnte man schreiben:

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); 
} 

Die Überlastungen von advance_impl als drittes Argument erhalten eine unbenannte Argument, das eine Instanz ihrer gewählten Tag-Typ ist.

Answer 2

Ich könnte mir vorstellen, std::iterator_traits::iterator_category verwenden, um herauszufinden, was der Typ des Iterators ist.

Darauf basierend kann es entscheiden, wie man Dinge voranbringt.