Last updated：2026-10-12

STL iterator source code analysis

0.Introduction

This section uses the Traits technique from the previous section to study the iterator source code, implement a simple iterator_category, and analyze the source structure of iterator.

Know what, and know why — before the source code, no secrets remain!

1.Using the traits extractor to implement simple iterator_category recognition

The previous section pointed out the role of iterators, shown again in the figure below:

An iterator is an abstraction of a pointer to an element of a sequence. Using iterators, we can access some element of the sequence, change the value of some element, move the iterator forward or backward, and so on.

Iterators commonly have five associated types: value_type, difference_type, reference_type, and pointer_type are all fairly easy to extract via traits and the corresponding partial specializations.

But there are in general also 5 iterator_categories, and this associated type can trigger a large-scale coding effort.

• Input Iterator: moves one way, read-only
• Output Iterator: moves one way, write-only
• Forward Iterator: moves one way, read-write
• Bidirectional Iterator: moves both ways, read-write

For example: suppose we implement advanceII, advanceBI, and advanceRAI as the respective implementations for the iterator types Input Iterator, Bidirectional Iterator, and Random Access Iterator.

template<class Iterator>
void advance(Iterator& i) {
    if (is_random_access_iterator(i))
        advanceRAI(i,n);
    if (is_bidirectional_iterator(i))
        advanceBI(i,n);
    else
        advanceII(i,n);
}

But deciding at execution time which version to use hurts program efficiency. It would be best to select the correct version at compile time.

And the overloading mechanism of functions can achieve this goal.

The advanceXX() functions each take two function parameters whose types are undetermined (since they are all template parameters). To give them the same name and form overloaded functions, we must add a function parameter whose type is fixed, so that the function overload mechanism can operate effectively.

The design is as follows: if traits is capable of extracting the category of an iterator, we can use this "iterator category" associated type as the third parameter of advancexx; and this associated type must be a class type, not something like a numeric code, because the compiler relies on it for overload resolution.

Now let's implement it; first, an overall structure diagram:

Define the following tags:

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};
// 继承的好处就是，当函数需要用 input_iterator_tag 的时候
// 假设你传进一个forward_iterator_tag，它会沿继承向上找，知道符合条件

After declaring this series of tags, we can overload the advance function. We define these functions with leading underscores to indicate internal use, invisible from the outside.

// 继承的好处就是，当函数需要用 input_iterator_tag 的时候
// 假设你传进一个forward_iterator_tag，它会沿继承向上找，知道符合条件
// input iterator
template<class inputIterator, class distance>
inline void __advance(inputIterator&i, distance n,
                      input_iterator_tag) {
    std::cout << "input tag" << std::endl;
}
// output iterator
template<class outputIterator, class distance>
inline void __advance(outputIterator&i, distance n,
                      output_iterator_tag) {
    std::cout << "output tag" << std::endl;
}

// forward iterator
template<class ForwardIterator, class Distance>
inline void __advance(ForwardIterator &i, Distance n,
                      forward_iterator_tag) {
    std::cout << "forward tag" << std::endl;
}

// bidrectional iterator
template<class BidiectionalIterator, class Distance>
inline void __advance(BidiectionalIterator &i, Distance n,
                      bidiectional_iterator_tag) {
    std::cout << "bidrectional tag" << std::endl;

}

// RandomAccess iterator
template<class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator &i, Distance n,
                      random_access_iterator_tag) {
    std::cout << "randomaccess tag" << std::endl;

}

Define the traits extractor:

// traits 型别
template<class I>
struct Iterator_traits {
    typedef typename I::iterator_category iterator_category;
};

// 针对原生指针设计的"偏特化版"
template<class I>
struct Iterator_traits<I *> {
    typedef random_access_iterator_tag iterator_category;
};
template<class I>
struct Iterator_traits<const I *> {
    typedef random_access_iterator_tag iterator_category;
};

Expose the external interface:

// 对外接口
template<class InputIterator, class Distance>
inline void advance(InputIterator &i, Distance n) {
    // 通过Ierator_traits询问它的iterator_category是谁
    typedef typename Iterator_traits<InputIterator>::iterator_category category;
    __advance(i, n, category()); // 各型别的重载
}

Define the class type:

// class type
template<class Category>
struct iterator {
    typedef Category iterator_category;
};

Time to test. We use the class type defined above together with native pointers to enter, respectively, the ordinary extractor and the partially-specialized extractor of the traits extractor, and see whether the corresponding Tags are obtained.

int main() {
    iterator<input_iterator_tag> input;
    iterator<output_iterator_tag> output;
    iterator<forward_iterator_tag> forward;
    iterator<bidiectional_iterator_tag> bidect;
    iterator<random_access_iterator_tag> random;
    advance(input, 10);
    advance(output, 10);
    advance(forward, 10);
    advance(bidect, 10);
    advance(random, 10);
    int *p=NULL;
    advance(p,10);
    return 0;
}

Output:

input tag
output tag
forward tag
bidrectional tag
randomaccess tag
randomaccess tag

Everything is as we expected: through the traits extractor we obtained each iterator's tag, as well as the tag of native pointers.

Let's think a bit more ambitiously: what if we want to know the return type of advance?

First, modify advance to return:

// 对外接口
template<class InputIterator, class Distance>
inline typename Iterator_traits<InputIterator>::iterator_category
advance(InputIterator &i, Distance n) {
    // 通过Ierator_traits询问它的iterator_category是谁
    typedef typename Iterator_traits<InputIterator>::iterator_category category;
    return __advance(i, n, category()); // 各型别的重载
}

Then modify __advance to return:

// input iterator
template<class inputIterator, class distance>
inline typename Iterator_traits<inputIterator>::iterator_category
__advance(inputIterator &i, distance n,
          input_iterator_tag) {
    std::cout << "input tag" << std::endl;
    return input_iterator_tag();
}

// output iterator
template<class outputIterator, class distance>
inline typename Iterator_traits<outputIterator>::iterator_category
__advance(outputIterator &i, distance n,
          output_iterator_tag) {
    std::cout << "output tag" << std::endl;
    return output_iterator_tag();
}

// forward iterator
template<class ForwardIterator, class Distance>
inline typename Iterator_traits<ForwardIterator>::iterator_category
__advance(ForwardIterator &i, Distance n,
          forward_iterator_tag) {
    std::cout << "forward tag" << std::endl;
    return forward_iterator_tag();
}

// bidrectional iterator
template<class BidiectionalIterator, class Distance>
inline typename Iterator_traits<BidiectionalIterator>::iterator_category
__advance(BidiectionalIterator &i, Distance n,
          bidiectional_iterator_tag) {
    std::cout << "bidrectional tag" << std::endl;
    return bidiectional_iterator_tag();
}

// RandomAccess iterator
template<class RandomAccessIterator, class Distance>
inline typename Iterator_traits<RandomAccessIterator>::iterator_category
__advance(RandomAccessIterator &i, Distance n,
          random_access_iterator_tag) {
    std::cout << "randomaccess tag" << std::endl;
    return random_access_iterator_tag();
}

All it takes is changing void to the corresponding traits extractor.

Finally, modify the test by adding the returns:

int main() {
    iterator<input_iterator_tag> input;
    iterator<output_iterator_tag> output;
    iterator<forward_iterator_tag> forward;
    iterator<bidiectional_iterator_tag> bidect;
    iterator<random_access_iterator_tag> random;
    input_iterator_tag inputIteratorTag = advance(input, 10);
    output_iterator_tag outputIteratorTag = advance(output, 10);
    forward_iterator_tag forwardIteratorTag = advance(forward, 10);
    bidiectional_iterator_tag bidiectionalIteratorTag = advance(bidect, 10);
    random_access_iterator_tag randomAccessIteratorTag = advance(random, 10);
    int *p = NULL;
    random_access_iterator_tag v = advance(p, 10);
    return 0;
}

With that, a simple iterator category discrimination at compile time is fully implemented.

2.STL source code analysis of Iterator

In bits/stl_iterator_base_types.h things are as shown above (in fact, the above is a simplified version of the STL source code, quite close to it). Let's look together.

(1) tag

 ///  Marking input iterators.
  struct input_iterator_tag { };

  ///  Marking output iterators.
  struct output_iterator_tag { };

  /// Forward iterators support a superset of input iterator operations.
  struct forward_iterator_tag : public input_iterator_tag { };

  /// Bidirectional iterators support a superset of forward iterator
  /// operations.
  struct bidirectional_iterator_tag : public forward_iterator_tag { };

  /// Random-access iterators support a superset of bidirectional
  /// iterator operations.
  struct random_access_iterator_tag : public bidirectional_iterator_tag { };

The same ones I used above.

(2) The iterator_traits extractor contains five associated types, while above we implemented only one of them: iterator_category. So in the STL, the iterator — the bridge between containers and algorithms — must contain the following five typedefs.

template<typename _Iterator>
struct iterator_traits
{
  typedef typename _Iterator::iterator_category iterator_category;
  typedef typename _Iterator::value_type        value_type;
  typedef typename _Iterator::difference_type   difference_type;
  typedef typename _Iterator::pointer           pointer;
  typedef typename _Iterator::reference         reference;
};

(3) iterator

The class type mentioned above is a simplified version of the following; compare them — no real difference, just a few more template parameters and more typedefs.

template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
       typename _Pointer = _Tp*, typename _Reference = _Tp&>
struct iterator
{
  /// One of the @link iterator_tags tag types@endlink.
  typedef _Category  iterator_category;
  /// The type "pointed to" by the iterator.
  typedef _Tp        value_type;
  /// Distance between iterators is represented as this type.
  typedef _Distance  difference_type;
  /// This type represents a pointer-to-value_type.
  typedef _Pointer   pointer;
  /// This type represents a reference-to-value_type.
  typedef _Reference reference;
};

With that, the analysis of iterator and the traits technique is complete. Welcome to explore the mysteries of the STL source code with me. As teacher 侯捷 says: before the source code, no secrets remain.

Related Topics

• STL array source code analysis | C++那些事
• STL string deep dive | C++那些事
• STL string interview questions in depth | C++那些事
• STL deque source code analysis | C++那些事
• STL empty base optimization EBO | C++那些事
• STL hand-written hash table implementation | C++那些事
• STL hashtable hash table | C++那些事
• STL list source code analysis | C++那些事
• STL map and multimap | C++那些事
• STL queue and stack source code analysis | C++那些事

Comments