STL Containers

The Standard Template Library (STL) is the part of the C++ standard library that provides ready-made containers and algorithms. A container is an object that stores a collection of other objects and manages their memory for you. You already know std::vector and std::array. In this lesson you will meet the other containers you will use most often, and learn how to choose between them.

Every container is a class template, so you write the item type in angle brackets: std::map<std::string, int>, std::set<int>.

The main containers at a glance

If you are not sure, start with std::vector. Change only when you need lookup by key, uniqueness, or fast insertion at the front.

std::deque: a double-ended queue

A deque (pronounced "deck") supports fast insertion and removal at both the front and the back.

#include <deque>
#include <print>
#include <string>

int main() {
    std::deque<std::string> counter = {"Aarav", "Isha"};
    counter.push_back("Rohan");             // joins at the back
    counter.push_front("Meera (senior)");   // served first
    counter.pop_front();                    // Meera is served

    std::println("Next: {}, last: {}, waiting: {}", counter.front(), counter.back(), counter.size());
}

Next: Aarav, last: Rohan, waiting: 3

std::map: key-value pairs in sorted order

A map stores key-value pairs: each unique key (a student's name) maps to a value (their marks). It keeps the keys sorted, so looping over a map visits them in order.

#include <map>
#include <print>
#include <string>

int main() {
    std::map<std::string, int> marks;
    marks["Rohan"] = 78;
    marks["Ananya"] = 91;
    marks.insert({"Kabir", 66});
    marks["Rohan"] += 5;                       // update an existing value

    for (const auto& [name, score] : marks) {  // structured binding (C++17)
        std::println("{:<8}{}", name, score);
    }

    std::println("Has Isha? {}", marks.contains("Isha"));     // C++20
    if (auto it = marks.find("Kabir"); it != marks.end()) {
        std::println("Found {} with {}", it->first, it->second);
    }

    marks.erase("Kabir");
    std::println("Students left: {}", marks.size());
}

Ananya  91
Kabir   66
Rohan   83
Has Isha? false
Found Kabir with 66
Students left: 2

Each element of a map is a std::pair with members first (the key) and second (the value). The structured binding const auto& [name, score] unpacks the pair into two readable names. find returns an iterator (a position) to the element, or end() when the key is missing.

std::unordered_map: fast lookup without order

An unordered_map stores pairs in a hash table. Lookup, insertion and removal take constant time on average, usually faster than map, but the elements are in no particular order, and the order can change between compilers or runs. Use it when you need speed and do not need sorted output.

#include <print>
#include <string>
#include <unordered_map>
#include <vector>

int main() {
    std::vector<std::string> orders = {"tea", "coffee", "tea", "lassi", "tea", "coffee"};

    std::unordered_map<std::string, int> count;
    for (const auto& drink : orders) {
        ++count[drink];                       // missing keys start at 0
    }

    std::println("tea: {}, coffee: {}, lassi: {}", count["tea"], count["coffee"], count["lassi"]);
    std::println("Different drinks: {}", count.size());
    std::println("Anyone for juice? {}", count.contains("juice"));
}

tea: 3, coffee: 2, lassi: 1
Different drinks: 3
Anyone for juice? false

This program looks up specific keys instead of looping over the whole map, because looping would print the drinks in an unpredictable order.

std::set: unique, sorted values

A set stores each value at most once, in sorted order. Inserting a value that is already present does nothing.

#include <print>
#include <set>

int main() {
    std::set<int> rolls = {12, 5, 31, 5, 8};   // the second 5 is ignored
    rolls.insert(20);

    auto [position, added] = rolls.insert(12);
    std::println("12 added again? {}", added);

    for (int r : rolls) {
        std::print("{} ", r);
    }
    std::println("");
    std::println("Smallest: {}, largest: {}", *rolls.begin(), *rolls.rbegin());
}

12 added again? false
5 8 12 20 31
Smallest: 5, largest: 31

insert returns a pair: an iterator to the element and a bool saying whether it was newly added. begin() points at the smallest value and rbegin() (reverse begin) at the largest; the * reads the value at that position.

Stack, queue and priority_queue

These container adapters wrap another container and allow only certain operations, which makes your intent clear.

#include <print>
#include <queue>
#include <stack>
#include <string>

int main() {
    std::stack<std::string> browser_history;      // last in, first out
    browser_history.push("home");
    browser_history.push("results");
    browser_history.push("admit-card");
    browser_history.pop();                         // back button
    std::println("Back to: {}", browser_history.top());

    std::queue<int> tokens;                        // first in, first out
    tokens.push(101);
    tokens.push(102);
    std::println("Now serving token {}", tokens.front());

    std::priority_queue<int> urgency;              // largest on top
    urgency.push(3);
    urgency.push(9);
    urgency.push(5);
    std::println("Most urgent: {}", urgency.top());
}

Back to: results
Now serving token 101
Most urgent: 9

Common mistakes

• Using [] just to check a key. It inserts the key. Use contains or find.
• Depending on unordered_map order. The order is unspecified; sort the keys or use std::map if order matters.
• Choosing std::list for speed. Linked lists are slow in practice because their items are scattered in memory; std::vector is usually faster even for inserts in the middle of small lists.
• Changing a key in place. Keys in maps and sets are const; remove the element and insert a new one.

Key points

• std::vector is the default; std::deque adds fast insertion at the front.
• std::map keeps key-value pairs sorted by key; std::unordered_map is usually faster but unordered.
• std::set and std::unordered_set store unique values.
• Use contains (C++20) or find to look up keys; [] inserts missing keys.
• Structured bindings auto& [key, value] make map loops readable.
• std::stack, std::queue and std::priority_queue restrict a container to LIFO, FIFO or largest-first access.

#include <map>
#include <print>
#include <set>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> borrowed = {"Wings of Fire", "Godan", "Wings of Fire",
                                         "Gitanjali", "Godan", "Wings of Fire"};

    std::map<std::string, int> count;
    for (const auto& title : borrowed) {
        ++count[title];
    }
    for (const auto& [title, times] : count) {
        std::println("{:<15}{}", title, times);
    }

    std::set<std::string> distinct(borrowed.begin(), borrowed.end());
    std::println("Different titles: {}", distinct.size());
}

Gitanjali      1
Godan          2
Wings of Fire  3
Different titles: 3