I102 - Paradigmas de Programación
3.5
Prof. Mariano Scaramal
Ingeniería en Inteligencia Artificial
Contenedores Secuenciales
• Tamaño fijo, con datos almacenados en forma secuencial, no utiliza memoria dinámica.
array<T, n> a 1 2 3 4 … n
• Array de tamaño dinámico con datos almacenados en forma secuencial.
vector<T> v 1 2 3 4 5 6
• Array de tamaño dinámico con datos almacenados en forma secuencial.
deque<T> d 1 2 3 4 5 6
• Lista simplemente enlazada.
foward_list<T> fl 1 2 3 4 5 6 end
• Lista doblemente enlazada.
list<T> l 1 2 3 4 5 6 end
2
Array (std::array)
Este container funciona en forma
#include <iostream>
similar al array ya conocido de C. #include <array> // Se necesita incluir array
Al igual que en C, std::array int main() {
std::array<int, 5> arr = {3, 2, 6, 1, 5};
requiere un tamaño fijo. // Acceder valores como un array de C y con .at()
std::cout << "El primer valor es: " << arr[0] << std::endl;
Debido a esto, no se aloca std::cout << "El cuarto valor es: " << arr.at(3) << std::endl;
memoria en tiempo de ejecución. // Utilizar el for por rango
std::cout << "Los elementos de arr son: ";
Si bien en el array de C también for (const int n : arr)
std::cout << n << " ";
se pueden almacenar objetos, std::cout << std::endl;
std::array tiene funcionalidades
return 0;
útiles para el manejo de objetos. }
3
Vector (std::vector)
Este container encapsula un array de tamaño dinámico.
Debido a su versatilidad, suele utilizarse más frecuentemente que los arrays
además de poseer varios métodos interesantes como ser insert, erase, clear,
reverse, empty, capacity, at, etc.
int main() {
vector<int> vec1 {1, 2, 3};
#include <iostream> vector<int> vec2 (4, 9);
#include <string> // Imprime los vectores
#include <vector> // Se necesita incluir vector printVec(vec1, "vec1"); printVec(vec2, "vec2");
// Uso de push_back y pop_back
using namespace std; vec1.push_back(4); vec2.pop_back();
// Uso de size(), front() y back()
void printVec(vector<int> v, string name){ cout << "Vec1 tiene un size de " << vec1.size() << endl;
cout << name + " es: "; cout << "Vec1 comienza con " << vec1.front() << endl;
for (const int n : v) cout << "Vec1 termina con " << vec1.back() << endl;
cout << n << " "; // Imprime nuevamente con las modificaciones
cout << endl; printVec(vec1, "vec1"); printVec(vec2, "vec2");
}
return 0;
4
}
Cola Doblemente Terminada (std::dequeu)
Es una cola donde se puede agregar y sacar información del frente o el final.
Al igual que vector, también tiene los métodos front, back, at, begin, size, empty,
insert y erase (no tiene capacity), y más.
int main() {
deque<int> Dq;
// Agregar elementos al frente y al final
#include <iostream> Dq.push_back(3); // Agrega al final
#include <deque> // Necesario para deque Dq.push_back(8); // Agrega al final
using namespace std; Dq.push_front(5); // Agrega al frente
Dq.push_front(1); // Agrega al frente
void printDeq(deque<int> d, string name){ // Se imprime con los datos agregados
cout << name + " es: "; printDeq(Dq, "Dq");
for (const int n : d) // Se remueve información
cout << n << " "; Dq.pop_front(); // Remueve el primer elemento
cout << endl; Dq.pop_back(); // Remueve el último elemento
} // Se imprime luego de las modificaciones
printDeq(Dq, "Dq");
return 0;
} 5
Listas (std::forward_list y std::list)
Implementan una lista simplemente enlazada (forward_list) y una lista
doblemente enlazada (list). No se provee acceso aleatorio en ningún caso.
Tienen algunos métodos similares a vector y los propios según la lista.
int main() {
Ejemplo con forward_list forward_list<int> myList = {5, 8, 3, 4, 1, 6};
// Imprimir lista
include <iostream>
printFL(myList, "myList");
#include <forward_list> // Para usar forward_list
myList.push_front(0); // Insertar al frente
using namespace std;
myList.push_front(9); // Insertar al frente
myList.remove(3); // Remover todos los 3
void printFL(forward_list<int> fl, string name){
// Imprimir luego de las modificaciones
cout << name + " es: ";
printFL(myList, "myList");
for (const int n : fl)
myList.reverse(); // Invertir la lista
cout << n << " ";
// Imprimir lista invertida
cout << endl;
printFL(myList, "myList");
}
return 0;
} 6
Pilas y Colas
Las pilas y colas son implementadas con #include <iostream>
#include <stack>
las librerías stack y queue, #include <queue>
respectivamente. #include <vector>
#include <list>
En las pilas, se tienen los métodos push y int main() {
pop, propios de este modelo. Nótese que std::vector<int> vec = {1, 2, 3};
std::list<int> lst = {10, 20, 30};
se utiliza el modelo LIFO para este caso.
std::stack<int, std::vector<int>> st(vec);
En las colas, también se tienen los std::stack<int, std::list<int>> st2(lst);
métodos push y pop que funcionan con el std::queue<int, std::vector<int>> q(vec);
std::queue<int, std::list<int>> q2(lst);
modelo FIFO, típico de una cola.
std::cout << st.top() << std::endl; // Imprime 3
Las pilas y las colas se pueden inicializar std::cout << st2.top() << std::endl; // Imprime 30
con push, con un vector o con una lista. std::cout << q.front() << std::endl; // Imprime 1
std::cout << q2.front() << std::endl; // Imprime 10
return 0;
} 7
Set y Multiset
El set es un conjunto de elementos que no #include <iostream>
#include <set>
puede tener repetidos. Por otro lado, el #include <string>
multiset es un conjunto de elementos que
using namespace std;
pueden ser repetidos.
int main() {
Ambos containers mantienen los elementos set<int> setDes = {5, 2, 8, 3, 10};
multiset<int, greater<int>> setAsc = {3, 5, 9, 21, 5};
ordenados. De usar valores numéricos el // Imprime 2 3 5 8 10
default es en orden ascendente. cout << "setDes es: ";
for (const auto& val : setDes)
cout << val << " ";
cout << std::endl;
// Imprime 21 9 5 5 3
cout << "setAsc es: ";
for (const auto& val : setAsc)
cout << val << " ";
cout << std::endl;
return 0;
} 8
Map y Multimap
El map asocia un key con un value. #include <iostream>
Similarmente a set, no permite #include <map>
using namespace std;
duplicados.
int main() {
Por otro lado, un multimap tiene map<std::string, int> m;
permite duplicados. // Producto y precio por kg
m["manzana"] = 5;
También se hizo uso de un modelo m["banana"] = 2;
// Para insertar un elemento se puede hacer con un pair
pair. El elemento std::pair es de la m.insert(std::make_pair("sandía", 1));
librería <utility> y simplemente crear // Para recorrerlo
for (const auto& pair : m)
una asociación de par entre dos cout << pair.first << ": " << pair.second << endl;
datos. // También se pueden acceder los precios
cout << "El precio de la banana es: " << m["banana"] << endl;
// Borrar un elemento
m.erase("banana");
return 0;
}
9
Preguntas?
10
