Contenedores de la STL

Parte de la sección Programación Orientada a Objetos del Journey de C++ de Coddy — lección 71 de 104.

Los contenedores de la STL son clases de plantilla que almacenan y organizan colecciones de objetos. Cada tipo de contenedor está optimizado para diferentes patrones de acceso y operaciones. Elegir el contenedor adecuado para sus necesidades puede afectar significativamente el rendimiento de su programa.

Los contenedores de secuencia mantienen los elementos en un orden específico:

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // Array dinámico, acceso aleatorio rápido
vec.push_back(4);                   // Añadir al final: O(1) amortizado
int x = vec[2];                     // Acceso por índice: O(1)

std::list<int> lst = {1, 2, 3};    // Lista doblemente enlazada
lst.push_front(0);                  // Añadir al principio: O(1)
lst.push_back(4);                   // Añadir al final: O(1)

Los contenedores asociativos almacenan elementos en orden para una búsqueda rápida:

#include <map>
#include <set>

std::set<int> s = {3, 1, 4, 1};    // Elementos únicos ordenados: {1, 3, 4}
s.insert(2);                        // Insertar: O(log n)
bool found = s.count(3);            // Comprobar existencia: O(log n)

std::map<std::string, int> ages;   // Pares clave-valor, ordenados por clave
ages["Alice"] = 25;                 // Insertar/actualizar: O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // Acceso: O(log n)

Los contenedores no ordenados utilizan tablas hash para una búsqueda en el caso promedio aún más rápida:

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // Inserción: O(1) promedio
scores["player2"] = 200;
std::cout << scores["player1"];    // Acceso: O(1) promedio

Usa vector cuando necesites acceso aleatorio rápido, list para inserciones frecuentes en el medio, map/set cuando necesites datos ordenados, y unordered_map cuando la velocidad de búsqueda sea crítica y el orden no importe.

Desafío

Fácil

Vamos a construir un sistema de gestión de calificaciones de estudiantes que demuestre cómo los diferentes contenedores de la STL sirven para propósitos distintos. Utilizarás múltiples tipos de contenedores para organizar los datos de los estudiantes de manera eficiente, eligiendo el contenedor adecuado para cada tarea.

Crearás dos archivos para organizar tu código:

GradeManager.h: Define una clase GradeManager que utiliza múltiples contenedores de la STL para gestionar la información de los estudiantes.
Tu clase debe utilizar:
- Un std::vector<std::string> para almacenar los nombres de los estudiantes en el orden en que fueron añadidos
- Un std::map<std::string, int> para asociar cada nombre de estudiante con su calificación
- Un std::set<int> para rastrear todas las calificaciones únicas que han sido asignadas
Implementa estos métodos:
- addStudent(const std::string& name, int grade) — añade un estudiante con su calificación a los tres contenedores
- getGrade(const std::string& name) — devuelve la calificación para un nombre de estudiante dado utilizando el mapa
- printRoster() — imprime todos los nombres de los estudiantes en el orden en que fueron añadidos (desde el vector), cada uno en una línea nueva
- printGrades() — imprime todos los estudiantes con sus calificaciones en orden alfabético (el mapa maneja esto automáticamente), con el formato name: grade en cada línea
- printUniqueGrades() — imprime todas las calificaciones únicas en orden ascendente (el conjunto maneja esto), separadas por espacios seguidos de un salto de línea
main.cpp: Lee las entradas y demuestra cómo cada tipo de contenedor sirve para un propósito diferente.
Lee seis entradas (cada una en una línea separada):
1. Nombre del primer estudiante
2. Calificación del primer estudiante (entero)
3. Nombre del segundo estudiante
4. Calificación del segundo estudiante (entero)
5. Nombre del tercer estudiante
6. Calificación del tercer estudiante (entero)
Crea un GradeManager y añade a los tres estudiantes. Luego demuestra los diferentes comportamientos de los contenedores:
1. Imprime Roster (insertion order): seguido de la llamada a printRoster()
2. Imprime Grades (alphabetical): seguido de la llamada a printGrades()
3. Imprime Unique grades: seguido de la llamada a printUniqueGrades()
4. Busca la calificación del segundo estudiante e imprime <name>'s grade: <grade>

Por ejemplo, con las entradas Charlie, 85, Alice, 90, Bob, 85:

Roster (insertion order):
Charlie
Alice
Bob
Grades (alphabetical):
Alice: 90
Bob: 85
Charlie: 85
Unique grades:
85 90 
Alice's grade: 90

Observa cómo el vector preserva el orden de inserción (Charlie, Alice, Bob), el mapa ordena automáticamente por clave (Alice, Bob, Charlie), y el conjunto almacena solo valores únicos en orden ascendente (85 aparece una vez, no dos). ¡Cada tipo de contenedor destaca en diferentes tareas!

Hoja de referencia

Los contenedores de la STL son clases de plantilla para almacenar y organizar colecciones de objetos. Cada tipo está optimizado para diferentes operaciones.

Contenedores de Secuencia

Mantienen los elementos en un orden específico:

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // Dynamic array, fast random access
vec.push_back(4);                   // Add to end: O(1) amortized
int x = vec[2];                     // Access by index: O(1)

std::list<int> lst = {1, 2, 3};    // Doubly-linked list
lst.push_front(0);                  // Add to front: O(1)
lst.push_back(4);                   // Add to end: O(1)

Contenedores Asociativos

Almacenan elementos en orden clasificado para una búsqueda rápida:

#include <map>
#include <set>

std::set<int> s = {3, 1, 4, 1};    // Unique sorted elements: {1, 3, 4}
s.insert(2);                        // Insert: O(log n)
bool found = s.count(3);            // Check existence: O(log n)

std::map<std::string, int> ages;   // Key-value pairs, sorted by key
ages["Alice"] = 25;                 // Insert/update: O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // Access: O(log n)

Contenedores No Ordenados

Utilizan tablas hash para una búsqueda más rápida en el caso promedio:

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // Insert: O(1) average
scores["player2"] = 200;
std::cout << scores["player1"];    // Access: O(1) average

Elegir el Contenedor Adecuado

vector: Acceso aleatorio rápido
list: Inserciones frecuentes en el medio
map/set: Se necesitan datos ordenados
unordered_map: La velocidad de búsqueda es crítica, el orden no importa

Pruébalo tú mismo

#include <iostream>
#include <string>
#include "GradeManager.h"

using namespace std;

int main() {
    // Lee las entradas para tres estudiantes
    string name1, name2, name3;
    int grade1, grade2, grade3;
    
    cin >> name1;
    cin >> grade1;
    cin >> name2;
    cin >> grade2;
    cin >> name3;
    cin >> grade3;
    
    // TODO: Crea un objeto GradeManager
    
    // TODO: Agrega a los tres estudiantes al GradeManager
    
    // TODO: Imprime "Roster (insertion order):" y llama a printRoster()
    
    // TODO: Imprime "Grades (alphabetical):" y llama a printGrades()
    
    // TODO: Imprime "Unique grades:" y llama a printUniqueGrades()
    
    // TODO: Busca la calificación del segundo estudiante e imprime "<name>'s grade: <grade>"
    
    return 0;
}