Última atualização：2026-10-12

Análise do código-fonte dos iteradores da STL

0. Introdução

Nesta seção, usando as características de Traits da seção anterior, estudamos o código-fonte do iterator para implementar um iterator_category simples e, ao mesmo tempo, analisamos a estrutura do código-fonte do iterator.

Conhecer o fato e conhecer o porquê do fato: diante do código-fonte, não há segredos!

1. Usando o extrator para implementar um reconhecimento simples de iterator_category

A seção anterior apontou o papel dos iteradores, conforme a figura abaixo:

Um iterador é uma abstração de um ponteiro para elementos de uma sequência. Ao usar iteradores, podemos acessar determinado elemento da sequência, alterar o valor de determinado elemento da sequência, fazer o iterador avançar ou retroceder, e assim por diante.

Os iteradores comumente têm cinco tipos associados: value_type, difference_type, reference_type e pointer_type são relativamente fáceis de extrair com traits e as especializações parciais correspondentes.

Mas iterator_category também costuma ter 5, e esse tipo associado desperta um esforço de escrita de código de grande escala.

• Input Iterator: iterador de movimento unidirecional somente leitura
• Output Iterator: iterador de movimento unidirecional somente escrita
• Forward Iterator: iterador de movimento unidirecional de leitura e escrita
• Bidirectional Iterator: iterador de movimento bidirecional de leitura e escrita

Por exemplo: implementamos advanceII, advanceBI e advanceRAI, representando, respectivamente, as implementações correspondentes quando o tipo do iterador é Input Iterator, Bidirectional Iterator e 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);
}

Mas decidir em tempo de execução qual versão usar afeta a eficiência do programa. O ideal seria escolher a versão correta já em tempo de compilação.

E o mecanismo de sobrecarga de funções pode atingir esse objetivo.

Quanto aos advanceXX(), ambos têm dois parâmetros de função, com tipos indeterminados (pois todos são parâmetros de template). Para que tenham o mesmo nome e formem funções sobrecarregadas, devemos acrescentar um parâmetro de função com tipo já determinado, para que o mecanismo de sobrecarga de funções possa operar de forma eficaz.

O desenho é o seguinte: se o traits for capaz de extrair a categoria do iterador, podemos usar esse tipo associado "tipo do iterador" como terceiro parâmetro de advancexx; e esse tipo associado deve ser um class type, não pode ser algo como um número, pois o compilador depende dele para fazer a resolução de sobrecarga.

Vamos implementar; primeiro, o diagrama geral da estrutura:

Definimos as tags abaixo:

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

Depois de declarar essa série de tags, podemos sobrecarregar a função advance; definimos essas funções com sublinhados, indicando que são de uso interno, invisíveis externamente.

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

}

Definindo o extrator:

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

Expondo a interface externa:

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

Definindo o class type:

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

Hora de testar: usamos o class type definido acima e ponteiros nativos para testar, entrando, respectivamente, no extrator comum e no extrator com especialização parcial, para ver se obtemos as Tags correspondentes.

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

Resultado da saída:

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

Tudo ocorreu como esperávamos: por meio do extrator, obtivemos a tag de cada iterador, incluindo a tag de ponteiros nativos.

Vamos complicar um pouco mais: se quisermos conhecer o tipo de retorno de advance, como fazer?

Primeiro, modifique o retorno de 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()); // 各型别的重载
}

Em seguida, modifique o retorno de __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();
}

Basta trocar void pelo extrator correspondente.

Por fim, teste a modificação, acrescentando os retornos:

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

Com isso, fica concluída a implementação de um discernimento simples de tipo de iterador em tempo de compilação.

2. Análise do Iterator no código-fonte da STL

Em bits/stl_iterator_base_types.h é como mostrado acima (na verdade, o que fizemos é uma versão simplificada do código-fonte da STL, bem próxima); vamos ver juntos.

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

Igual ao que usei acima.

（2）o extrator iterator_traits, que contém cinco tipos, dos quais implementamos apenas um acima: iterator_category. Por isso, na STL, o iterator — ponte entre contêineres e algoritmos — deve conter os cinco typedef abaixo.

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

O class type mencionado acima é a versão simplificada do seguinte; comparando, não há diferença: apenas há mais alguns parâmetros de template e mais 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;
};

Com isso, conclui-se a análise das características de iterator e traits. Sejam bem-vindos a explorar comigo os mistérios do código-fonte da STL; como diz o professor 侯捷: diante do código-fonte, não há segredos.

Tópicos relacionados

• Análise do código-fonte do STL array | C++那些事
• Análise aprofundada do STL string | C++那些事
• Questões de entrevista sobre STL string explicadas | C++那些事
• Análise do código-fonte do STL deque | C++那些事
• STL otimização de classe base vazia EBO | C++那些事
• STL implementação manual de tabela hash | C++那些事
• STL hashtable tabela hash | C++那些事
• Análise do código-fonte do STL list | C++那些事
• STL map e multimap | C++那些事
• Análise do código-fonte do STL queue e stack | C++那些事

Comentários