STL Containers — vector, map, set & friends

Containers fall into three families:

std::vector (recap)

Dynamic array — your default. Covered in detail in the vector topic. Reach for vector first; switch only when measurements demand.

std::array

A thin wrapper over a fixed-size C array. Stack-allocated, size known at compile time, but you get size(), begin(), end(), range-for, comparison, etc.

#include <array>
array<int, 4> a{1, 2, 3, 4};
for (int x : a) cout << x;

Use when you know the size at compile time and don't want heap allocation.

std::map — Sorted Key→Value

Implemented as a balanced binary tree (red-black tree). Operations are O(log n) and iteration is sorted by key.

map<string, int> scores;
scores["alice"] = 90;          // insert/assign
scores["bob"]   = 75;
scores.insert({"carol", 88});
scores.emplace("dave", 60);     // construct in place
for (const auto& [name, score] : scores) cout << name << ":" << score << "\n";
// Iterates ALPHABETICALLY by key
if (auto it = scores.find("alice"); it != scores.end()) {
    cout << it->second;
}
// C++20:
if (scores.contains("alice")) { /* ... */ }
scores.erase("bob");

> ⚠️ m[key] inserts a default-constructed value if the key is missing. Use m.find() or m.contains() to check without inserting.

std::unordered_map — Hash Table

Same interface as map, but:

• Hash table internally
• O(1) average lookup, O(n) worst case
• Unordered iteration
• Slightly higher memory use

unordered_map<string, int> counts;
counts["hello"]++;
counts["world"]++;

For built-in types and string, the standard hash works out of the box. Custom types need a hasher.

> Default to unordered_map unless you need sorted iteration or you've measured a problem.

std::set / std::unordered_set

Like maps but only keys — sorted unique values, or hashed unique values:

set<int> ids{3, 1, 4, 1, 5};      // {1, 3, 4, 5} — duplicates collapsed
ids.insert(9);
if (ids.count(3)) cout << "yes";   // ↑ count(0|1) — works on all sets
unordered_set<string> seen;
seen.insert("alpha");

std::deque

Double-ended queue. push_front and push_back both O(1). Indexing is O(1) too. Memory layout is segmented, so worse cache behaviour than vector.

deque<int> d;
d.push_back(1);
d.push_front(0);    // [0, 1]

std::list — Doubly Linked List

O(1) insert/erase anywhere if you have an iterator. Random access is O(n) — no [] operator. Cache-unfriendly.

> Rarely the right answer. Use vector or deque unless you measurably need O(1) splice.

Adapters: stack, queue, priority_queue

These wrap an underlying container with a restricted interface.

stack — LIFO

#include <stack>
stack<int> s;
s.push(1); s.push(2); s.push(3);
cout << s.top();   // 3
s.pop();

queue — FIFO

#include <queue>
queue<int> q;
q.push(1); q.push(2);
cout << q.front();  // 1
q.pop();

priority_queue — Max-Heap

priority_queue<int> pq;
pq.push(3); pq.push(1); pq.push(4);
cout << pq.top();    // 4 — largest
pq.pop();
// Min-heap:
priority_queue<int, vector<int>, greater<int>> minpq;

Used heavily in graph algorithms (Dijkstra, A*, k-largest, etc.).

Choosing the Right Container

Need order matters?
├─ Yes → vector (default), array (fixed size), deque (push both ends), list (O(1) splice)
└─ No  → 
    Lookup by key?
    ├─ Yes → unordered_map (default), map (need sorted)
    └─ No  → unordered_set (default), set (need sorted)

Common Operations Across Containers

Iteration & Structured Bindings (C++17)

map<string, int> m{{"a", 1}, {"b", 2}};
// pre-C++17
for (auto it = m.begin(); it != m.end(); ++it)
    cout << it->first << ":" << it->second << "\n";
// C++17 structured bindings — much cleaner
for (const auto& [key, value] : m)
    cout << key << ":" << value << "\n";

Insertion-Without-Override

m["a"] = 5;          // overwrites if "a" exists
m.insert({"a", 5});   // does NOT overwrite if "a" exists
m.try_emplace("a", 5); // C++17 — most efficient

Common Pitfalls

You now know which container to grab for any problem. Phase 4 starts with STL algorithms — the verbs that operate on these containers.