Lista de reenvío y lista de pares 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(): esta función se usa para insertar el elemento en la primera posición en una lista hacia adelante. El valor de esta función se copia en el espacio antes del primer elemento del contenedor. El tamaño de la lista de reenvío aumenta en 1.
  • pop_front(): esta función se utiliza para eliminar el primer elemento de la lista.

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.

Par

Un contenedor de pares es un contenedor simple que se define en el encabezado <utilidad> y consta de dos elementos de datos u objetos. En un par, el primer objeto se referencia con «primero» y el segundo objeto se referencia como «segundo» y el orden se fija como {primero, segundo}.

Sintaxis 1: 

forward_list<pair<data_type1, data_type2>> forwardList;

Aquí,
data_type1 y data_type2 son los tipos de datos.
La lista de reenvío declarada puede almacenar pares como un elemento que consta solo de esos tipos de datos. 

Sintaxis 2: 

lista<par<tipo_datos1, tipo_datos2>> Lista;

Aquí, 
data_type1 y data_type2 son los tipos de datos.
La lista declarada puede almacenar pares como un elemento que consta solo de esos tipos de datos. 

Reenviar lista de pares

A continuación se muestra la implementación de una lista directa de pares:  

Ejemplo 1:

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print forward
// list elements
void print(forward_list<pair<int, int> >&
           forwardListOfPairs)
{
 
  cout << "Forward List : " << '\n';
  for (auto currentPair : forwardListOfPairs)
  {
    // Each element of the forwardList is
    // a pair itself
    pair<int, int> currentpair = currentPair;
 
    cout << "[ ";
 
    // Printing pair contents
    cout << currentPair.first << ' ' <<
            currentPair.second;
    cout << ']';
    cout << '\n';
  }
}
 
// Driver code
int main()
{
  // Declaring a forward list of pairs
  forward_list<pair<int, int> >
  forwardListOfPairs;
 
  // Declaring a pair
  pair<int, int> pair1;
 
  // Initializing the
  // pair
  pair1 = make_pair(11, 22);
 
  // Push the pair at the back
  // in the forward list
  forwardListOfPairs.push_front(pair1);
 
  // Declaring another pair
  pair<int, int> pair2;
 
  // Initializing the
  // pair
  pair2 = make_pair(33, 44);
 
  // Push the pair at the front
  // in the forward list
  forwardListOfPairs.push_front(pair2);
 
  // Declaring another pair
  pair<int, int> pair3;
 
  // Initializing the pair
  pair3 = make_pair(55, 66);
 
  // Push the pair at the front
  // in the forward list
  forwardListOfPairs.push_front(pair3);
 
  // Declaring another pair
  pair<int, int> pair4;
 
  // Initializing the pair
  pair4 = make_pair(77, 88);
 
  // Push the pair at the front
  // in the forward list
  forwardListOfPairs.push_front(pair4);
 
  // Calling print function
  print(forwardListOfPairs);
  return 0;
}
Producción

Forward List : 
[ 77 88]
[ 55 66]
[ 33 44]
[ 11 22]

Ejemplo 2:

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print list
// contents
void print(forward_list<pair<int, string> >&
           forwardListOfPairs)
{
  cout << "Forward List : " << '\n';
   
  for (auto currentPair : forwardListOfPairs)
  {
    // Each element of the forward list is
    // a pair itself
    pair<int, string> currentpair = currentPair;
 
    cout << "[ ";
 
    // Printing pair elements
    cout << "First: " << currentPair.first <<
            " and " << "Second: " <<
            currentPair.second;
    cout << ']';
    cout << '\n';
  }
}
 
// Driver code
int main()
{
  // Declaring a forward list of pairs
  forward_list<pair<int, string> >
  forwardListOfPairs;
 
  // Declaring a pair
  pair<int, string> pair1;
 
  // Initializing the
  // pair
  pair1 = make_pair(1, "Geeks");
 
  // Push the pair at the back
  // in the forwardList
  forwardListOfPairs.push_front(pair1);
 
  // Declaring another pair
  pair<int, string> pair2;
 
  // Initializing the
  // pair
  pair2 = make_pair(2, "for");
 
  // Push the pair at the front
  // in the forward list
  forwardListOfPairs.push_front(pair2);
 
  // Declaring another pair
  pair<int, string> pair3;
 
  // Initializing the pair
  pair3 = make_pair(3, "Geeks");
 
  // Push the pair at the front
  // in the forwardList
  forwardListOfPairs.push_front(pair3);
 
  // Declaring another pair
  pair<int, string> pair4;
 
  // Initializing the pair
  pair4 = make_pair(4, "C++");
 
  // Push the pair at the front
  // in the forwardList
  forwardListOfPairs.push_front(pair4);
 
  // Calling print function
  print(forwardListOfPairs);
  return 0;
}
Producción

Forward List : 
[ First: 4 and Second: C++]
[ First: 3 and Second: Geeks]
[ First: 2 and Second: for]
[ First: 1 and Second: Geeks]

Lista de pares

A continuación se muestra la implementación de una lista de pares:

Ejemplo 1:

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print list
// contents
void print(list<pair<int, int> >&
           listOfPairs)
{
 
  cout << "List : " << '\n';
   
  for (auto currentPair : listOfPairs)
  {
    // Each element of the list is
    // a pair itself
    pair<int, int> currentpair = currentPair;
 
    cout << "[ ";
 
    // Printing pair elements
    cout << "First: " << currentPair.first <<
            " and " << "Second: " <<
            currentPair.second;
    cout << ']';
    cout << '\n';
  }
}
 
// Driver code
int main()
{
  // Declaring a list of pairs
  list<pair<int, int> > listOfPairs;
 
  // Declaring a pair
  pair<int, int> pair1;
 
  // Initializing the
  // pair
  pair1 = make_pair(11, 22);
 
  // Push the pair at the back
  // in the list
  listOfPairs.push_back(pair1);
 
  // Declaring another pair
  pair<int, int> pair2;
 
  // Initializing the
  // pair
  pair2 = make_pair(33, 44);
 
  // Push the pair at the back
  // in the list
  listOfPairs.push_back(pair2);
 
  // Declaring another pair
  pair<int, int> pair3;
 
  // Initializing the pair
  pair3 = make_pair(55, 66);
 
  // Push the pair at the front
  // in the list
  listOfPairs.push_front(pair3);
 
  // Declaring another pair
  pair<int, int> pair4;
 
  // Initializing the pair
  pair4 = make_pair(77, 88);
 
  // Push the pair at the back
  // in the list
  listOfPairs.push_back(pair4);
 
  // Calling print function
  print(listOfPairs);
  return 0;
}
Producción

List : 
[ First: 55 and Second: 66]
[ First: 11 and Second: 22]
[ First: 33 and Second: 44]
[ First: 77 and Second: 88]

Ejemplo 2:

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print list
// contents
void print(list<pair<int, string> >&
           listOfPairs)
{
 
  cout << "List : " << '\n';
  for (auto currentPair : listOfPairs)
  {
    // Each element of the forwardList is
    // a pair itself
    pair<int, string> currentpair = currentPair;
 
    cout << "[ ";
 
    // Printing pair contents
    cout << "First: " << currentPair.first <<
            " and " << "Second: " <<
            currentPair.second;
    cout << ']';
    cout << '\n';
  }
}
 
// Driver code
int main()
{
  // Declaring a list of pairs
  list<pair<int, string> > listOfPairs;
 
  // Declaring a pair
  pair<int, string> pair1;
 
  // Initializing the
  // pair
  pair1 = make_pair(1, "Geeks");
 
  // Push the pair at the back
  // in the list
  listOfPairs.push_front(pair1);
 
  // Declaring another pair
  pair<int, string> pair2;
 
  // Initializing the
  // pair
  pair2 = make_pair(2, "for");
 
  // Push the pair at the front
  // in the list
  listOfPairs.push_front(pair2);
 
  // Declaring another pair
  pair<int, string> pair3;
 
  // Initializing the pair
  pair3 = make_pair(3, "Geeks");
 
  // Push the pair at the front
  // in the list
  listOfPairs.push_front(pair3);
 
  // Declaring another pair
  pair<int, string> pair4;
 
  // Initializing the pair
  pair4 = make_pair(4, "C++");
 
  // Push the pair at the front
  // in the list
  listOfPairs.push_front(pair4);
 
  // Calling print function
  print(listOfPairs);
  return 0;
}
Producción

List : 
[ First: 4 and Second: C++]
[ First: 3 and Second: Geeks]
[ First: 2 and Second: for]
[ First: 1 and Second: Geeks]

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 *