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 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 tus necesidades puede afectar significativamente al rendimiento de tu 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 frente: O(1)
lst.push_back(4);                   // Añadir al final: O(1)

Los contenedores asociativos almacenan elementos en orden ordenado 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);            // Verificar 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 sin orden utilizan tablas hash para realizar búsquedas de caso promedio aún más rápidas:

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // Insertar: 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 fundamental y el orden no importe.

Desafío

Fácil

Construyamos un sistema de gestión de calificaciones de estudiantes que demuestre cómo los diferentes contenedores de STL sirven para distintos propósitos. Usarás varios 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 varios contenedores de 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 se añadieron
- Un std::map<std::string, int> para asociar el nombre de cada estudiante con su calificación
- Un std::set<int> para realizar un seguimiento de todas las calificaciones únicas que se han asignado
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 de un estudiante dado utilizando el mapa
- printRoster(): imprime todos los nombres de los estudiantes en el orden en que se añadieron (desde el vector), cada uno en una línea nueva
- printGrades(): imprime todos los estudiantes con sus calificaciones en orden alfabético (el mapa lo gestiona automáticamente), con el formato name: grade en cada línea
- printUniqueGrades(): imprime todas las calificaciones únicas en orden ascendente (el conjunto se encarga de esto), separadas por espacios y seguidas 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 los tres estudiantes. Después, demuestra los diferentes comportamientos de los contenedores:
1. Imprime Roster (insertion order): y después llama a printRoster()
2. Imprime Grades (alphabetical): y después llama a printGrades()
3. Imprime Unique grades: y después llama 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 conserva el orden de inserción (Charlie, Alice, Bob), el mapa ordena automáticamente por clave (Alice, Bob, Charlie) y el conjunto almacena únicamente valores únicos en orden ascendente (85 aparece una vez, no dos). ¡Cada tipo de contenedor destaca en tareas diferentes!

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: Añade los tres estudiantes al GradeManager
    
    // TODO: Print "Roster (insertion order):" and call printRoster()
    
    // TODO: Print "Grades (alphabetical):" and call printGrades()
    
    // TODO: Print "Unique grades:" and call printUniqueGrades()
    
    // TODO: Busca la calificación del segundo estudiante e imprime "<name>'s grade: <grade>"
    
    return 0;
}