Lección 4 de 8: contenedores y algoritmos en C++. La biblioteca estándar trae listas, diccionarios y conjuntos listos para usar, y más de cien algoritmos para ordenarlos, buscar en ellos o transformarlos. Usarlos bien ahorra cientos de líneas y muchos errores; usarlos mal, sobre todo con iteradores y referencias que se invalidan, produce algunos de los fallos más difíciles de encontrar. Esta lección enseña las dos cosas.
std::vector: el contenedor que usarás casi siempre
Un contenedor es un objeto que guarda otros objetos. El más usado, con diferencia, es std::vector: una lista de elementos del mismo tipo, seguidos en memoria, que crece sola. Es lo que en C sería un array con malloc y realloc, pero sin tener que liberar nada a mano:
#include <print>
#include <string>
#include <vector>
int main()
{
std::vector<int> notas{7, 9, 6};
notas.push_back(10); // añade al final
std::println("Hay {} notas; la primera es {} y la última, {}", notas.size(), notas.front(), notas.back());
int suma = 0;
for (int n : notas) { // recorrer con el for de rango
suma += n;
}
std::println("Media: {}", static_cast<double>(suma) / notas.size());
std::vector<std::string> nombres{"Ana", "Luis"};
nombres.insert(nombres.begin(), "Eva"); // al principio
nombres.pop_back(); // quita el último
std::println("{}", nombres); // C++23 imprime contenedores enteros
}salidaHay 4 notas; la primera es 7 y la última, 10 Media: 8 ["Eva", "Ana"]
Desde C++23, std::println sabe imprimir un vector entero, con corchetes y comas, y pone comillas a las cadenas. Para acceder a un elemento hay dos formas: notas[i], que no comprueba nada, y notas.at(i), que comprueba el índice y lanza una excepción si se sale:
#include <print>
#include <stdexcept>
#include <vector>
int main()
{
std::vector<int> notas{7, 9, 6};
try {
std::println("{}", notas.at(1));
std::println("{}", notas.at(5));
} catch (const std::out_of_range& e) {
std::println("Fuera de rango: {}", e.what());
}
}salida9 Fuera de rango: vector::_M_range_check: __n (which is 5) >= this->size() (which is 3)
El error que te ahorra: leer fuera de un vector con []
#include <print>
#include <vector>
int main()
{
std::vector<int> notas{7, 9, 6};
int total = 0;
for (std::size_t i = 0; i <= notas.size(); ++i) { // <= en vez de <
total += notas[i];
}
std::println("{}", total);
}salida con error==115==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x730d2f3e001c at pc 0x0000004028bb bp 0x7ffcd3a44b90 sp 0x7ffcd3a44b88
READ of size 4 at 0x730d2f3e001c thread T0
#0 0x0000004028ba in main /curso/fuera_rango.cpp:9
…
0x730d2f3e001c is located 0 bytes after 12-byte region [0x730d2f3e0010,0x730d2f3e001c)
allocated by thread T0 here:
…
#7 0x00000040273a in main /curso/fuera_rango.cpp:6
…
SUMMARY: AddressSanitizer: heap-buffer-overflow /curso/fuera_rango.cpp:9 in mainCompilado con optimización y sin sanitizador, el programa suma la basura que haya después del vector y escribe un número cualquiera sin quejarse. Con -fsanitize=address se detiene en la línea exacta: una lectura de 4 bytes (un int) justo al final de un bloque de 12 bytes, los tres int del vector. El <= en lugar de < es el error más repetido con los índices, en C y en C++.
-O1, -O2…), la biblioteca estándar de GCC ya comprueba los índices de [] por su cuenta y detiene el programa con un mensaje Assertion '__n < this->size()' failed. Es el modo endurecido que verás al final de la lección, que desde GCC 15 viene activado en las compilaciones de depuración. En las optimizadas, que son las que se publican, no está a menos que lo pidas.Tamaño y capacidad
Un vector distingue entre su tamaño (size(), cuántos elementos tiene) y su capacidad (capacity(), para cuántos tiene sitio reservado). Cuando se llena, reserva un bloque más grande, mueve allí los elementos y libera el viejo. Así crece en la biblioteca de GCC:
#include <print>
#include <vector>
int main()
{
std::vector<int> v;
std::size_t antes = v.capacity();
std::println("size {:2} capacity {:2}", v.size(), v.capacity());
for (int i = 0; i < 20; ++i) {
v.push_back(i);
if (v.capacity() != antes) {
std::println("size {:2} capacity {:2}", v.size(), v.capacity());
antes = v.capacity();
}
}
std::vector<int> w;
w.reserve(20); // si sabes cuántos habrá, resérvalos de una vez
std::println("con reserve: capacity {}", w.capacity());
}salidasize 0 capacity 0 size 1 capacity 1 size 2 capacity 2 size 3 capacity 4 size 5 capacity 8 size 9 capacity 16 size 17 capacity 32 con reserve: capacity 20
La capacidad se duplica: 1, 2, 4, 8, 16, 32. Gracias a eso, añadir al final es rápido en promedio, aunque de vez en cuando toque copiar todo. Si sabes de antemano cuántos elementos vas a meter, reserve evita esas copias. El esquema muestra lo que pasa en una de esas mudanzas, y por qué es importante para lo que viene después:
std::array: tamaño fijo, sin sorpresas
Si el número de elementos se conoce al compilar y no cambia, std::array es la versión moderna del array de C: vive donde se declara (en la pila, si es una variable local), no reserva memoria dinámica y, a diferencia del array de C, sabe su tamaño, se puede copiar y comparar, y no se convierte en puntero al pasarlo a una función:
#include <array>
#include <print>
int main()
{
std::array<int, 7> temperaturas{18, 21, 23, 22, 19, 17, 20};
std::println("{} días, el tercero a {} grados", temperaturas.size(), temperaturas[2]);
std::array<int, 7> copia = temperaturas; // se copia entero
copia[0] = 30;
std::println("¿Iguales? {}", copia == temperaturas);
int maxima = temperaturas[0];
for (int t : temperaturas) {
if (t > maxima) maxima = t;
}
std::println("Máxima: {}", maxima);
}salida7 días, el tercero a 23 grados ¿Iguales? false Máxima: 23
std::string a fondo
En la lección 2 vimos lo básico de std::string. Es un contenedor de caracteres, con casi todas las operaciones de vector y muchas propias para buscar, recortar y reemplazar:
#include <print>
#include <string>
int main()
{
std::string correo = "ana.lopez@ejemplo.com";
std::size_t arroba = correo.find('@');
if (arroba != std::string::npos) {
std::println("Usuario: {}", correo.substr(0, arroba));
std::println("Dominio: {}", correo.substr(arroba + 1));
}
std::println("¿Empieza por ana? {}", correo.starts_with("ana")); // C++20
std::println("¿Termina en .com? {}", correo.ends_with(".com")); // C++20
std::println("¿Contiene lopez? {}", correo.contains("lopez")); // C++23
std::string saludo = "Hola, mundo";
saludo.replace(saludo.find("mundo"), 5, "C++");
saludo += '!';
std::println("{}", saludo);
std::string pais = "España";
std::println("{} letras, pero size() dice {}", 6, pais.size());
}salidaUsuario: ana.lopez Dominio: ejemplo.com ¿Empieza por ana? true ¿Termina en .com? true ¿Contiene lopez? true Hola, C++! 6 letras, pero size() dice 7
find devuelve la posición o la constante std::string::npos si no encuentra nada; compararla siempre antes de usar el resultado evita sorpresas. Y ojo con la última línea: size() cuenta bytes, no letras. En UTF-8, la «ñ» ocupa dos, por eso «España» mide 7. Para la mayoría de las tareas da igual, pero no si recortas texto por posiciones: podrías partir una letra por la mitad.
Diccionarios y conjuntos: map, unordered_map y set
std::map guarda pares clave-valor ordenados por la clave; std::unordered_map hace lo mismo con una tabla hash, sin orden pero normalmente más rápido; std::set guarda valores sin repetir, ordenados. Contar palabras es el ejemplo clásico:
#include <map>
#include <print>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
int main()
{
std::vector<std::string> palabras{"sol", "mar", "sol", "luna", "mar", "sol"};
std::map<std::string, int> cuenta;
for (const auto& p : palabras) {
++cuenta[p]; // si la clave no existe, la crea con 0
}
for (const auto& [palabra, veces] : cuenta) { // ordenado por la clave
std::println("{:5} {}", palabra, veces);
}
if (auto it = cuenta.find("luna"); it != cuenta.end()) {
std::println("luna aparece {} vez", it->second);
}
std::println("¿Hay estrella? {}", cuenta.contains("estrella")); // C++20
std::unordered_map<std::string, std::string> capitales{{"Francia", "París"}, {"Perú", "Lima"}};
capitales["Chile"] = "Santiago";
std::println("{} capitales; la de Perú es {}", capitales.size(), capitales.at("Perú"));
std::set<std::string> distintas(palabras.begin(), palabras.end());
std::println("{}", distintas);
}salidaluna 1
mar 2
sol 3
luna aparece 1 vez
¿Hay estrella? false
3 capitales; la de Perú es Lima
{"luna", "mar", "sol"}La línea for (const auto& [palabra, veces] : cuenta) usa los structured bindings de C++17: cada elemento del map es un par, y así se le da nombre a sus dos partes. Para buscar sin modificar, usa find, contains o at, nunca []: con un map, cuenta["estrella"] no busca, inserta la clave con valor 0 si no existe. Es una de las rarezas de C++ que más errores provoca.
- ContenedorQué guardaBuscarCuándo usarlo
vectorelementos seguidos, en orden de inserciónlineal, o binaria si está ordenadopor omisión, casi siemprearrayun número fijo de elementoslinealtamaño conocido al compilarmap/setclaves ordenadas (árbol)logarítmicanecesitas recorrer en ordenunordered_map/unordered_setclaves sin orden (tabla hash)constante en promediosolo buscar, y rápidodequecomo vector, pero crece por los dos ladoslinealcolas en las que se añade delante y detrás
Iteradores
Los contenedores se recorren con iteradores: objetos que señalan un elemento, como un puntero. begin() señala el primero y end(), la posición siguiente al último, que no se puede leer. El for de rango usa iteradores por debajo, y casi todos los algoritmos de la biblioteca reciben un par de ellos:
#include <print>
#include <vector>
int main()
{
std::vector<int> v{3, 8, 1, 9, 4};
for (auto it = v.begin(); it != v.end(); ++it) {
*it *= 10; // * da acceso al elemento
}
std::println("{}", v);
// borrar los menores de 50 mientras se recorre: erase devuelve el siguiente válido
for (auto it = v.begin(); it != v.end(); ) {
if (*it < 50) it = v.erase(it);
else ++it;
}
std::println("{}", v);
// desde C++20 hay una forma más corta
std::vector<int> w{3, 8, 1, 9, 4};
std::size_t borrados = std::erase_if(w, [](int x) { return x < 5; });
std::println("{} borrados, quedan {}", borrados, w);
}salida[30, 80, 10, 90, 40] [80, 90] 3 borrados, quedan [8, 9]
Iteradores, referencias e invalidación
Aquí está la trampa más típica de los contenedores. Una referencia, un puntero o un iterador a un elemento de un vector son, en el fondo, direcciones de memoria. Si el vector se muda a otro bloque al crecer, como en el esquema de arriba, esas direcciones apuntan al bloque viejo, que ya se liberó. Se dice que quedan invalidados, y usarlos es comportamiento indefinido:
El error que te ahorra: usar una referencia invalidada
#include <print>
#include <string>
#include <vector>
int main()
{
std::vector<std::string> tareas{"comprar pan"};
const std::string& primera = tareas[0];
tareas.push_back("llamar al banco"); // sin sitio: el vector se muda
std::println("Primera tarea: {}", primera);
}salida con error==132==ERROR: AddressSanitizer: heap-use-after-free on address 0x7ac0f4de0040 at pc 0x000000410917 bp 0x7ffe76bfd790 sp 0x7ffe76bfd788
READ of size 8 at 0x7ac0f4de0040 thread T0
…
#9 0x000000404a30 in main /curso/invalidacion.cpp:11
…
0x7ac0f4de0040 is located 0 bytes inside of 32-byte region [0x7ac0f4de0040,0x7ac0f4de0060)
freed by thread T0 here:
…
#9 0x00000040493e in main /curso/invalidacion.cpp:10
…
previously allocated by thread T0 here:
…
#7 0x000000404861 in main /curso/invalidacion.cpp:7
…
SUMMARY: AddressSanitizer: heap-use-after-free /curso/invalidacion.cpp:11 in mainEl informe se lee de abajo arriba: el bloque se reservó al crear el vector (previously allocated), se liberó al hacer push_back (freed by) y se leyó después en la línea del println (heap-use-after-free). Sin sanitizador, este programa puede imprimir bien, imprimir basura o romperse, según la ejecución. La regla: no guardes referencias ni iteradores a un vector mientras le añades o quitas elementos; guarda el índice, o copia el valor.
Cada contenedor tiene sus reglas. En vector y string, insertar puede invalidarlo todo, y borrar invalida desde el punto borrado; en map, set y list, insertar no invalida nada y borrar solo invalida el elemento borrado. Por eso el bucle con erase de la sección anterior usa el iterador que devuelve erase y no el viejo.
Los algoritmos de la biblioteca estándar
El archivo <algorithm> trae más de cien algoritmos ya escritos y probados: ordenar, buscar, contar, copiar, quitar duplicados… Reciben un rango de iteradores y, a menudo, una lambda (la vimos en la lección 3) que dice qué hacer con cada elemento. Antes de escribir un bucle, merece la pena buscar si ya existe un algoritmo que lo hace:
#include <algorithm>
#include <numeric>
#include <print>
#include <string>
#include <vector>
struct Producto {
std::string nombre;
double precio;
};
int main()
{
std::vector<int> v{5, 3, 8, 1, 9, 3};
std::sort(v.begin(), v.end());
std::println("ordenado: {}", v);
auto pos = std::find(v.begin(), v.end(), 8);
std::println("el 8 está en la posición {}", pos - v.begin());
auto pares = std::count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
std::println("números pares: {}", pares);
int suma = std::accumulate(v.begin(), v.end(), 0);
std::println("suma {}, máximo {}", suma, *std::max_element(v.begin(), v.end()));
v.erase(std::unique(v.begin(), v.end()), v.end()); // quitar repetidos (ya ordenado)
std::println("sin repetidos: {}", v);
std::vector<Producto> carrito{{"café", 4.5}, {"pan", 1.2}, {"queso", 7.9}};
std::sort(carrito.begin(), carrito.end(),
[](const Producto& a, const Producto& b) { return a.precio > b.precio; });
for (const auto& p : carrito) {
std::println("{:6} {:5.2f}", p.nombre, p.precio);
}
}salidaordenado: [1, 3, 3, 5, 8, 9] el 8 está en la posición 4 números pares: 1 suma 29, máximo 9 sin repetidos: [1, 3, 5, 8, 9] queso 7.90 café 4.50 pan 1.20
Fíjate en el truco de unique: no borra nada, solo junta los valores únicos al principio y devuelve dónde acaban; el erase quita el resto. Es un clásico de C++ y conviene reconocerlo.
Ranges: lo mismo, más corto (C++20 y C++23)
Pasar siempre v.begin(), v.end() es repetitivo y propenso a errores, como mezclar el begin de un vector con el end de otro. Desde C++20, casi todos los algoritmos tienen una versión en std::ranges que recibe el contenedor entero. Y las vistas (std::views) permiten encadenar filtros y transformaciones con |, sin copiar nada hasta el final:
#include <algorithm>
#include <print>
#include <ranges>
#include <string>
#include <vector>
int main()
{
std::vector<int> v{5, 3, 8, 1, 9, 4};
std::ranges::sort(v);
std::println("{}", v);
std::println("¿Hay un 9? {}", std::ranges::contains(v, 9)); // C++23
// los cuadrados de los pares, como vista: no se calcula nada hasta recorrerla
auto cuadrados = v | std::views::filter([](int x) { return x % 2 == 0; })
| std::views::transform([](int x) { return x * x; });
std::println("{}", cuadrados);
// y en C++23, ranges::to lo convierte en un contenedor de verdad
auto lista = cuadrados | std::ranges::to<std::vector>();
std::println("vector de {} elementos", lista.size());
std::vector<std::string> nombres{"Eva", "Luis", "Ana"};
for (auto [i, n] : std::views::enumerate(nombres)) { // C++23
std::println("{}. {}", i + 1, n);
}
}salida[1, 3, 4, 5, 8, 9] ¿Hay un 9? true [16, 64] vector de 2 elementos 1. Eva 2. Luis 3. Ana
std::ranges::to, std::ranges::contains y std::views::enumerate son de C++23: con GCC 15 funcionan, pero con compiladores de hace dos o tres años no. Si tu proyecto usa C++20, el resto del ejemplo sirve igual.
std::span: una vista de datos ajenos
¿Cómo se escribe una función que sume los elementos de un vector, de un array o de un array de C, sin escribirla tres veces? Con std::span (C++20): un puntero y un tamaño empaquetados juntos, que no son dueños de los datos, solo los miran. Sustituye a la pareja de puntero y longitud de C, con la que es tan fácil equivocarse:
#include <array>
#include <print>
#include <span>
#include <vector>
double media(std::span<const int> datos)
{
if (datos.empty()) return 0.0;
int suma = 0;
for (int x : datos) suma += x;
return static_cast<double>(suma) / datos.size();
}
int main()
{
std::vector<int> v{4, 8, 6};
std::array<int, 4> a{1, 2, 3, 4};
int c[] = {10, 20};
std::println("{} {} {}", media(v), media(a), media(c));
std::println("solo los dos primeros de v: {}", media(std::span(v).first(2)));
}salida6 2.5 15 solo los dos primeros de v: 6
Como no es dueño de los datos, un span no debe vivir más que el contenedor que mira: es la misma idea que las referencias y los iteradores, y el mismo peligro. Úsalo sobre todo como parámetro de funciones, que es donde brilla.
Ojo con la seguridad: los índices sin comprobar
Los [] de vector, array, string y span no comprueban el índice, como en C: un índice que viene del usuario y no se valida es un desbordamiento de búfer. Hay tres defensas. La primera, validar el índice o usar at() cuando venga de fuera. La segunda, preferir el for de rango y los algoritmos, que no usan índices. Y la tercera, compilar con el modo endurecido de la biblioteca de GCC, -D_GLIBCXX_ASSERTIONS, que añade la comprobación a [] y detiene el programa en lugar de dejarlo leer fuera. GCC 15 lo activa solo en las compilaciones sin optimizar; para las de producción hay que pedirlo:
#include <print>
#include <vector>
int main()
{
std::vector<int> precios{100, 250, 75};
std::size_t indice = 7; // imagina que viene de una petición
std::println("{}", precios[indice]);
}salida con error/usr/local/include/c++/15.3.0/bits/stl_vector.h:1263: constexpr std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::reference std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::operator[](size_type) [with _Tp = int; _Alloc = std::allocator<int>; reference = int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.
Compilado con -O2 -D_GLIBCXX_ASSERTIONS, como se compilaría para producción, el programa se detiene en el [] en lugar de leer memoria ajena. Las distribuciones de Linux ya compilan muchos de sus paquetes con esta opción, y GCC 14 añadió -fhardened, que la activa junto con otras protecciones. Cuesta muy poco rendimiento y convierte un fallo de seguridad silencioso en una parada controlada.
Retos
Reto 1. Escribe una función que reciba un std::vector<int> y lo deje ordenado y sin repetidos, usando algoritmos de la biblioteca y no bucles.
Ver la solución
#include <algorithm>
#include <print>
#include <vector>
void ordenar_sin_repetidos(std::vector<int>& v)
{
std::ranges::sort(v);
auto repetidos = std::ranges::unique(v);
v.erase(repetidos.begin(), repetidos.end());
}
int main()
{
std::vector<int> v{4, 1, 4, 2, 9, 1, 2};
ordenar_sin_repetidos(v);
std::println("{}", v);
}salida[1, 2, 4, 9]
La versión de std::ranges de unique devuelve directamente el trozo sobrante, que se pasa a erase. Con std::sort y std::unique clásicos queda igual, como en la sección de algoritmos.
Reto 2. ¿Qué escribe este programa? std::map<std::string, int> m{ {"a", 1} }; if (m["b"] == 0) std::println("cero"); std::println("{}", m.size());
Ver la solución
#include <map>
#include <print>
#include <string>
int main()
{
std::map<std::string, int> m{{"a", 1}};
if (m["b"] == 0) std::println("cero");
std::println("{}", m.size());
}salidacero 2
Escribe «cero» y después 2: al consultar m["b"], el map inserta la clave "b" con valor 0. Para preguntar si existe sin crearla, usa m.contains("b").
Reto 3. Con vistas de std::views, imprime en mayúsculas las palabras de más de tres letras de {"sol", "montaña", "río", "bosque"}.
Ver la solución
#include <cctype>
#include <print>
#include <ranges>
#include <string>
#include <vector>
int main()
{
std::vector<std::string> palabras{"sol", "montaña", "río", "bosque"};
auto mayusculas = [](std::string p) {
for (char& c : p) c = static_cast<char>(std::toupper(static_cast<unsigned char>(c)));
return p;
};
for (const auto& p : palabras | std::views::filter([](const std::string& p) { return p.size() > 3; })
| std::views::transform(mayusculas)) {
std::println("{}", p);
}
}salidaMONTAñA RíO BOSQUE
Dos sorpresas, las dos por UTF-8. «río» pasa el filtro aunque tiene tres letras, porque size() cuenta bytes y la «í» ocupa dos. Y salen «MONTAñA» y «RíO»: toupper trabaja byte a byte y no sabe qué hacer con los dos bytes de la «ñ» o de la «í». Contar letras de verdad y pasarlas a mayúsculas pide una biblioteca de Unicode, como ICU; para texto en inglés o identificadores, este método basta.
Todo el código de esta lección se compiló con GCC 15.3 (C++23, -std=c++23 -Wall -Wextra) y se ejecutó en un contenedor limpio antes de publicarla; los avisos del compilador y las salidas están copiados de esa ejecución. ¿Algo no te compila? Revisa tu versión con g++ --version: hace falta GCC 14 o más nuevo (o Clang 19 con libstdc++ 14) para std::print y el resto de C++23.