Implementation of a Simple iterator_category in C++ STL Source Code Analysis

Table of Contents

Implementation of a Simple iterator_category in C++ STL Source Code Analysis

0. Introduction

In this section, we will use the Traits feature introduced in the previous section to study the iterator source code, implementing a simple iterator_category, while also analyzing the structure of the iterator's source code.

Know the facts, know the reasons, and there are no secrets in front of the source code!

1. Implementing a Simple iterator_category Recognition Using Type Traits

As mentioned in the previous section, iterators play a vital role, as illustrated in the following diagram:

Iterator Diagram

Iterators are abstractions of pointers to elements in a sequence. By using iterators, we can access elements in a sequence, modify the values of elements, move the iterator forward or backward, and so on.

There are commonly five types of iterators: value_type, difference_type, reference_type, pointer_type, all of which can be easily extracted in traits and corresponding partial specializations.

However, there are generally also five iterator categories, which can lead to a large-scale code engineering effort.

Input Iterator: Read-only iterator for single-pass traversal.
Output Iterator: Write-only iterator for single-pass traversal.
Forward Iterator: Read-write iterator for single-pass traversal.
Bidirectional Iterator: Read-write iterator for bidirectional traversal.
Random Access Iterator: Read-write iterator for random access traversal.

For example, if we implement advanceII, advanceBI, advanceRAI representing implementations corresponding to the types Input Iterator, Bidirectional Iterator, and Random Access Iterator, respectively:

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

However, deciding which version to use at runtime will affect program efficiency. It is better to select the correct version at compile time.

The mechanism of overloading functions can achieve this goal.

For advanceXX() functions, both function parameters are undefined types (because they are template parameters). To make them have the same name and form overloaded functions, we must add a determined type as a function parameter. This allows the function overloading mechanism to work effectively.

The design is as follows: if the traits have the ability to extract the category of the iterator, we can use this "iterator type" as the third parameter of advancexx, and this corresponding type must be a class type, not just a numerical value, because the compiler relies on it for overload resolution.

Let's implement it. First, here's an overall structure diagram:

Iterator Structure

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 {};
// The benefit of inheritance is that when a function needs to use input_iterator_tag
// and you pass in a forward_iterator_tag, it will traverse the inheritance chain until it finds a match.

After declaring a series of tags, we can overload the advance function. We denote these functions using underscores to indicate that they are used internally and are not visible externally.

// The benefit of inheritance is that when a function needs to use input_iterator_tag
// and you pass in a forward_iterator_tag, it will traverse the inheritance chain until it finds a match.
// 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;
}

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

}

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

}

Define the trait:

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

// Specialization for native pointers
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 interface:

// External interface
template<class InputIterator, class Distance>
inline void advance(InputIterator &i, Distance n) {
    // Inquire about the iterator's iterator_category through Iterator_traits
    typedef typename Iterator_traits<InputIterator>::iterator_category category;
    __advance(i, n, category()); // Overloads for each category
}

Define the class type:

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

Start testing. We use the class type defined above and native pointers for testing, entering the ordinary extraction machine and the specialized extraction machine to see if we get the corresponding tags.

int main() {
    iterator<input_iterator_tag> input;
    iterator<output_iterator_tag> output;
    iterator<forward_iterator_tag> forward;
    iterator<bidirectional_iterator_tag> bidirectional;
    iterator<random_access_iterator_tag> random_access;
    advance(input, 10);
    advance(output, 10);
    advance(forward, 10);
    advance(bidirectional, 10);
    advance(random_access, 10);
    int *p = nullptr;
    advance(p, 10);
    return 0;
}

Output:

input tag
output tag
forward tag
bidirectional tag
random access tag
random access tag

As expected, through the extraction machine, we obtain the tags for each iterator and the tag for native pointers.

Let's make it a bit more complex. If we want to know the return type of advance, how can we do that?

First, modify the return of advance:

// External interface
template<class InputIterator, class Distance>
inline typename Iterator_traits<InputIterator>::iterator_category
advance(InputIterator &i, Distance n) {
    // Inquire about the iterator's iterator_category through Iterator_traits
    typedef typename Iterator_traits<InputIterator>::iterator_category category;
    return __advance(i, n, category()); // Overloads for each category
}

Next, modify the return of __advance:

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

// bidirectional iterator
template<class BidirectionalIterator, class Distance>
inline typename Iterator_traits<BidirectionalIterator>::iterator_category
__advance(BidirectionalIterator &i, Distance n,
          bidirectional_iterator_tag) {
    std::cout << "bidirectional tag" << std::endl;
    return bidirectional_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 << "random access tag" << std::endl;
    return random_access_iterator_tag();
}

Just change void to the respective extraction machine.

Finally, test the modification, adding the return:

int main() {
    iterator<input_iterator_tag> input;
    iterator<output_iterator_tag> output;
    iterator<forward_iterator_tag> forward;
    iterator<bidirectional_iterator_tag> bidirectional;
    iterator<random_access_iterator_tag> random_access;
    input_iterator_tag inputIteratorTag = advance(input, 10);
    output_iterator_tag outputIteratorTag = advance(output, 10);
    forward_iterator_tag forwardIteratorTag = advance(forward, 10);
    bidirectional_iterator_tag bidirectionalIteratorTag = advance(bidirectional, 10);
    random_access_iterator_tag randomAccessIteratorTag = advance(random_access, 10);
    int *p = nullptr;
    random_access_iterator_tag v = advance(p, 10);
    return 0;
}

With this, a simple iterator type determination at compile time is complete.

2. STL Source Code Analysis of Iterator

In bits/stl_iterator_base_types.h, it is essentially as shown above (in fact, the above is a simplified version of the STL source code, very close to it), let's take a 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 { };

Similar to what we used above.

(2) iterator_traits extraction machine, which contains five types in STL, while above we implemented only one: iterator_category. Therefore, in the STL, the bridge between containers and algorithms, the iterator, must include 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, compared to it, there is not much difference, just that the template parameters are more, and there are 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 this, the analysis of iterators and trait features is complete. Welcome to explore the mysteries of the STL source code together, as Mr. Hou Jie said: There are no secrets in front of the source code.