Lección 14 · 14 de 20

set, unordered_map y deque · C++

Elija el contenedor de C++ adecuado: std::set para valores únicos ordenados, std::unordered_map para contar visitas y std::deque para una cola.

C++ · set, unordered_map y deque en DMarlon Studio: el código del ejemplo y su salida en la terminal

`std::set` guarda valores únicos y siempre ordenados: se insertan seis etiquetas, pero cpp y linux están repetidas y quedan cuatro, en orden alfabético. count("gui") vale 1 si está y 0 si no (C++20 añade contains). Buscar en un set es rápido incluso con millones de elementos.

`std::unordered_map` es una tabla hash: como std::map, relaciona claves y valores, pero no las ordena, y a cambio busca en un tiempo casi constante. ++visits[page] cuenta las visitas de cada página: los corchetes crean la clave con valor 0 si no existe.

El orden en que un unordered_map recorre sus elementos depende de la implementación, así que el programa no lo recorre: pregunta por cada página en un orden fijo con `find`, que devuelve end() si la clave no está y, a diferencia de los corchetes, no la añade. Por eso /blog da 0 sin crearse.

`std::deque` (*double-ended queue*) añade y quita rápido por los dos extremos: push_back pone «photo.png» al final y push_front cuela «URGENT.pdf» al principio. El bucle atiende la cola de impresión con front() y pop_front() hasta que empty() es verdadero.

Código · main.cpp

#include <deque>#include <iostream>#include <set>#include <string>#include <unordered_map>int main() {    // std::set: unique values, always kept in order.    std::set<std::string> tags;    for (const char* t : {"cpp", "linux", "fltk", "cpp", "gui", "linux"}) tags.insert(t);    std::cout << tags.size() << " tags:";    for (const auto& t : tags) std::cout << " " << t;    std::cout << "\nHas 'gui'? " << (tags.count("gui") ? "yes" : "no") << "\n";    // std::unordered_map: a hash table. Fast look-ups, but no order.    std::unordered_map<std::string, int> visits;    for (const char* page : {"/home", "/download", "/home", "/courses", "/home", "/download"})        ++visits[page];                                   // a missing key starts at 0    for (const char* page : {"/home", "/download", "/courses", "/blog"}) {        auto it = visits.find(page);                      // find does not add keys        std::cout << page << ": " << (it != visits.end() ? it->second : 0) << "\n";    }    // std::deque: fast to add and remove at both ends.    std::deque<std::string> jobs = {"invoice.pdf", "report.pdf"};    jobs.push_back("photo.png");    jobs.push_front("URGENT.pdf");                        // jumps the queue    while (!jobs.empty()) {        std::cout << "Printing " << jobs.front() << "\n";        jobs.pop_front();    }}

Salida · c++ -std=c++17 main.cpp -o main && ./main

4 tags: cpp fltk gui linux
Has 'gui'? yes
/home: 3
/download: 2
/courses: 1
/blog: 0
Printing URGENT.pdf
Printing invoice.pdf
Printing report.pdf
Printing photo.png

Para recordar

std::set: valores únicos y ordenados.
std::unordered_map: búsquedas muy rápidas, sin orden.
m[clave] crea la clave si no existe; find no.
No dependa del orden de un unordered_map: ordene antes de escribir.
std::deque: inserción y borrado rápidos por delante y por detrás.

Ejercicio

Copie las visitas a un std::vector<std::pair<std::string, int>>, ordénelo de más a menos visitas y escriba la clasificación de páginas.