Lista de reenvío y lista de mapas desordenados en C++ con ejemplos

Posted on by Rudeus Greyrat

Lista de reenvíos

Lista de reenvíoen STL implementa una lista enlazada individualmente. Introducidas desde C++ 11, las listas de reenvío son más útiles que otros contenedores en las operaciones de inserción, eliminación y movimiento (como ordenar) y permiten la inserción y eliminación constante de elementos en el tiempo. Se diferencia de la lista por el hecho de que la lista de reenvío realiza un seguimiento de la ubicación solo del siguiente elemento, mientras que la lista realiza un seguimiento de los elementos anterior y siguiente, lo que aumenta el espacio de almacenamiento necesario para almacenar cada elemento. El inconveniente de una lista hacia adelante es que no se puede iterar hacia atrás y no se puede acceder directamente a sus elementos individuales. La lista de reenvío se prefiere a la lista cuando solo se requiere el recorrido hacia adelante (igual que se prefiere la lista de enlaces simples a la lista de enlaces dobles) ya que podemos ahorrar espacio. Algunos casos de ejemplo son, enstringmiento en hashing, representación de lista de adyacencia del gráfico,

Funciones utilizadas con la lista de reenvío:

  • push_front(x): agrega un nuevo elemento ‘x’ al comienzo de la lista de reenvío.
  • pop_front(): esta función se utiliza para eliminar el primer elemento de la lista de reenvío.

Lista

Las listas son contenedores de secuencias que permiten la asignación de memoria no contigua. En comparación con el vector, la lista tiene un recorrido lento, pero una vez que se ha encontrado una posición, la inserción y la eliminación son rápidas. Normalmente, cuando decimos una Lista, hablamos de una lista doblemente enlazada. Para implementar una lista de enlace simple, usamos una lista de reenvío.

Funciones utilizadas con la lista:

  • front(): Devuelve el valor del primer elemento de la lista.
  • back(): Devuelve el valor del último elemento de la lista.
  • push_front(x): Agrega un nuevo elemento ‘x’ al principio de la lista.
  • push_back(x): Agrega un nuevo elemento ‘x’ al final de la lista.

Mapa_desordenado

Un mapa desordenado es un contenedor asociado que almacena elementos formados por la combinación de clave-valor y un valor mapeado. El valor de la clave se utiliza para identificar de forma única el elemento y el valor asignado es el contenido asociado con la clave. Tanto la clave como el valor pueden ser de cualquier tipo predefinido o definido por el usuario. Internamente, se implementa un mapa desordenado utilizando Hash Table .

Funciones utilizadas con el mapa desordenado:

  • at(): Esta función en C++ unordered_map devuelve la referencia al valor con el elemento como clave k.
  • begin(): Devuelve un iterador que apunta al primer elemento del contenedor en el contenedor unordered_map
  • end(): devuelve un iterador que apunta a la posición más allá del último elemento en el contenedor en el contenedor unordered_map
  • size(): Devuelve el número de elementos presentes dentro del mapa desordenado.

Este artículo se centra en cómo podemos usar una lista de reenvío y una lista de mapas desordenados en C++. El vector de listas y las listas de reenvío pueden ser bastante útiles al diseñar estructuras de datos complejas. 

Reenviar lista de mapas desordenados

A continuación se muestra la implementación utilizando una lista directa de mapas desordenados:

Ejemplo 1:

C++

// C++ program to implement
// the above concept
#include <bits/stdc++.h>
using namespace std;
  
// Function to print forward 
// list elements
void print(forward_list<unordered_map<int, int> >& 
           forwardList1)
{
  cout << "Forward List : \n";
    
  for (auto currentUnorderedMap : forwardList1) 
  {
    // Each element of the forward_list 
    // is a unordered map
  
    cout << "Unordered Map : ";
    cout << "[   ";
  
    // Print unordered map elements
    for (auto it = currentUnorderedMap.begin();
              it != currentUnorderedMap.end(); it++) 
    {
      cout << "First : " << it->first << " , " << 
              "Second : " << it->second << "   ";
    }
    cout << "]\n";
  }
}
  
// Driver code
int main()
{
  // Declaring a forward list of 
  // unordered maps
  forward_list<unordered_map<int, int> > 
  forwardList1;
  
  // Declaring a unordered map
  unordered_map<int, int> unorderedMap1;
  
  // Hashing values
  unorderedMap1[2] = 4;
  unorderedMap1[4] = 3;
  unorderedMap1[6] = 9;
  
  // Push back the unordered map in 
  // the forward list
  forwardList1.push_front(unorderedMap1);
  
  // Declaring another unordered map
  unordered_map<int, int> unorderedMap2;
  
  // Hashing values
  unorderedMap2[31] = 8;
  unorderedMap2[11] = 3;
  unorderedMap2[23] = 7;
  
  // Push back the unordered map in 
  // the forward list
  forwardList1.push_front(unorderedMap2);
  
  // Declaring another unordered map
  unordered_map<int, int> unorderedMap3;
  
  // Hashing values
  unorderedMap3[7] = 3;
  unorderedMap3[18] = 1;
  unorderedMap3[9] = 6;
    
  // Push back the unordered map in 
  // the forward list
  forwardList1.push_front(unorderedMap3);
  
  // Declaring another unordered map
  unordered_map<int, int> unorderedMap4;
  
  // Hashing values
  unorderedMap4[32] = 9;
  unorderedMap4[15] = 3;
  unorderedMap4[97] = 5;
  
  // Push back the unordered map in 
  // the forward list
  forwardList1.push_front(unorderedMap4);
  
  print(forwardList1);
  return 0;
}

Producción:

Lista adelante:  
Mapa desordenado: [Primero: 97, Segundo: 5 Primero: 32, Segundo: 9 Primero: 15, Segundo: 3]
Mapa desordenado: [Primero: 9, Segundo: 6 Primero: 7, Segundo: 3 Primero: 18 , Segundo : 1 ]
Mapa desordenado : [ Primero : 23 , Segundo : 7 Primero : 31 , Segundo : 8 Primero : 11 , Segundo : 3 ]
Mapa desordenado : [ Primero : 6 , Segundo : 9 Primero : 2 , Segundo : 4 Primero : 4 , Segundo : 3 ]

Ejemplo 2:

C++

// C++ program to implement
// the above concept
#include <bits/stdc++.h>
using namespace std;
  
// Function to print forward 
// list elements
void print(forward_list<unordered_map<int, string> >& 
           forwardList1)
{
  cout << "Forward List : \n";
    
  for (auto currentUnorderedMap : forwardList1)
  {
    // Each element of the forward list is 
    // a unordered map
  
    cout << "Unordered Map : ";
    cout << "[   ";
  
    // Print unordered map elements
    for (auto it = currentUnorderedMap.begin();
              it != currentUnorderedMap.end(); it++) 
    {
      cout << "First : " << it->first << " , " << 
              "Second : " << it->second << "   ";
    }
    cout << "]\n";
  }
}
  
// Driver code
int main()
{
  // Declaring a forward_list of 
  // unordered maps
  forward_list<unordered_map<int, string> > 
  forwardList1;
  
  // Declaring a unordered map
  unordered_map<int, string> unorderedMap1;
  
  // Hashing values
  unorderedMap1[2] = "Geeks";
  unorderedMap1[4] = "for";
  unorderedMap1[6] = "Geeks";
  
  // Push back the unordered map in 
  // the forward list
  forwardList1.push_front(unorderedMap1);
  
  // Declaring another unordered map
  unordered_map<int, string> unorderedMap2;
  
  // Hashing values
  unorderedMap2[3] = "Python";
  unorderedMap2[11] = "Java";
  unorderedMap2[23] = "C++";
  
  // Push back the unordered map in 
  // the forward list
  forwardList1.push_front(unorderedMap2);
  
  // Declaring another unordered map
  unordered_map<int, string> unorderedMap3;
  
  // Hashing values
  unorderedMap3[7] = "C";
  unorderedMap3[18] = "PHP";
  unorderedMap3[9] = "Swift";
    
  // Push back the unordered map in 
  // the forward list
  forwardList1.push_front(unorderedMap3);
  
  // Declaring another unordered map
  unordered_map<int, string> unorderedMap4;
  
  // Hashing values
  unorderedMap4[121] = "Hello";
  unorderedMap4[97] = "Coding";
  unorderedMap4[197] = "World";
  
  // Push back the unordered map in 
  // the forward list
  forwardList1.push_front(unorderedMap4);
  
  print(forwardList1);
  return 0;
}

Producción:

Lista de reenvío:  
Mapa desordenado: [Primero: 197, Segundo: Primero mundial: 121, Segundo: Hola Primero: 97, Segundo: Codificación]
Mapa desordenado: [Primero: 9, Segundo: Swift Primero: 7, Segundo: C Primero: 18 , Segundo : PHP ]
Mapa desordenado : [ Primero : 23 , Segundo : C++ Primero : 3 , Segundo : Python Primero : 11 , Segundo : Java ]
Mapa desordenado : [ Primero : 6 , Segundo : Geeks Primero : 2 , Segundo : Geeks primero : 4 , Segundo : para ]

Lista de mapas desordenados

A continuación se muestra la implementación usando una lista de mapas desordenados:

Ejemplo 1:

C++

// C++ program to implement
// the above concept
#include <bits/stdc++.h>
using namespace std;
  
// Function to print list elements
void print(list<unordered_map<int, int> >& 
           List)
{
  cout << "List : \n";
  for (auto currentUnorderedMap : List) 
  {
    // Each element of the list is 
    // a unordered map
    cout << "Unordered Map : ";
    cout << "[   ";
  
    // Print unordered map elements
    for (auto it = currentUnorderedMap.begin();
              it != currentUnorderedMap.end(); it++) 
    {
      cout << "First : " << it->first << " , " << 
              "Second : " << it->second << "   ";
    }
    cout << "]\n";
  }
}
  
// Driver code
int main()
{
  // Declaring a list of unordered maps
  list<unordered_map<int, int> > List;
  
  // Declaring a unordered map
  unordered_map<int, int> unorderedMap1;
  
  // Hashing values
  unorderedMap1[2] = 4;
  unorderedMap1[4] = 3;
  unorderedMap1[6] = 9;
  
  // Push back the unordered map 
  // in the list
  List.push_front(unorderedMap1);
  
  // Declaring another unordered map
  unordered_map<int, int> unorderedMap2;
  
  // Hashing values
  unorderedMap2[31] = 8;
  unorderedMap2[11] = 3;
  unorderedMap2[23] = 7;
  
  // Push back the unordered map 
  // in the list
  List.push_front(unorderedMap2);
  
  // Declaring another unordered map
  unordered_map<int, int> unorderedMap3;
  
  // Hashing values
  unorderedMap3[7] = 3;
  unorderedMap3[18] = 1;
  unorderedMap3[9] = 6;
    
  // Push back the unordered map 
  // in the list
  List.push_front(unorderedMap3);
  
  // Declaring another unordered map
  unordered_map<int, int> unorderedMap4;
  
  // Hashing values
  unorderedMap4[32] = 9;
  unorderedMap4[15] = 3;
  unorderedMap4[97] = 5;
  
  // Push back the unordered map 
  // in the list
  List.push_front(unorderedMap4);
  
  print(List);
  return 0;
}

Producción:

Lista :  
Mapa desordenado : [ Primero : 97 , Segundo : 5 Primero : 32 , Segundo : 9 Primero : 15 , Segundo : 3 ]
Mapa desordenado : [ Primero : 9 , Segundo : 6 Primero : 7 , Segundo : 3 Primero : 18 , Segundo : 1 ]
Mapa desordenado : [ Primero : 23 , Segundo : 7 Primero : 31 , Segundo : 8 Primero : 11 , Segundo : 3 ]
Mapa desordenado : [ Primero : 6 , Segundo : 9 Primero : 2 , Segundo : 4 Primero : 4 , Segundo : 3 ]

Ejemplo 2:

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to print list elements
void print(list<unordered_map<int, string> >& List)
{
  cout << "List : \n";
  for (auto currentUnorderedMap : List) 
  {
    // Each element of the list is 
    // a unordered map
    cout << "Unordered Map : ";
    cout << "[   ";
  
    // Print unordered map elements
    for (auto it = currentUnorderedMap.begin();
              it != currentUnorderedMap.end(); it++) 
    {
      cout << "First : " << it->first << " , " << 
              "Second : " << it->second << "   ";
    }
    cout << "]\n";
  }
}
  
// Driver code
int main()
{
  // Declaring a list of unordered maps
  list<unordered_map<int, string> > List;
  
  // Declaring a unordered map
  unordered_map<int, string> unorderedMap1;
  
  // Hashing values
  unorderedMap1[2] = "Geeks";
  unorderedMap1[4] = "for";
  unorderedMap1[6] = "Geeks";
  
  // Push back the unordered map in 
  // the forward list
  List.push_front(unorderedMap1);
  
  // Declaring another unordered map
  unordered_map<int, string> unorderedMap2;
  
  // Hashing values
  unorderedMap2[3] = "Python";
  unorderedMap2[11] = "Java";
  unorderedMap2[23] = "C++";
  
  // Push back the unordered map in 
  // the forward list
  List.push_front(unorderedMap2);
  
  // Declaring another unordered map
  unordered_map<int, string> unorderedMap3;
  
  // Hashing values
  unorderedMap3[7] = "C";
  unorderedMap3[18] = "PHP";
  unorderedMap3[9] = "Swift";
    
  // Push back the unordered map in 
  // the forward list
  List.push_front(unorderedMap3);
  
  // Declaring another unordered map
  unordered_map<int, string> unorderedMap4;
  
  // Hashing values
  unorderedMap4[121] = "Hello";
  unorderedMap4[97] = "Coding";
  unorderedMap4[197] = "World";
  
  // Push back the unordered map in 
  // the forward list
  List.push_front(unorderedMap4);
  
  print(List);
  return 0;
}

Producción:

Lista:  
Mapa desordenado: [Primero: 197, Segundo: Mundo Primero: 121, Segundo: Hola Primero: 97, Segundo: Codificación]
Mapa desordenado: [Primero: 9, Segundo: Swift Primero: 7, Segundo: C Primero: 18, Segundo: PHP]
Mapa desordenado: [Primero: 23, Segundo: C++ Primero: 3, Segundo: Python Primero: 11, Segundo: Java]
Mapa desordenado: [Primero: 6, Segundo: Geeks Primero: 2, Segundo: Geeks Primero: 4 , Segundo : para ]

Publicación traducida automáticamente

Artículo escrito por bhuwanesh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *