Lesson 14 · 14 of 20

set, unordered_map and deque · C++

Choose the right C++ container: std::set for unique sorted values, std::unordered_map to count page visits and std::deque for a print queue.

C++ · set, unordered_map and deque in DMarlon Studio: the example's code and its output in the terminal

`std::set` stores unique values and keeps them sorted: six tags go in, but cpp and linux are repeated, so four remain, in alphabetical order. count("gui") is 1 if it is there and 0 if not (C++20 adds contains). Looking things up in a set is fast even with millions of elements.

`std::unordered_map` is a hash table: like std::map, it links keys to values, but it does not sort them, and in exchange its look-ups take almost constant time. ++visits[page] counts each page's visits: the square brackets create the key with a value of 0 if it is missing.

The order in which an unordered_map walks its elements depends on the implementation, so the program does not walk it: it asks for each page in a fixed order with `find`, which returns end() when the key is missing and, unlike the square brackets, does not add it. That is why /blog gives 0 without being created.

`std::deque` (*double-ended queue*) adds and removes quickly at both ends: push_back puts "photo.png" at the back and push_front lets "URGENT.pdf" jump the queue. The loop serves the print queue with front() and pop_front() until empty() is true.

Code · 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();    }}

Output · 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

Key points

std::set: unique, sorted values.
std::unordered_map: very fast look-ups, no order.
m[key] creates the key if missing; find does not.
Do not rely on an unordered_map's order: sort before printing.
std::deque: fast insertion and removal at the front and the back.

Exercise

Copy the visits into a std::vector<std::pair<std::string, int>>, sort it from most to fewest visits and print the page ranking.