Lesson 1310 min read

STL Containers

A fully-stocked kitchen — why build a pot from scratch when there's one on the shelf?

The Kitchen Analogy

The C++ Standard Template Library (STL) is like a professional kitchen that comes fully equipped. Need to store a list of items? There's a container for that. Need fast lookups by key? There's one for that too. Need a priority queue for scheduling? Already built.

The trick isn't learning every pot and pan — it's knowing which one to grab for the job.

Sequence Containers — Ordered Collections

These store elements in a specific order.

vector — Dynamic array. Your go-to default. Fast random access, fast append.
deque — Double-ended queue. Fast insert/remove at both front and back.
list — Doubly-linked list. Fast insert/remove anywhere (if you have an iterator), but no random access.

Associative Containers — Key-Based Lookup

map — Sorted key-value pairs. \(O(\log n)\) lookup. Keys are ordered.
set — Sorted unique values. Like a map with no values.
unordered_map — Hash table. \(O(1)\) average lookup. No ordering.
unordered_set — Hash set. Unique values, no ordering.

Container Adapters — Restricted Interfaces

stack — LIFO. Push/pop from top only.
queue — FIFO. Push back, pop front.
priority_queue — Always pops the largest (or smallest) element first.

map — Word Frequency Counter

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> freq;
    string words[] = {"apple", "banana", "apple", "cherry", "banana", "apple"};

    for (const auto& w : words) {
        freq[w]++;  // operator[] creates entry if missing
    }

    // map is sorted by key!
    for (const auto& [word, count] : freq) {
        cout << word << ": " << count << endl;
    }

    return 0;
}

Output

apple: 3
banana: 2
cherry: 1

set — Unique Elements, Automatically Sorted

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(5);
    s.insert(2);
    s.insert(8);
    s.insert(2);  // duplicate — ignored
    s.insert(5);  // duplicate — ignored

    cout << "Size: " << s.size() << endl;
    cout << "Elements: ";
    for (int x : s) cout << x << " ";
    cout << endl;

    // Fast lookup
    if (s.count(8)) cout << "Found 8!" << endl;
    if (!s.count(99)) cout << "99 not found" << endl;

    return 0;
}

Output

Size: 3
Elements: 2 5 8
Found 8!
99 not found

unordered_map vs. map — Performance

#include <iostream>
#include <map>
#include <unordered_map>
#include <chrono>
using namespace std;
using namespace chrono;

int main() {
    const int N = 1000000;

    // --- map (sorted, O(log n)) ---
    map<int, int> ordered;
    auto t1 = high_resolution_clock::now();
    for (int i = 0; i < N; i++) ordered[i] = i;
    auto t2 = high_resolution_clock::now();
    cout << "map insert: "
         << duration_cast<milliseconds>(t2 - t1).count()
         << " ms" << endl;

    // --- unordered_map (hash, O(1) avg) ---
    unordered_map<int, int> hashed;
    t1 = high_resolution_clock::now();
    for (int i = 0; i < N; i++) hashed[i] = i;
    t2 = high_resolution_clock::now();
    cout << "unordered_map insert: "
         << duration_cast<milliseconds>(t2 - t1).count()
         << " ms" << endl;

    return 0;
}

Output

map insert: 612 ms
unordered_map insert: 198 ms

priority_queue — Top-K Elements

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // Default: max-heap (largest on top)
    priority_queue<int> maxPQ;
    for (int x : {3, 1, 4, 1, 5, 9, 2, 6}) {
        maxPQ.push(x);
    }

    cout << "Top 3 largest: ";
    for (int i = 0; i < 3; i++) {
        cout << maxPQ.top() << " ";
        maxPQ.pop();
    }
    cout << endl;

    // Min-heap: use greater<int>
    priority_queue<int, vector<int>, greater<int>> minPQ;
    for (int x : {3, 1, 4, 1, 5, 9, 2, 6}) {
        minPQ.push(x);
    }

    cout << "Top 3 smallest: ";
    for (int i = 0; i < 3; i++) {
        cout << minPQ.top() << " ";
        minPQ.pop();
    }
    cout << endl;

    return 0;
}

Output

Top 3 largest: 9 6 5
Top 3 smallest: 1 1 2

stack — Bracket Matching

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isBalanced(const string& expr) {
    stack<char> s;
    for (char c : expr) {
        if (c == '(' || c == '[' || c == '{') {
            s.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (s.empty()) return false;
            char top = s.top(); s.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{'))
                return false;
        }
    }
    return s.empty();
}

int main() {
    cout << "{[()]}  -> " << (isBalanced("{[()]}") ? "balanced" : "not balanced") << endl;
    cout << "{[(])}  -> " << (isBalanced("{[(])}") ? "balanced" : "not balanced") << endl;
    cout << "((()))  -> " << (isBalanced("((()))") ? "balanced" : "not balanced") << endl;

    return 0;
}

Output

{[()]}  -> balanced
{[(])}  -> not balanced
((()))  -> balanced

When to Use Which?

Need	Container	Why
General-purpose list	`vector`	Cache-friendly, fast random access
Fast front + back ops	`deque`	O(1) push/pop at both ends
Frequent mid-insert/remove	`list`	O(1) splice with iterator
Sorted key-value pairs	`map`	O(log n), ordered iteration
Fast key-value lookup	`unordered_map`	O(1) average
Unique sorted values	`set`	O(log n), auto-sorted
LIFO	`stack`	Push/pop top only
FIFO	`queue`	Push back, pop front
Always get max/min	`priority_queue`	Heap-based, O(log n) push/pop

Note: unordered_map is O(1) average but O(n) worst case (hash collisions). map is O(log n) always. Use unordered_ versions when you don't need ordering — they're faster on average. But if you need sorted iteration or guaranteed worst-case performance, stick with map/set.

Challenge

Quick check

What is the average time complexity of lookup in std::unordered_map?

← Smart Pointers Iterators & Algorithms →