Definición de iterador de mi propio contenedor

Question

estoy confundido con algunos conceptos acerca de la definición de mi propio iterador:

De esta: http://www.cs.northwestern.edu/~riesbeck/programming/c++/stl-iterator-define.html, lo que parece sugerir el uso de la clase de iterador interno que define los operadores. Muchos otros heredan la clase base iterator para redefinir los operadores.

Estoy bastante confundido acerca de qué métodos se deben utilizar. ¿Por qué hay

typedef ptrdiff_t difference_type; 

por ejemplo, al principio de la definición de clase de contenedor?

¡Muchas gracias!

Answer 1

La especificación C++ sobre qué es exactamente un contenedor STL exige que cualquier tipo de contenedor STL tenga varios campos diferentes disponibles. Algunos, como begin() y end(), son funciones, mientras que otros, como iterator, son tipos. Estas restricciones también se aplican a los iteradores. Esto permite que las funciones de la plantilla de C++ tengan una introspección en sus tipos de argumentos para buscar más propiedades. Por ejemplo, todos los tipos de iteradores STL deben definir un campo iterator_category que contenga un tipo que codifique sus capacidades. De esta manera, los algoritmos STL pueden tener diferentes implementaciones de diferentes funciones basadas en el poder de los iteradores que aceptan. Un ejemplo de clase es la función distance, que toma dos iteradores y devuelve el número de espacios entre ellos. Si la entrada es muy baja ForwardIterator o BidirectionalIterator esto funciona al avanzar los iteradores y contando cuántos pasos se tomaron, lo cual se ejecuta en O (n). Si la entrada es RandomAccessIterator, los iteradores solo se pueden restar para obtener el resultado en O (1).

Afortunadamente, por lo general no es necesario enumerar explícitamente todos los typedefs. Hay un tipo de utilidad en el encabezado <iterator> llamado iterator que está parametrizado en una gran cantidad de argumentos diferentes. Si define un tipo de iterador personalizado, puede heredar de iterator para importar toda esta información automáticamente. Es esencialmente una forma más rápida de tener todos los typedef s en su lugar.

En cuanto a los operadores Lo que hay que sobrecargar, en un mínimo que necesita para obtener ++ (prefijo y postfijo), ==, !=, * (de referencia de puntero), y -> definido. Todos los tipos de iteradores lo soportan. Para iteradores bidireccionales o superiores, también debe tener -- definido (prefijo y postfijo). Por último, para los iteradores de acceso aleatorio, debe apoyar [], +, +=, - (copia de seguridad de muchos pasos y restar dos iteradores), -=, <, >, <= y >=.

Espero que esto ayude!

Answer 2

Aunque la respuesta de @ templattypedef es precisa, quizás pueda aclarar la situación un poco.

Un iterador normalmente se define como una clase anidada dentro del contenedor. std::iterator se usa generalmente como una clase base para facilitarle la definición de su clase de iterador. Nunca realmente tiene para usar std::iterator - está ahí para facilitar el trabajo y (especialmente) reducir la cantidad de código que necesita escribir.

Answer 3

Aunque el uso de std::iterator puede ayudar con typedef s, ciertamente no ayuda con la implementación real.

La biblioteca Boost.Iterator tiene muchas cosas buenas para esto, y sugeriré leer sobre el boost::iterator_adaptor que reduce en gran medida la cantidad de código que necesita escribir para definir un nuevo iterador encima de uno anterior.