Namespaces
Variants

Iterator library

From cppreference.net
C++
Iterator library
Iterator concepts
Iterator primitives
Algorithm concepts and utilities
Indirect callable concepts
Common algorithm requirements
(C++20)
(C++20)
(C++20)
Utilities
(C++20)
Iterator adaptors
Range access
(C++11) (C++14)
(C++14) (C++14)
(C++11) (C++14)
(C++14) (C++14)
(C++17) (C++20)
(C++17)
(C++17)

Los iteradores son una generalización de pointers que permiten a un programa de C++ trabajar con diferentes estructuras de datos (por ejemplo, containers y ranges (since C++20) ) de manera uniforme. La biblioteca de iteradores proporciona definiciones para iteradores, así como traits de iteradores, adaptadores y funciones de utilidad.

Dado que los iteradores son una abstracción de los punteros, su semántica es una generalización de la mayoría de la semántica de los punteros en C++. Esto garantiza que cada function template que acepta iteradores funcione igualmente bien con punteros regulares.

Contenidos

Categorías de iteradores

Existen cinco (hasta C++17) seis (desde C++17) tipos de iteradores: LegacyInputIterator , LegacyOutputIterator , LegacyForwardIterator , LegacyBidirectionalIterator , LegacyRandomAccessIterator , y LegacyContiguousIterator (desde C++17) . (Véase también LegacyIterator para el tipo más básico de iterador.)

En lugar de estar definidas por tipos específicos, cada categoría de iterador se define por las operaciones que se pueden realizar sobre él. Esta definición significa que cualquier tipo que soporte las operaciones necesarias puede ser usado como iterador -- por ejemplo, un puntero soporta todas las operaciones requeridas por LegacyRandomAccessIterator , por lo que un puntero puede usarse en cualquier lugar donde se espere un LegacyRandomAccessIterator .

Todas las categorías de iteradores (excepto LegacyOutputIterator ) pueden organizarse en una jerarquía, donde las categorías de iteradores más potentes (por ejemplo, LegacyRandomAccessIterator ) admiten las operaciones de categorías menos potentes (por ejemplo, LegacyInputIterator ). Si un iterador cae en una de estas categorías y además cumple con los requisitos de LegacyOutputIterator , entonces se denomina iterador mutable y admite tanto entrada como salida. Los iteradores no mutables se denominan iteradores constantes .

Los iteradores se denominan constexpr iteradores si todas las operaciones proporcionadas para cumplir con los requisitos de categoría de iterador son funciones constexpr .

(since C++20)
Categoría de iterador Operaciones y requisitos de almacenamiento
escritura lectura incremento decremento acceso
aleatorio 		almacenamiento
contiguo
sin
múltiples
pasadas 		con
múltiples
pasadas
LegacyIterator Requerido
LegacyOutputIterator Requerido Requerido
LegacyInputIterator
(mutable si soporta operación de escritura) 		Requerido Requerido
LegacyForwardIterator
(también satisface LegacyInputIterator ) 		Requerido Requerido Requerido
LegacyBidirectionalIterator
(también satisface LegacyForwardIterator ) 		Requerido Requerido Requerido Requerido
LegacyRandomAccessIterator
(también satisface LegacyBidirectionalIterator ) 		Requerido Requerido Requerido Requerido Requerido
LegacyContiguousIterator [1]
(también satisface LegacyRandomAccessIterator ) 		Requerido Requerido Requerido Requerido Requerido Requerido
  1. ↑ LegacyContiguousIterator la categoría solo se especificó formalmente en C++17, pero los iteradores de std::vector , std::basic_string , std::array , y std::valarray , así como los punteros a arrays de C, a menudo se trataban como una categoría separada en código pre-C++17.

Nota: Un tipo que soporte las operaciones requeridas en una fila de la tabla anterior no necesariamente pertenece a la categoría correspondiente, consulte la página de categoría para la lista completa de requisitos.

Definiciones

Tipos y capacidad de escritura

Un iterador de entrada i admite la expresión * i , resultando en un valor de algún tipo objeto T , llamado el tipo de valor del iterador.

Un iterador de salida i tiene un conjunto no vacío de tipos que son writable (until C++20) indirectly_writable (since C++20) al iterador; para cada tipo T , la expresión * i = o es válida donde o es un valor de tipo T .

Para cada tipo de iterador X para el cual se define igualdad (hasta C++20) , existe un tipo entero (hasta C++20) similar a entero (desde C++20) con signo correspondiente llamado tipo de diferencia del iterador.

Dereferenciabilidad y validez

Así como un puntero regular a un array garantiza que existe un valor de puntero que apunta más allá del último elemento del array, de igual manera para cualquier tipo de iterador existe un valor de iterador que apunta más allá del último elemento de una secuencia correspondiente. Tal valor se denomina valor past-the-end .

Los valores de un iterador i para los cuales la expresión * i está definida se denominan dereferenciables . La biblioteca estándar nunca asume que los valores pasados-el-final son dereferenciables.

Los iteradores también pueden tener valores singulares que no están asociados con ninguna secuencia. Los resultados de la mayoría de las expresiones no están definidos para valores singulares; las únicas excepciones son

  • la asignación de un valor no singular a un iterador que contiene un valor singular,
  • destruir un iterador que contiene un valor singular, y,
  • para iteradores que cumplen con los requisitos DefaultConstructible , usar un iterador value-initialized como fuente de una operación de copia o movimiento (since C++11) .

En estos casos el valor singular se sobrescribe de la misma manera que cualquier otro valor. Los valores dereferenciables siempre son no singulares.

Un iterador inválido es un iterador que puede ser singular.

Rangos

La mayoría de las plantillas algorítmicas de la biblioteca estándar que operan sobre estructuras de datos tienen interfaces que utilizan rangos.

Un iterador j se denomina accesible desde un iterador i si y solo si existe una secuencia finita de aplicaciones de la expresión ++ i que hace que i == j . Si j es accesible desde i , ambos se refieren a elementos de la misma secuencia.

Un rango es un par de iteradores que designan el inicio y el fin del cálculo. Un rango [ i , i ) es un rango vacío; en general, un rango [ i , j ) se refiere a los elementos en la estructura de datos comenzando por el elemento apuntado por i y hasta pero sin incluir el elemento apuntado por j .

El rango [ i , j ) es válido si y solo si j es accesible desde i .

(hasta C++20)

Un range puede denotarse mediante

  • [ i , s ) , con un iterador i y un sentinel s que designan el inicio y el fin del cómputo ( i y s pueden tener tipos diferentes), o
  • i + [ ​ 0 ​ , n ) , con un iterador i y un contador n que designan el inicio y el número de elementos a los que se aplicará el cómputo.
Rango iterador-sentinel

Un iterador y un sentinel que denotan un rango son comparables. [ i , s ) está vacío si i == s ; de lo contrario, [ i , s ) se refiere a los elementos en la estructura de datos comenzando por el elemento apuntado por i y hasta, pero sin incluir, el elemento, si existe, apuntado por el primer iterador j tal que j == s .

Un sentinel s se denomina alcanzable desde un iterador i si y solo si existe una secuencia finita de aplicaciones de la expresión ++ i que hace que i == s .

Si s es alcanzable desde i , [ i , s ) denota un rango válido .

Rango contado

Un counted range i + [ ​ 0 ​ , n ) está vacío si n == 0 ; de lo contrario, i + [ ​ 0 ​ , n ) se refiere a los n elementos en la estructura de datos comenzando por el elemento apuntado por i y hasta, pero sin incluir, el elemento, si existe, apuntado por el resultado de n aplicaciones de ++ i .

Un rango contado i + [ ​ 0 ​ , n ) es válido si y solo si

  • n == 0 ; o
  • se satisfacen todas las siguientes condiciones:
    • n es positivo,
    • i es desreferenciable, y
    • ++ i + [ ​ 0 ​ , -- n ) es válido.
(desde C++20)

El resultado de la aplicación de funciones en la biblioteca estándar a rangos inválidos es indefinido.

Conceptos de iterador (desde C++20)

Un nuevo sistema de iteradores basado en concepts que son diferentes de los iteradores de C++17. Si bien la taxonomía básica permanece similar, los requisitos para categorías individuales de iteradores son algo diferentes.

Definido en el espacio de nombres std
(C++20)
especifica que un tipo es indirectamente legible aplicando el operador *
(concepto)
(C++20)
especifica que un valor puede escribirse en el objeto referenciado por un iterador
(concepto)
(C++20)
especifica que un tipo semiregular puede incrementarse con operadores de preincremento y postincremento
(concepto)
(C++20)
especifica que la operación de incremento en un tipo weakly_incrementable es que preserva la igualdad y que el tipo es equality_comparable
(concepto)
(C++20) (C++20)
especifica que un tipo se comporta como un tipo entero (con signo)
( concepto solo de exposición* )
(C++20)
especifica que los objetos de un tipo pueden incrementarse y desreferenciarse
(concepto)
(C++20)
especifica que un tipo es un centinela para un tipo input_or_output_iterator
(concepto)
(C++20)
especifica que el operador - puede aplicarse a un iterador y un centinela para calcular su diferencia en tiempo constante
(concepto)
(C++20)
especifica que un tipo es un iterador de entrada, es decir, sus valores referenciados pueden leerse y puede ser preincrementado y postincrementado
(concepto)
(C++20)
especifica que un tipo es un iterador de salida para un tipo de valor dado, es decir, se pueden escribir valores de ese tipo en él y puede ser preincrementado y postincrementado
(concepto)
(C++20)
especifica que un input_iterator es un iterador de avance, que admite comparación de igualdad y múltiples pasadas
(concepto)
(C++20)
especifica que un forward_iterator es un iterador bidireccional, que admite movimiento hacia atrás
(concepto)
(C++20)
especifica que un bidirectional_iterator es un iterador de acceso aleatorio, que admite avance en tiempo constante e indexación
(concepto)
(C++20)
especifica que un random_access_iterator es un iterador contiguo, que hace referencia a elementos que son contiguos en memoria
(concepto)

Tipos asociados del iterador (desde C++20)

Definido en el espacio de nombres std
(C++20)
calcula el tipo de diferencia de un tipo weakly_incrementable
(plantilla de clase)
(C++20)
calcula el tipo de valor de un tipo indirectly_readable
(plantilla de clase)
(C++20) (C++20) (C++23) (C++20) (C++20) (C++20)
calcula los tipos asociados de un iterador
(plantilla de alias)

Primitivas de iterador

proporciona una interfaz uniforme para las propiedades de un iterador
(plantilla de clase)
(C++20)
tipos de clases vacías utilizadas para indicar categorías de iteradores
(clase)
(obsoleto en C++17)
clase base para facilitar la definición de tipos requeridos para iteradores simples
(plantilla de clase)

Puntos de personalización de iteradores (desde C++20)

Definido en el espacio de nombres std::ranges
(C++20)
convierte el resultado de desreferenciar un objeto a su tipo de referencia a valor asociado
(objeto de punto de personalización)
(C++20)
intercambia los valores referenciados por dos objetos desreferenciables
(objeto de punto de personalización)

Conceptos y utilidades de algoritmos (since C++20)

Un conjunto de conceptos y plantillas de utilidad relacionados diseñados para facilitar la restricción de operaciones comunes de algoritmos.

Definido en el encabezado <iterator>
Definido en el espacio de nombres std
Conceptos de invocación indirecta
(C++20) (C++20)
especifica que un tipo invocable puede ser invocado con el resultado de desreferenciar un indirectly_readable type
(concept)
(C++20)
especifica que un tipo invocable, cuando se invoca con el resultado de desreferenciar un indirectly_readable type, satisface predicate
(concepto)
(C++20)
especifica que un tipo invocable, cuando se invoca con el resultado de desreferenciar dos indirectly_readable tipos, satisface predicate
(concepto)
(C++20)
especifica que un tipo invocable, cuando se invoca con el resultado de desreferenciar dos indirectly_readable tipos, satisface equivalence_relation
(concepto)
(C++20)
especifica que un tipo invocable, cuando se invoca con el resultado de desreferenciar dos indirectly_readable tipos, satisface strict_weak_order
(concepto)
Requisitos comunes de algoritmos
(C++20)
especifica que los valores pueden ser movidos desde un tipo indirectly_readable a un tipo indirectly_writable
(concepto)
(C++20)
especifica que los valores pueden ser movidos desde un indirectly_readable tipo a un indirectly_writable tipo y que la operación de movimiento puede realizarse a través de un objeto intermedio
(concepto)
(C++20)
especifica que los valores pueden copiarse desde un indirectly_readable tipo a un indirectly_writable tipo
(concepto)
(C++20)
especifica que los valores pueden copiarse desde un indirectly_readable tipo a un indirectly_writable tipo y que la copia puede realizarse a través de un objeto intermedio
(concepto)
(C++20)
especifica que los valores referenciados por dos indirectly_readable tipos pueden intercambiarse
(concepto)
(C++20)
especifica que los valores referenciados por dos indirectly_readable tipos pueden ser comparados
(concepto)
(C++20)
especifica los requisitos comunes de los algoritmos que reordenan elementos en el lugar
(concept)
(C++20)
especifica los requisitos de los algoritmos que fusionan secuencias ordenadas en una secuencia de salida copiando elementos
(concept)
(C++20)
especifica los requisitos comunes de los algoritmos que permutan secuencias en secuencias ordenadas
(concept)
Utilidades
(C++20)
calcula el resultado de invocar un objeto invocable sobre el resultado de desreferenciar algún conjunto de tipos indirectly_readable
(plantilla de alias)
(C++20)
plantilla auxiliar para especificar las restricciones en algoritmos que aceptan proyecciones
(alias template)
(C++26)
calcula el tipo de valor de un indirectly_readable mediante proyección
(alias de plantilla)

Adaptadores de iteradores

adaptador de iterador para recorrido en orden inverso
(plantilla de clase)
(C++14)
crea un std::reverse_iterator del tipo inferido del argumento
(plantilla de función)
adaptador de iterador para inserción al final de un contenedor
(plantilla de clase)
crea un std::back_insert_iterator del tipo inferido del argumento
(plantilla de función)
adaptador de iterador para inserción al frente de un contenedor
(plantilla de clase)
crea un std::front_insert_iterator del tipo inferido del argumento
(plantilla de función)
adaptador de iterador para inserción en un contenedor
(plantilla de clase)
crea un std::insert_iterator del tipo inferido del argumento
(plantilla de función)
(C++23)
adaptador de iterador que convierte un iterador en un iterador constante
(plantilla de clase)
(C++23)
calcula un tipo de iterador constante para un tipo dado
(plantilla de alias)
(C++23)
calcula un tipo de centinela para ser usado con iteradores constantes
(plantilla de alias)
(C++23)
crea un std::const_iterator del tipo inferido del argumento
(plantilla de función)
(C++23)
crea un std::const_sentinel de tipo inferido a partir del argumento
(plantilla de función)
(C++11)
adaptador de iterador que se desreferencia a un valor r
(plantilla de clase)
(C++20)
adaptador de centinela para std::move_iterator
(plantilla de clase)
(C++11)
crea un std::move_iterator del tipo inferido del argumento
(plantilla de función)
(C++20)
adapta un tipo de iterador y su centinela en un tipo de iterador común
(plantilla de clase)
(C++20)
centinela predeterminado para usar con iteradores que conocen el límite de su rango
(clase)
(C++20)
adaptador de iterador que rastrea la distancia hasta el final del rango
(plantilla de clase)
(C++20)
centinela que siempre compara desigual con cualquier weakly_incrementable type
(clase)

Iteradores de flujo

iterador de entrada que lee desde std::basic_istream
(plantilla de clase)
iterador de salida que escribe en std::basic_ostream
(plantilla de clase)
iterador de entrada que lee desde std::basic_streambuf
(plantilla de clase)
iterador de salida que escribe en std::basic_streambuf
(plantilla de clase)

Operaciones de iterador

Definido en el encabezado <iterator>
avanza un iterador una distancia dada
(plantilla de función)
devuelve la distancia entre dos iteradores
(plantilla de función)
(C++11)
incrementa un iterador
(plantilla de función)
(C++11)
decrementa un iterador
(plantilla de función)
(C++20)
avanza un iterador una distancia dada o hasta un límite especificado
(objeto función de algoritmo)
(C++20)
devuelve la distancia entre un iterador y un centinela, o entre el inicio y fin de un rango
(objeto función de algoritmo)
(C++20)
incrementa un iterador una distancia dada o hasta un límite
(objeto función de algoritmo)
(C++20)
decrementa un iterador una distancia dada o hasta un límite
(objeto función de algoritmo)

Acceso a rangos (desde C++11)

Estas plantillas de función no miembro proporcionan una interfaz genérica para contenedores, arrays simples y std::initializer_list .

Definido en el encabezado <array>
Definido en el encabezado <deque>
Definido en el encabezado <flat_map>
Definido en el encabezado <flat_set>
Definido en el encabezado <forward_list>
Definido en el encabezado <inplace_vector>
Definido en el encabezado <iterator>
Definido en el encabezado <list>
Definido en el encabezado <map>
Definido en el encabezado <regex>
Definido en el encabezado <set>
Definido en el encabezado <span>
Definido en el encabezado <string>
Definido en el encabezado <string_view>
Definido en el encabezado <unordered_map>
Definido en el encabezado <unordered_set>
Definido en el encabezado <vector>
Definido en el espacio de nombres std
(C++11) (C++14)
devuelve un iterador al inicio de un contenedor o array
(plantilla de función)
(C++11) (C++14)
devuelve un iterador al final de un contenedor o array
(plantilla de función)
(C++14)
devuelve un iterador inverso al inicio de un contenedor o array
(plantilla de función)
(C++14)
devuelve un iterador inverso al final de un contenedor o array
(plantilla de función)
(C++17) (C++20)
devuelve el tamaño de un contenedor o array
(plantilla de función)
(C++17)
comprueba si el contenedor está vacío
(plantilla de función)
(C++17)
obtiene el puntero al array subyacente
(plantilla de función)

Informes de defectos

Los siguientes informes de defectos que modifican el comportamiento se aplicaron retroactivamente a los estándares de C++ publicados anteriormente.

DR Se aplica a Comportamiento publicado Comportamiento correcto
CWG 1181 C++98 los tipos array no podían ser tipos de valor pueden serlo
LWG 208 C++98 los iteradores past-the-end siempre eran no singulares pueden ser singulares
LWG 278 C++98 no se definía la validez de un iterador definido como siempre no singular
LWG 324 C++98 los iteradores de salida tenían tipos de valor los iteradores de salida tienen tipos escribibles en su lugar
LWG 407 C++98 los iteradores singulares no podían destruirse permitido
LWG 408
( N3066 ) 		C++98 los iteradores singulares no podían copiarse permitido si están inicializados por valor
LWG 1185
( N3066 ) 		C++98 LegacyForwardIterator , LegacyBidirectionalIterator
y LegacyRandomAccessIterator
siempre satisfacen LegacyOutputIterator 		podrían no satisfacer LegacyOutputIterator
LWG 1210
( N3066 ) 		C++98 la definición de singularidad del iterador y
accesibilidad dependía de contenedores 		depende de secuencias en su lugar
LWG 3009 C++17 <string_view> no proporcionaba las
plantillas de función de acceso a rangos 		proporciona estas plantillas
LWG 3987 C++23 <flat_map> y <flat_set> no
proporcionaban las plantillas de función de acceso a rangos 		proporcionan estas plantillas