¿Cómo funciona la categoría de iterador en C++?

Question

traté de entender la aplicación iterador, y al mismo tiempo jugando con la fuente, vi esta declaración:

typedef output_iterator_tag iterator_category; 

No entiendo cómo este trabajo typedef dentro de la clase? ¿Cuál es el efecto secundario que proporciona? ¿Alguien puede guiarme a través de esto?

Answer 1

Necesita leer sobre programación genérica porque no es probable que obtenga esta respuesta.

"Iterador de salida" es un concepto que coinciden con ciertos iteradores. Cada iterador que es una realización de este concepto tiene cierta funcionalidad asociada. Es algo así como herencia, pero no lo es.

C++ no tiene nada que represente conceptos (fue una adición propuesta a C++ 0x pero no lo logró). Siendo ese el caso, necesitamos varias construcciones de plantilla para permitirnos asociar una "etiqueta" con un tipo de iterador. Al asociar el tipo output_iterator_tag con un iterador, afirmamos que nuestro tipo de iterador realiza el concepto OutputIterator.

Esto se vuelve muy importante cuando intenta escribir algoritmos que están lo más optimizados posible y también genéricos. Por ejemplo, realizar una ordenación con un iterador que se puede incrementar o disminuir mediante un valor arbitrario (que no sea 1 en otras palabras) es más eficiente que uno que no tiene esta capacidad. Además, para obtener un nuevo iterador con una distancia X de otro puede requerir diferentes operaciones dependiendo de las capacidades del iterador. Para escribir un algoritmo de este tipo, utiliza el "despacho de etiquetas". Para explicar esto más completamente, aquí hay una implementación (no probada) de std :: advance que funciona tanto con iteradores que tienen un operador + = como aquellos que solo tienen un operador ++ y que es lo más rápido posible con ambas versiones.

template < typename RandomAccessIterator > 
RandomAccessIterator advance(RandomAccessIterator it 
          , int amount 
          , random_access_iterator_tag) 
{ return it + amount; } 

template < typename ForwardIterator > 
ForwardIterator advance(ForwardIterator it, int amount, forward_iterator_tag) 
{ 
    for (;amount; --amount) ++it; 
    return it; 
} 

template < typename Iterator > 
Iterator advance(Iterator it, int amount) 
{ 
    typedef typename std::iterator_traits<Iterator>::iterator_tag tag; 
    advance(it, amount, tag()); 
} 

Esa es la memoria de lo que es probablemente plagado de errores (probablemente tienen un montón de tipos de mal incluso) ... pero esa es la idea. Las etiquetas de los iteradores son tipos que están vacíos y también se heredan el uno del otro exactamente de la misma manera que los conceptos se refinan entre sí. Por ejemplo, un iterador de acceso aleatorio ES un iterador directo. Así random_access_iterator_tag es una derivada de forward_iterator_tag. Debido a las reglas de resolución de sobrecarga de función que pasan un random_access_iterator_tag a la función se resuelve en esa versión de la función en lugar de en la etiqueta forward_iterator_tag.

De nuevo, lea sobre la programación genérica. Es esencial utilizar toda la potencia de C++.

Ah, y finalmente ... El typedef está ahí en la definición de la clase del iterador porque es un lugar agradable y conveniente para ponerlo. Un iterator_traits por defecto puede buscarlo allí. Sin embargo, querrá usar iterator_traits en lugar de esa definición porque los punteros sin procesar también son iteradores y no pueden tener typedefs internos.

Answer 2

output_iterator_tag es una clase vacía. Su propósito es permitir que los algoritmos identifiquen clasificaciones genéricas de iteradores que siguen ciertas reglas y proporcionan operadores particulares. Esto permite que los algoritmos proporcionen una implementación más especializada de un algoritmo dado bajo ciertas condiciones. ":: distancia std"

Por ejemplo en la cabecera de VS2010, 'algoritmo s tiene dos implementaciones dependiendo de la 'iterator_category' typedef'd en los iteradores aprobadas en.

std :: distancia solamente requiere un iterador de entrada para calcular la distancia entre dos iteradores, pero podría tomar el tiempo lineal 'O (n)' para calcular la respuesta.

Sin embargo, el compilador se da cuenta de que se está utilizando un iterador de acceso aleatorio y puede aprovechar el operador de resta para calcular la distancia en tiempo constante 'O (1)'.

Recomendaría mirar el video de Stephan T. Lavavej donde se adentra un poco en los rasgos de tipo y sus usos en la Biblioteca de plantillas estándar.