Iteradores bidireccionales en C++

Después de pasar por la definición de plantilla de varios algoritmos STL como std::reverse , std::next_permutation y std::reverse_copy , debe haber encontrado su definición de plantilla que consiste en objetos de tipo Iterador bidireccional . Entonces, ¿qué son y por qué se utilizan?

Los iteradores bidireccionales son uno de los cinco tipos principales de iteradores presentes en la biblioteca estándar de C++, otros son iteradores de entrada, iterador de salida , iterador directo e iteradores de acceso aleatorio .

Los iteradores bidireccionales son iteradores que se pueden usar para acceder a la secuencia de elementos en un rango en ambas direcciones (hacia el final y hacia el principio). Son similares a los iteradores hacia adelante, excepto que también pueden moverse hacia atrás , a diferencia de los iteradores hacia adelante, que solo pueden moverse hacia adelante.

Cabe señalar que los contenedores como list, map, multimap, set y multiset admiten iteradores bidireccionales . Esto significa que si declaramos iteradores normales para ellos, serán iteradores bidireccionales, al igual que en el caso de vectores y deque, son iteradores de acceso aleatorio.

Una cosa importante a tener en cuenta es que los iteradores de acceso aleatorio también son iteradores bidireccionales válidos, como se muestra en la jerarquía de iteradores anterior.

Características sobresalientes

1. Usabilidad: dado que los iteradores directos se pueden usar en algoritmos de pasos múltiples, es decir, algoritmos que implican procesar el contenedor varias veces en varios pasos, por lo tanto, los iteradores bidireccionales también se pueden usar en algoritmos de pasos múltiples.
   .
2. Comparación de igualdad/desigualdad: un iterador bidireccional se puede comparar para la igualdad con otro iterador. Dado que los iteradores apuntan a alguna ubicación, los dos iteradores serán iguales solo cuando apunten a la misma posición, de lo contrario no.

   Entonces, las siguientes dos expresiones son válidas si A y B son iteradores bidireccionales:

   A == B  // Checking for equality
   A != B  // Checking for inequality
   

3. Eliminación de referencias: debido a que se puede eliminar la referencia de un iterador de entrada, al usar el operador * y -> como un valor r y un iterador de salida se puede eliminar la referencia como un valor l, por lo que los iteradores directos, que son la combinación de ambos, se pueden usar para ambos propósitos y, de manera similar, bidireccional. los operadores también pueden servir para ambos propósitos.

   // C++ program to demonstrate bidirectional iterator #include<iostream> #include<list> using namespace std; int main() {     list<int>v1 = {1, 2, 3, 4, 5};        // Declaring an iterator     list<int>::iterator i1;        for (i1=v1.begin();i1!=v1.end();++i1)     {         // Assigning values to locations pointed by iterator         *i1 = 1;     }        for (i1=v1.begin();i1!=v1.end();++i1)     {         // Accessing values at locations pointed by iterator         cout << (*i1) << " ";     }            return 0; }

   Producción:

   1 1 1 1 1
   

   Entonces, como podemos ver aquí, podemos acceder y asignar valor al iterador, por lo tanto, el iterador es un iterador bidireccional.

4. Incrementable: un iterador bidireccional se puede incrementar, de modo que se refiera al siguiente elemento en secuencia, usando el operador ++().

   Entonces, las siguientes dos expresiones son válidas si A es un iterador bidireccional:

   A++   // Using post increment operator
   ++A   // Using pre increment operator
   

5. Decrementable: esta es la característica que diferencia un iterador bidireccional de un iterador directo. Así como podemos usar el operador ++() con iteradores bidireccionales para incrementarlos, también podemos disminuirlos.

   Por eso, su nombre es bidireccional, lo que demuestra que puede moverse en ambas direcciones .

   // C++ program to demonstrate bidirectional iterator #include<iostream> #include<list> using namespace std; int main() {     list<int>v1 = {1, 2, 3, 4, 5};        // Declaring an iterator     list<int>::iterator i1;        // Accessing the elements from end using decrement     // operator     for (i1=v1.end();i1!=v1.begin();--i1)     {         if (i1 != v1.end())         {             cout << (*i1) << " ";         }     }     cout << (*i1);            return 0; }

   Producción:

   5 4 3 2 1
   

   Dado que comenzamos desde el final de la lista y luego avanzamos hacia el principio al disminuir el puntero, lo que muestra que el operador de disminución se puede usar con dichos iteradores. Aquí, hemos ejecutado el bucle hasta que el iterador se vuelve igual a begin(), por eso el primer valor no se imprime dentro del bucle y lo hemos impreso por separado.

6. Intercambiable: el valor al que apuntan estos iteradores se puede intercambiar o intercambiar.

Implementación práctica

Después de comprender sus características, es muy importante conocer también su implementación práctica. Como se dijo anteriormente, los iteradores bidireccionales se pueden usar para todos los propósitos en los que se puede usar el iterador de avance dentro de aquellas situaciones en las que se debe disminuir el iterador. Los siguientes dos algoritmos STL pueden mostrar este hecho:

• std::reverse_copy: como sugiere el nombre, este algoritmo se usa para copiar un rango en otro rango, pero en orden inverso. Ahora, en lo que respecta al acceso a los elementos y la asignación de elementos, los iteradores directos están bien, pero tan pronto como tengamos que disminuir el iterador, entonces no podemos usar estos iteradores directos para este propósito, y ahí es donde vienen los iteradores bidireccionales para nuestro rescate.

  // Definition of std::reverse_copy() template  OutputIterator reverse_copy(BidirectionalIterator first,                             BidirectionalIterator last,                             OutputIterator result)  {     while (first != last)      *result++ = *--last;     return result; }

  Aquí, podemos ver que hemos declarado último como un iterador bidireccional, ya que no podemos disminuir un iterador directo como se hizo en el caso de último, por lo que no podemos usarlo en este escenario, y tenemos que declararlo solo como un iterador bidireccional.

• std::random_shuffle: Como sabemos, este algoritmo se utiliza para barajar aleatoriamente todos los elementos presentes en un contenedor. Entonces, veamos su funcionamiento interno (no entre en detalles, solo mire dónde se pueden usar iteradores bidireccionales y dónde no):

  // Definition of std::random_shuffle() template  void random_shuffle(RandomAccessIterator first,                     RandomAccessIterator last,                     RandomNumberGenerator& gen) {     iterator_traits::difference_type i, n;     n = (last - first);     for (i=n-1; i>0; --i)      {         swap (first[i],first[gen(i+1)]);     } }

  Aquí, podemos ver que hemos hecho uso de iteradores de acceso aleatorio, ya que aunque podemos incrementar un iterador bidireccional, disminuirlo también, pero no podemos aplicarle un operador aritmético como +, – y esto es lo que se requiere en este algoritmo. , donde se hace (last – first), por lo que, por este motivo, no podemos usar un iterador bidireccional en estos escenarios.

Nota: Como sabemos que el iterador bidireccional está más arriba en la jerarquía que el iterador directo, que es a su vez más alto que los iteradores de entrada y salida, por lo tanto, estos tres tipos de iteradores pueden sustituirse por iteradores bidireccionales, sin afectar el funcionamiento del algoritmo.

Entonces, los dos ejemplos anteriores muestran muy bien cuándo, dónde, por qué y cómo se usan los iteradores bidireccionales en la práctica.

Limitaciones

Después de estudiar las características más destacadas, también se deben conocer sus deficiencias, aunque no hay tantas como en los iteradores de entrada o salida, ya que está más arriba en la jerarquía.

1. Operadores relacionales: aunque los iteradores bidireccionales se pueden usar con el operador de igualdad (==), pero no se pueden usar con otros operadores relacionales como , =.

   If A and B are Bidirectional iterators, then
   
   A == B     // Allowed
   A <= B     // Not Allowed
   

2. Operadores aritméticos: al igual que los operadores relacionales, tampoco se pueden usar con operadores aritméticos como +, –, etc. Esto significa que los iteradores bidireccionales pueden moverse en ambas direcciones, pero secuencialmente.

   If A and B are Bidirectional iterators, then
   
   A + 1     // Not allowed
   B - 2     // Not allowed
   

   // C++ program to demonstrate bidirectional iterator #include<iostream> #include<list> using namespace std; int main() {     list<int>v1 = {1, 2, 3, 4, 5};        // Declaring first iterator     list<int>::iterator i1;        // Declaring second iterator     list<int>::iterator i2;        // i1 points to the beginning of the list     i1 = v1.begin();        // i2 points to the end of the list     i2 = v1.end();        // Applying relational operator to them     if ( i1 > i2)     {         cout << "Yes";     }      // This will throw an error because relational     // operators cannot be applied to bidirectional iterators           // Applying arithmetic operator to them     int count = i1 - i2;     // This will also throw an error because arithmetic      // operators cannot be applied to bidirectional iterators       return 0; }

   Producción:

   Error, because of use of arithmetic and relational operators 
   with bidirectional iterators 
   

3. Uso del operador de desreferencia de desplazamiento ([ ]): los iteradores bidireccionales no admiten el operador de desreferencia de desplazamiento ([ ]), que se utiliza para el acceso aleatorio.

   If A is a Bidirectional iterator, then
   A[3]    // Not allowed 
   

Este artículo es una contribución de Mrigendra Singh . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.