Перейти к содержанию

Последнее обновление：2026-10-12

Анализ исходников STL итераторов

0. Введение

В этом разделе, используя описанную в прошлом разделе технику traits, мы исследуем исходники iterator, реализуем простое определение iterator_category и заодно проанализируем структуру исходников итератора.

Знать как — и знать почему; перед исходным кодом нет секретов!

1. Реализуем простое распознавание iterator_category с помощью «экстрактора»

В предыдущем разделе была показана роль итераторов, повторим её на схеме ниже:

rela

Итератор — это абстракция указателя на элемент последовательности. Используя итераторы, мы можем получить доступ к некоторому элементу последовательности, изменить значение некоторого элемента последовательности, перемещать итератор вперёд или назад и так далее.

У итераторов обычно выделяют пять связанных типов: value_type, difference_type, reference_type, pointer_type легко извлекаются в traits и соответствующих частичных специализациях.

Но iterator_category обычно тоже бывает 5 видов, и этот связанный тип порождает довольно большой объём кода.

  • однонаправленный итератор только для чтения Input Iterator
  • однонаправленный итератор только для записи Output Iterator
  • однонаправленный итератор для чтения и записи Forward Iterator
  • двунаправленный итератор для чтения и записи Bidirectional Iterator

iterator

Например: допустим, мы реализовали advanceII, advanceBI, advanceRAI — реализации соответственно для типов итераторов Input Iterator, Bidirectional Iterator и 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);
}

Но если решать, какую версию использовать, лишь во время выполнения, это скажется на эффективности программы. Лучше выбирать правильную версию на этапе компиляции.

И механизм перегрузки функций позволяет достичь этой цели.

У всех advanceXX() два параметра функции, и типы обоих не определены (поскольку это параметры шаблона). Чтобы они получили одинаковые имена и образовали перегруженные функции, мы должны добавить третий параметр с уже определённым типом, чтобы механизм перегрузки заработал.

Спроектируем так: если traits способен извлечь категорию итератора, мы сможем использовать этот связанный тип «категории итератора» в качестве третьего параметра advancexx. Причём этот связанный тип должен быть class type, а не просто чем-то вроде числового кода, поскольку компилятор опирается на него при выборе перегрузки.

Приступим к реализации; сначала общая структурная схема:

itera

Определим следующие tag:

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，它会沿继承向上找，知道符合条件

Объявив эти tag, мы можем перегрузить функцию advance; определим эти функции с ведущими подчёркиваниями, показывая, что они для внутреннего использования и снаружи не видны.

// 继承的好处就是，当函数需要用 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;

}

Определяем экстрактор:

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

Открытый наружу интерфейс:

// 对外接口
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()); // 各型别的重载
}

Определяем class type:

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

Начнём тестирование: используем определённый выше class type и обычный указатель, которые пройдут соответственно через обычный экстрактор и частично специализированный экстрактор, и посмотрим, получим ли мы соответствующие Tag.

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

Вывод:

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

Всё ровно как мы и ожидали: с помощью экстрактора мы получили tag каждого итератора, а также tag обычного указателя.

Усложним задачу: что если мы захотим узнать возвращаемый тип advance?

Сначала изменим возвращаемое значение advance:

// 对外接口
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()); // 各型别的重载
}

Сразу же изменим возвращаемое значение __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();
}

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

Достаточно заменить void на соответствующий экстрактор.

Наконец, изменим тест, добавив возвращаемое значение:

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

На этом простая реализация распознавания типа итератора на этапе компиляции завершена.

2. Анализ Iterator в исходниках STL

В bits/stl_iterator_base_types.h всё устроено так же, как описано выше (на самом деле выше — упрощённая версия исходников STL, очень близкая к ним); давайте посмотрим вместе.

（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 { };

То же, что я использовал выше.

（2）Экстрактор iterator_traits содержит пять типов, а выше мы реализовали лишь один из них: iterator_category. Поэтому iterator — мост между контейнерами и алгоритмами в STL — обязан содержать следующие пять typedef.

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

Упомянутый выше class type — упрощённая версия приведённого ниже; сравните: отличий нет, разве что параметров шаблона и typedef стало больше.

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

На этом анализ iterator и техники traits завершён. Приглашаю вместе со мной исследовать тайны исходников STL; как говорит учитель 侯捷: перед исходным кодом нет секретов.

Похожие темы

Комментарии