C++
Iteradores

Iteradores C (Punteros)

// This creates an array with 5 values.
const int array[] = { 1, 2, 3, 4, 5 };

#ifdef BEFORE_CPP11

// You can use `sizeof` to determine how many elements are in an array.
const int* first = array;
const int* afterLast = first + sizeof(array) / sizeof(array[0]);

// Then you can iterate over the array by incrementing a pointer until
// it reaches past the end of our array.
for (const int* i = first; i < afterLast; ++i) {
    std::cout << *i << std::endl;
}

#else

// With C++11, you can let the STL compute the start and end iterators:
for (auto i = std::begin(array); i != std::end(array); ++i) {
    std::cout << *i << std::endl;
}

#endif

Este código emitiría los números del 1 al 5, uno en cada línea de la siguiente manera:

1
2
3
4
5

Rompiendolo

const int array[] = { 1, 2, 3, 4, 5 };

Esta línea crea una nueva matriz de enteros con 5 valores. Las matrices C son solo punteros a la memoria donde cada valor se almacena junto en un bloque contiguo.

const int* first = array;
const int* afterLast = first + sizeof(array) / sizeof(array[0]);

Estas líneas crean dos punteros. El primer puntero recibe el valor del puntero de matriz, que es la dirección del primer elemento de la matriz. El operador sizeof cuando se utiliza en una matriz C devuelve el tamaño de la matriz en bytes. Dividido por el tamaño de un elemento, se obtiene el número de elementos en la matriz. Podemos usar esto para encontrar la dirección del bloque después de la matriz.

for (const int* i = first; i < afterLast; ++i) {

Aquí creamos un puntero que usaremos como iterador. Se inicia con la dirección del primer elemento que queremos para repetir, y vamos a seguir para recorrer todo el tiempo que i es menor que afterLast , lo que significa el tiempo que i está apuntando a una dirección dentro de array .

    std::cout << *i << std::endl;

Por último, dentro del bucle podemos acceder al valor al que apunta nuestro iterador i mediante la anulación de la referencia. Aquí el operador de desreferencia * devuelve el valor en la dirección en i .

Visión general

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.

Iteradores inversos

Si queremos iterar hacia atrás a través de una lista o vector, podemos usar un reverse_iterator . Un iterador inverso se realiza a partir de un iterador de acceso aleatorio o bidireccional que mantiene como miembro al que se puede acceder a través de base() .

Para iterar hacia atrás, utilice rbegin() y rend() como los iteradores para el final de la colección y el inicio de la colección, respectivamente.

Por ejemplo, para iterar hacia atrás use:

std::vector<int> v{1, 2, 3, 4, 5};
for (std::vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it)
{
    cout << *it;
} // prints 54321

Un iterador inverso se puede convertir en un iterador directo a través de la función miembro base() . La relación es que el iterador inverso hace referencia a un elemento más allá del iterador base() :

std::vector<int>::reverse_iterator r = v.rbegin();
std::vector<int>::iterator i = r.base();
assert(&*r == &*(i-1)); // always true if r, (i-1) are dereferenceable
                        // and are not proxy iterators

 +---+---+---+---+---+---+---+
 |   | 1 | 2 | 3 | 4 | 5 |   |
 +---+---+---+---+---+---+---+
   ↑   ↑               ↑   ↑
   |   |               |   |
rend() |         rbegin()  end()
       |                   rbegin().base()
     begin()
     rend().base()

En la visualización donde los iteradores marcan posiciones entre elementos, la relación es más simple:

  +---+---+---+---+---+
  | 1 | 2 | 3 | 4 | 5 |
  +---+---+---+---+---+
  ↑                   ↑
  |                   |
  |                 end()
  |                 rbegin()
begin()             rbegin().base()
rend()
rend().base()

Iterador de vectores

begin devuelve un iterator al primer elemento en el contenedor de secuencia.

end devuelve un iterator al primer elemento más allá del final.

Si el objeto vectorial es const , tanto begin como end devuelven un const_iterator . Si desea que se const_iterator un const_iterator incluso si su vector no es const , puede usar cbegin y cend .

Ejemplo:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = { 1, 2, 3, 4, 5 };  //intialize vector using an initializer_list

    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }

    return 0;
}

Salida:

1 2 3 4 5

Iterador de mapas

Un iterador para el primer elemento en el contenedor.

Si un objeto de mapa está constante, la función devuelve un const_iterator . De lo contrario, devuelve un iterator .

// Create a map and insert some values
std::map<char,int> mymap;
mymap['b'] = 100;
mymap['a'] = 200;
mymap['c'] = 300;

// Iterate over all tuples
for (std::map<char,int>::iterator it = mymap.begin(); it != mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';

Salida:

a => 200
b => 100
c => 300

Iteradores de corriente

Los iteradores de flujo son útiles cuando necesitamos leer una secuencia o imprimir datos formateados desde un contenedor:

// Data stream. Any number of various whitespace characters will be OK.
std::istringstream istr("1\t 2     3 4");
std::vector<int> v;

// Constructing stream iterators and copying data from stream into vector.
std::copy(
    // Iterator which will read stream data as integers.
    std::istream_iterator<int>(istr),
    // Default constructor produces end-of-stream iterator.
    std::istream_iterator<int>(),
    std::back_inserter(v));

// Print vector contents.
std::copy(v.begin(), v.end(),
    //Will print values to standard output as integers delimeted by " -- ".
    std::ostream_iterator<int>(std::cout, " -- "));

El programa de ejemplo imprimirá 1 -- 2 -- 3 -- 4 -- en salida estándar.

Escribe tu propio iterador respaldado por generador

Un patrón común en otros idiomas es tener una función que produce un "flujo" de objetos, y poder usar un código de bucle para recorrerlo.

Podemos modelar esto en C ++ como

template<class T>
struct generator_iterator {
  using difference_type=std::ptrdiff_t;
  using value_type=T;
  using pointer=T*;
  using reference=T;
  using iterator_category=std::input_iterator_tag;
  std::optional<T> state;
  std::function< std::optional<T>() > operation;
  // we store the current element in "state" if we have one:
  T operator*() const {
    return *state;
  }
  // to advance, we invoke our operation.  If it returns a nullopt
  // we have reached the end:
  generator_iterator& operator++() {
    state = operation();
    return *this;        
  }
  generator_iterator operator++(int) {
    auto r = *this;
    ++(*this);
    return r;
  }
  // generator iterators are only equal if they are both in the "end" state:
  friend bool operator==( generator_iterator const& lhs, generator_iterator const& rhs ) {
    if (!lhs.state && !rhs.state) return true;
    return false;
  }
  friend bool operator!=( generator_iterator const& lhs, generator_iterator const& rhs ) {
    return !(lhs==rhs);
  }
  // We implicitly construct from a std::function with the right signature:
  generator_iterator( std::function< std::optional<T>() > f ):operation(std::move(f))
  {
    if (operation)
      state = operation();
  }
  // default all special member functions:
  generator_iterator( generator_iterator && ) =default;
  generator_iterator( generator_iterator const& ) =default;
  generator_iterator& operator=( generator_iterator && ) =default;
  generator_iterator& operator=( generator_iterator const& ) =default;
  generator_iterator() =default;
};

ejemplo vivo .

Almacenamos el elemento generado temprano para que podamos detectar más fácilmente si ya estamos al final.

Como la función de un iterador de generador final nunca se usa, podemos crear un rango de iteradores de generador copiando solo la std::function . Un iterador de generador construido por defecto se compara igual a sí mismo y con todos los demás iteradores de generador final.