Saltar a contenido

Última actualización：2026-10-12

Análisis del código fuente de los iteradores STL

0. Introducción

Esta sección usa las Traits de la sección anterior para estudiar el código fuente de iterator e implementar un iterator_category sencillo, y analiza al mismo tiempo la estructura del código fuente de iterator.

Saber el qué y también el porqué: ¡ante el código fuente no hay secretos!

1. Usar el extractor para implementar un reconocimiento sencillo de iterator_category

La sección anterior señalaba el papel de los iteradores, como muestra la siguiente figura:

rela

Un iterador es una abstracción de los punteros que apuntan a los elementos de una secuencia. Usando iteradores podemos acceder a un elemento de la secuencia, modificar el valor de un elemento, hacer avanzar o retroceder el iterador, etc.

Los iteradores suelen tener cinco tipos asociados: value_type, difference_type, reference_type y pointer_type son fáciles de extraer mediante traits y las especializaciones parciales correspondientes.

Pero iterator_category también suele tener 5 valores, y este tipo asociado da lugar a un trabajo de código de considerable envergadura.

  • Input Iterator: iterador de solo lectura con movimiento unidireccional
  • Output Iterator: iterador de solo escritura con movimiento unidireccional
  • Forward Iterator: iterador de lectura y escritura con movimiento unidireccional
  • Bidirectional Iterator: iterador de lectura y escritura con movimiento bidireccional

iterator

Por ejemplo: hemos implementado advanceII, advanceBI y advanceRAI, que representan las implementaciones correspondientes para iteradores de tipo Input Iterator, Bidirectional Iterator y 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);
}

Pero decidir en tiempo de ejecución qué versión usar afecta a la eficiencia del programa. Lo ideal sería poder elegir la versión correcta ya en tiempo de compilación.

Y el mecanismo de sobrecarga de funciones puede lograr ese objetivo.

Los advanceXX() tienen dos parámetros de función, ambos de tipo indeterminado (por ser parámetros de plantilla). Para que compartan nombre y formen funciones sobrecargadas, debemos añadir un parámetro de función con el tipo ya determinado, de modo que el mecanismo de sobrecarga funcione eficazmente.

El diseño es el siguiente: si traits es capaz de extraer la categoría del iterador, podemos usar ese tipo asociado «categoría de iterador» como tercer parámetro de advancexx; y ese tipo asociado debe ser un class type, no algo así como un número, porque el compilador debe apoyarse en él para la resolución de sobrecarga.

Pasemos a la implementación; primero, un diagrama de la estructura general:

itera

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

Una vez declarada esta serie de tag, podemos sobrecargar la función advance. Definimos estas funciones con un guion bajo para indicar que son de uso interno, invisibles desde fuera. 

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

}

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

Interfaz expuesta al exterior: 

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

Definimos el class type: 

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

Empiezan las pruebas: usamos el class type definido arriba y un puntero nativo, que entran respectivamente en el extractor ordinario y en el extractor con especialización parcial, a ver si obtienen los Tag correspondientes. 

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 de la salida: 

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

Todo sale como esperábamos: mediante el extractor obtenemos el tag de cada iterador, y también el de los punteros nativos.

Compliquémonos un poco más la vida: ¿y si quisiéramos conocer el tipo de retorno de advance, cómo lo haríamos?

Primero modificamos el 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()); // 各型别的重载
}

Acto seguido modificamos el 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 con cambiar void por el extractor correspondiente.

Por último, modificamos la prueba añadiendo el retorno: 

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

Con esto queda implementada, en el compilador, la discriminación de un tipo de iterador sencillo.

2. Análisis del código fuente STL de Iterator

En bits/stl_iterator_base_types.h aparece lo mismo que lo descrito arriba (en realidad, lo anterior es una versión simplificada del código fuente de STL, muy parecida); vamos a verlo 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 que el que yo he usado arriba.

（2）El extractor iterator_traits contiene cinco tipos; arriba solo hemos implementado uno de ellos: iterator_category. Por eso, en STL, el iterator, puente entre contenedores y algoritmos, debe incluir los cinco typedef siguientes. 

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

El class type mencionado antes es la versión simplificada del siguiente; compáralos: no hay diferencia, solo que tiene más parámetros de plantilla y más 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;
};

Con esto termina el análisis de iterator y de las características de traits. Bienvenido a explorar conmigo los misterios del código fuente de STL; como dice el profesor Hou Jie: ante el código fuente no hay secretos.

Temas relacionados

Comentarios