STL Containers

Choosing the Right Container

The Standard Template Library gives you a set of containers that are already written, already tested and already fast. Learning them well is one of the highest-return things you can do in C++, both for real work and for interviews, where "which container would you use" is a question that reveals a lot about how much C++ someone has actually written.

The containers differ in how they store elements, and that single choice determines which operations are cheap. A std::vector keeps everything contiguously, so indexing is instant and inserting in the middle is expensive. A std::map keeps keys ordered in a balanced tree, so lookup is logarithmic and iteration comes out sorted. A std::unordered_map hashes keys into buckets, so lookup is typically constant time but iteration order is meaningless.

The practical way to choose is to ask what your code does most often. If you mostly append and read by position, std::vector. If you look things up by a key, a map — ordered if you need sorted iteration or range queries, unordered if you just want the fastest lookup. If you only need to know whether something is present, a set. If you need first-in-first-out or last-in-first-out behaviour, use the adapters rather than building it yourself.

One piece of advice that is more useful than it sounds: start with std::vector unless you have a specific reason not to. Its contiguous layout is extraordinarily friendly to modern processor caches, and it routinely beats theoretically better containers on real data of realistic size. std::list has O(1) insertion in the middle and is still usually slower in practice, because every node is a separate allocation somewhere else in memory.

• std::vector — dynamic array. Index O(1), append amortised O(1), middle insert O(n). The default choice.
• std::deque — double-ended queue. O(1) push at both ends, index O(1); not contiguous.
• std::list — doubly linked list. O(1) insert/erase given an iterator, no indexing, poor cache behaviour.
• std::map — sorted key-value store. Lookup, insert and erase all O(log n); iterates in key order.
• std::unordered_map — hash table. Average O(1) lookup, worst case O(n); no useful iteration order.
• std::set / std::unordered_set — the same two structures storing only keys, for membership tests.
• std::stack, std::queue, std::priority_queue — adapters that restrict an underlying container to one access pattern.

std::vector: Size, Capacity and Reallocation

A vector holds two different numbers and confusing them causes real bugs. size() is how many elements you have put in. capacity() is how many it could hold before it needs a bigger buffer. Capacity is always at least size, and usually more.

When you push_back and size has reached capacity, the vector allocates a new, larger buffer — typically double the size — moves or copies every existing element into it, and frees the old one. That one push is O(n). Because the capacity doubles, this happens increasingly rarely, and the average cost per push works out to a constant. That is what "amortised O(1)" means, and it is why push_back is cheap despite occasionally doing a lot of work.

If you know roughly how many elements are coming, call reserve(n) first. It allocates capacity once, up front, and every subsequent push_back up to that count avoids reallocation entirely. On a loop pushing a lakh of elements this is a measurable win, and on a vector of strings or other objects with expensive moves it can be a large one.

Now the consequence you must remember: reallocation invalidates every iterator, pointer and reference into the vector. The old buffer is freed, so anything referring to it dangles. This is the same trap as the dangling reference from the references lesson, and it is why you must not hold on to &v[0] or an iterator across a push_back. Note that reserve does not remove the danger; it only postpones it until you exceed the reserved capacity.

Two smaller points. resize(n) changes size, creating or destroying elements; reserve(n) changes only capacity and creates nothing — mixing them up produces a vector full of unexpected zeroes. And clear() sets size to zero but leaves capacity alone, so the memory is still held; if you genuinely want it back, shrink_to_fit() asks for it, though the standard permits an implementation to ignore the request.

#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<int> v;
    std::cout << v.size() << ' ' << v.capacity() << '\n';    // 0 0

    for (int i = 0; i < 10; ++i) v.push_back(i);
    std::cout << v.size() << ' ' << v.capacity() << '\n';    // 10, >= 10

    // Reserve when the count is known: one allocation instead of several
    std::vector<std::string> names;
    names.reserve(1000);
    for (int i = 0; i < 1000; ++i) names.push_back("student" + std::to_string(i));

    // INVALIDATION: this reference may dangle after a growth
    std::vector<int> marks = {72, 65, 91};
    int& first = marks[0];
    marks.push_back(48);          // may reallocate
    // std::cout << first;        // possibly dangling — do not do this

    // resize vs reserve
    std::vector<int> a;
    a.reserve(5);
    std::cout << a.size() << '\n';    // 0 — no elements exist yet
    std::vector<int> b;
    b.resize(5);
    std::cout << b.size() << ' ' << b[0] << '\n';   // 5 0 — five zeroes exist

    a.clear();
    std::cout << a.size() << '\n';    // 0, but capacity is still 5
}

map and unordered_map, and the operator[] Trap

A map stores key-value pairs and lets you look a value up by its key. std::map keeps the keys sorted and gives O(log n) for lookup, insertion and erasure; std::unordered_map hashes the keys and gives average O(1) for the same operations, with a worst case of O(n) when many keys collide.

Choose std::unordered_map when you only ever look things up — a word-frequency count, a cache, an index by ID. Choose std::map when you need the entries in sorted order, or need range queries such as "every roll number between 100 and 200", or when the key type has no hash function readily available. For small maps the difference is negligible, so readability wins.

Now the trap, and it is one of the most consequential in the whole standard library. map[key] inserts the key if it is not already there, with a value-initialised value — zero for numbers, an empty string for strings. This is convenient for counting, where ++counts[word] correctly starts a new word at 1. It is a disaster when you are merely checking, because if (ages["Meera"] > 18) silently adds Meera to the map with age 0, and your map quietly fills up with entries nobody ever inserted.

The consequence people meet first is a compile error rather than a bug: because operator[] can modify the map, it does not exist on a const map. A function taking const std::map& cannot use [] at all, and the error message is not obvious about why.

The safe alternatives are all short. at(key) reads without inserting and throws std::out_of_range if the key is absent. count(key) returns 0 or 1. find(key) returns an iterator, equal to end() when the key is missing, and is the right choice when you want the value too — it finds it once instead of searching twice. In C++20, contains(key) is the clearest way to ask the yes/no question.

#include <iostream>
#include <map>
#include <string>
#include <unordered_map>

int main() {
    std::map<std::string, int> ages;
    ages["Ananya"] = 22;
    ages["Rahul"] = 25;
    ages.insert({"Meera", 21});

    // Sorted iteration, with C++17 structured bindings
    for (const auto& [name, age] : ages) {
        std::cout << name << ": " << age << '\n';   // Ananya, Meera, Rahul
    }

    // THE TRAP: this inserts "Vikram" with age 0
    if (ages["Vikram"] > 18) { }
    std::cout << ages.size() << '\n';               // 4, not 3

    // Safe ways to ask
    if (ages.count("Kabir")) std::cout << "present\n";

    if (auto it = ages.find("Ananya"); it != ages.end()) {
        std::cout << it->second << '\n';            // 22 — found once, used once
    }

    try {
        std::cout << ages.at("Kabir") << '\n';      // throws, does not insert
    } catch (const std::out_of_range&) {
        std::cout << "no such student\n";
    }

    // Where operator[] is exactly right: counting
    std::unordered_map<std::string, int> frequency;
    for (const std::string& w : {"the", "cat", "the"}) ++frequency[w];
    std::cout << frequency["the"] << '\n';          // 2
}

Sets, Adapters, and Removing While Iterating

A set is a map without the values: it stores unique keys and answers "is this present?". std::set keeps them sorted, std::unordered_set hashes them. Inserting a duplicate is not an error — it simply does nothing, which makes a set the neatest way to deduplicate a collection. insert returns a pair whose second element tells you whether anything was actually added.

The adapters — std::stack, std::queue and std::priority_queue — are thin wrappers that restrict a container to one access pattern. A stack offers only push, pop, top and empty; a queue offers push, pop, front and back. The restriction is the point: code using a stack cannot accidentally index into the middle of it, and the reader knows the intent immediately. std::priority_queue keeps the largest element at the top by default, which is what makes it the standard tool for Dijkstra's algorithm and for "top K" problems — pass std::greater<> to get the smallest instead.

One shared gotcha with the adapters: pop() removes the top element and returns nothing. To use the value you must read top() (or front()) first and then call pop(). This looks like an oversight and is deliberate — returning the element by value could throw partway through, leaving the container already modified and the value lost.

Finally, removing elements while iterating. Doing it naively breaks, because erasing invalidates the iterator you are holding. Every container's erase returns an iterator to the element that followed, so the correct loop advances only when it does not erase: it = container.erase(it); in the erasing branch, ++it; otherwise.

For a vector, there is a better way. Erasing one element at a time is O(n) each, so removing many is O(n²). The erase-remove idiom does it in one pass: std::remove_if shuffles the survivors to the front and returns where the leftovers begin, and a single erase chops the tail off. In C++20 this is wrapped up as std::erase_if(v, predicate).

#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

int main() {
    // Set: unique, and sorted for std::set
    std::set<int> unique = {3, 1, 4, 1, 5, 9};
    for (int x : unique) std::cout << x << ' ';        // 1 3 4 5 9
    std::cout << '\n';

    auto [pos, inserted] = unique.insert(4);
    std::cout << inserted << '\n';                      // 0 — already present

    // Adapters: pop() returns nothing, so read first
    std::stack<std::string> undo;
    undo.push("typed"); undo.push("deleted");
    std::string last = undo.top();
    undo.pop();
    std::cout << last << '\n';                          // deleted

    std::priority_queue<int> highest;                   // largest on top
    for (int m : {72, 91, 65}) highest.push(m);
    std::cout << highest.top() << '\n';                 // 91

    std::priority_queue<int, std::vector<int>, std::greater<>> lowest;
    for (int m : {72, 91, 65}) lowest.push(m);
    std::cout << lowest.top() << '\n';                  // 65

    // Erasing from a map while iterating
    std::map<std::string, int> marks =
        {{"Ananya", 91}, {"Rahul", 28}, {"Meera", 78}};
    for (auto it = marks.begin(); it != marks.end(); ) {
        if (it->second < 33) it = marks.erase(it);      // erase returns the next
        else                 ++it;
    }
    std::cout << marks.size() << '\n';                  // 2

    // Erase-remove on a vector: one pass, not n passes
    std::vector<int> scores = {72, 28, 91, 15, 65};
    scores.erase(std::remove_if(scores.begin(), scores.end(),
                                [](int s) { return s < 33; }),
                 scores.end());
    std::cout << scores.size() << '\n';                 // 3
}