C++ Visión general


Ejemplo

Los iteradores son posiciones

Los iteradores son un medio para navegar y operar en una secuencia de elementos y son una extensión generalizada de punteros. Conceptualmente es importante recordar que los iteradores son posiciones, no elementos. Por ejemplo, tome la siguiente secuencia:

A B C

La secuencia contiene tres elementos y cuatro posiciones.

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+

Los elementos son cosas dentro de una secuencia. Las posiciones son lugares donde pueden suceder operaciones significativas a la secuencia. Por ejemplo, uno se inserta en una posición, antes o después del elemento A, no en un elemento. Incluso la eliminación de un elemento ( erase(A) ) se realiza primero encontrando su posición y luego eliminándola.

De los iteradores a los valores

Para convertir de una posición a un valor, un iterador se elimina de referencia :

auto my_iterator = my_vector.begin(); // position
auto my_value = *my_iterator; // value

Uno puede pensar en un iterador como una desreferencia al valor al que se refiere en la secuencia. Esto es especialmente útil para comprender por qué nunca debe desreferenciar el iterador end() en una secuencia:

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+
  ↑           ↑
  |           +-- An iterator here has no value. Do not dereference it!
  +-------------- An iterator here dereferences to the value A.

En todas las secuencias y contenedores que se encuentran en la biblioteca estándar de C ++, begin() devolverá un iterador a la primera posición, y end() devolverá un iterador a una pasada la última posición (¡ no la última posición!). En consecuencia, los nombres de estos iteradores en algoritmos a menudo se etiquetan first y last :

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+
  ↑           ↑
  |           |
  +- first    +- last

También es posible obtener un iterador para cualquier secuencia , porque incluso una secuencia vacía contiene al menos una posición:

+---+
|   |
+---+

En una secuencia vacía, begin() y end() estarán en la misma posición, y ninguna de ellas puede ser referenciada:

+---+
|   |
+---+
  ↑
  |
  +- empty_sequence.begin()
  |
  +- empty_sequence.end()

La visualización alternativa de los iteradores es que marcan las posiciones entre los elementos:

+---+---+---+
| A | B | C |
+---+---+---+
↑   ^   ^   ↑
|           |
+- first    +- last

y la anulación de la referencia a un iterador devuelve una referencia al elemento que viene después del iterador. Algunas situaciones donde esta vista es particularmente útil son:

  • insert operaciones de insert insertarán elementos en la posición indicada por el iterador,
  • erase operaciones de erase devolverán un iterador correspondiente a la misma posición que la pasada,
  • un iterador y su correspondiente iterador inverso están ubicados en la misma posición entre los elementos

Iteradores inválidos

Un iterador se invalida si (por ejemplo, en el curso de una operación) su posición ya no forma parte de una secuencia. No se puede anular la referencia a un iterador invalidado hasta que se haya reasignado a una posición válida. Por ejemplo:

std::vector<int>::iterator first;
{
    std::vector<int> foo;
    first = foo.begin(); // first is now valid
} // foo falls out of scope and is destroyed
// At this point first is now invalid

Los muchos algoritmos y las funciones de miembro de secuencia en la biblioteca estándar de C ++ tienen reglas que rigen cuándo se invalidan los iteradores. Cada algoritmo es diferente en la forma en que tratan (e invalidan) los iteradores.

Navegando con iteradores

Como sabemos, los iteradores son para navegar por secuencias. Para hacer eso, un iterador debe migrar su posición a lo largo de la secuencia. Los iteradores pueden avanzar en la secuencia y algunos pueden avanzar hacia atrás:

auto first = my_vector.begin();
++first;                                             // advance the iterator 1 position
std::advance(first, 1);                              // advance the iterator 1 position
first = std::next(first);                            // returns iterator to the next element
std::advance(first, -1);                             // advance the iterator 1 position backwards
first = std::next(first, 20);                        // returns iterator to the element 20 position forward
first = std::prev(first, 5);                         // returns iterator to the element 5 position backward
auto dist = std::distance(my_vector.begin(), first); // returns distance between two iterators.

Tenga en cuenta que el segundo argumento de std :: distance debe ser accesible desde el primero (o, en otras palabras, first debe ser menor o igual que el second ).

Aunque puede realizar operadores aritméticos con iteradores, no todas las operaciones están definidas para todos los tipos de iteradores. a = b + 3; funcionaría para los iteradores de acceso aleatorio, pero no funcionaría para los iteradores delanteros o bidireccionales, que aún pueden avanzar en 3 posiciones con algo como b = a; ++b; ++b; ++b; . Por lo tanto, se recomienda utilizar funciones especiales en caso de que no esté seguro de qué tipo de iterador (por ejemplo, en una función de plantilla que acepta iterador).

Conceptos de iterador

El estándar de C ++ describe varios conceptos diferentes de iteradores. Estos se agrupan de acuerdo a cómo se comportan en las secuencias a las que se refieren. Si conoce el concepto que modela un iterador (se comporta como), puede estar seguro del comportamiento de ese iterador independientemente de la secuencia a la que pertenezca . A menudo se describen en orden de la más a la menos restrictiva (porque el siguiente concepto de iterador es un paso mejor que su predecesor):

  • Iteradores de entrada: pueden ser referenciados solo una vez por posición. Solo puede avanzar, y solo una posición a la vez.
  • Iteradores de avance: un iterador de entrada que puede ser referenciado en cualquier cantidad de veces.
  • Iteradores bidireccionales: un iterador hacia adelante que también puede avanzar hacia atrás una posición a la vez.
  • Iteradores de acceso aleatorio: un iterador bidireccional que puede avanzar o retroceder cualquier número de posiciones a la vez.
  • Iteradores contiguos (desde C ++ 17): un iterador de acceso aleatorio que garantiza que los datos subyacentes son contiguos en la memoria.

Los algoritmos pueden variar según el concepto modelado por los iteradores que se les dan. Por ejemplo, aunque random_shuffle se puede implementar para los iteradores hacia adelante, se podría proporcionar una variante más eficiente que requiera iteradores de acceso aleatorio.

Rasgos del iterador

Los rasgos del iterador proporcionan una interfaz uniforme a las propiedades de los iteradores. Le permiten recuperar valores, diferencias, punteros, tipos de referencia y también la categoría de iterador:

template<class Iter>
Iter find(Iter first, Iter last, typename std::iterator_traits<Iter>::value_type val)  {
    while (first != last) {
        if (*first == val)
            return first;
        ++first;
    }
    return last;
}

La categoría de iterador se puede utilizar para especializar algoritmos:

template<class BidirIt>
void test(BidirIt a, std::bidirectional_iterator_tag)  {
    std::cout << "Bidirectional iterator is used" << std::endl;
}
 
template<class ForwIt>
void test(ForwIt a, std::forward_iterator_tag)  {
    std::cout << "Forward iterator is used" << std::endl;
}
 
template<class Iter>
void test(Iter a)  {
    test(a, typename std::iterator_traits<Iter>::iterator_category());
}

Las categorías de iteradores son básicamente conceptos de iteradores, excepto que los iteradores contiguos no tienen su propia etiqueta, ya que se encontró que rompe el código.