C++: STL, Advanced Containers
Master the full STL container toolkit: stack, queue, deque, list, set, map, unordered_map, and priority_queue, each suited to a different data problem.
Choosing the Right Container
Every STL container makes a specific set of trade-offs between speed, ordering guarantees, and memory layout. Picking the right one for the job is one of the most practical C++ skills. The question to ask first is: what operation do I need to be fast?
Container Selection Guide
Start with vector. Move to a specialized container only when you have a concrete need that vector handles poorly.
- Fast LIFO access: stack
- Fast FIFO access: queue
- Fast insert/remove at both ends: deque
- Fast insert/remove anywhere in the middle: list
- Unique sorted elements, fast membership test: set
- Key-value storage, sorted by key: map
- Key-value storage, fastest lookup: unordered_map
- Always process the highest-priority item next: priority_queue
Stack: Last-In, First-Out
A stack enforces LIFO order: the last element pushed is the first one popped. Only the top element is ever visible. Include <stack>.
stack
Think of a stack of plates: you always take from the top. push() adds to the top; pop() removes from the top; top() peeks without removing.
- push(x): add x to the top
- pop(): remove the top element (does not return it)
- top(): read the top element without removing it
- empty(): true if no elements remain
- size(): number of elements currently in the stack
Stack: Balanced Parentheses Checker
C++Push every opening bracket; pop when a closing bracket is found. An empty stack at the end means all brackets matched.
Queue: First-In, First-Out
A queue enforces FIFO order: the first element pushed is the first one served. New elements join at the back; elements leave from the front. Include <queue>.
queue
Think of a checkout line: the first person in is the first person served. push() joins the back; pop() removes from the front; front() peeks at the next to be served.
- push(x): add x to the back
- pop(): remove the front element
- front(): read the front element without removing it
- back(): read the last element
- empty() / size(): status checks
Queue: Customer Service Simulation
C++Customers join the back and are served from the front. front() reads who is next; pop() removes them after service.
Deque: Double-Ended Queue
A deque (double-ended queue) supports fast push and pop at both ends, unlike a vector which is only efficient at the back. It also supports random access by index. Include <deque>.
deque
Use deque when you need both push_front and push_back. It is the underlying container for std::queue and std::stack by default.
- push_back(x) / push_front(x): add to either end in O(1)
- pop_back() / pop_front(): remove from either end in O(1)
- Random access: d[i] or d.at(i) in O(1)
- No single contiguous block, slightly higher memory overhead than vector
Deque: Push and Pop at Both Ends
C++push_front and push_back both run in O(1). Random access by index is also supported.
List: Doubly Linked List
A list is a doubly linked list. Inserting or removing at any position takes O(1) once you have an iterator to that position, making it ideal for workloads with frequent mid-sequence modifications. The trade-off is no random access by index and higher memory use per element. Include <list>.
list
Use list when you insert or remove frequently in the middle. If you mostly append and access by index, vector is faster despite list's O(1) insert.
- push_back / push_front / pop_back / pop_front: same as deque
- insert(iterator, value): O(1) insert before the given position
- erase(iterator): O(1) remove at the given position
- No operator[]: you must traverse with an iterator to reach a position
- sort() is a member function, not std::sort, because random-access is unavailable
List: Insert, Remove, and Sort
C++advance() moves an iterator; insert() adds in O(1) at that position; remove() deletes all matching values.
Set: Unique Sorted Elements
A set automatically keeps its elements unique and sorted in ascending order. Inserting a duplicate is silently ignored. Membership tests run in O(log n). Include <set>.
set
Use set when you need a collection with no duplicates and fast membership testing. Iteration always yields elements in sorted order.
- insert(x): adds x if not already present; duplicate inserts are ignored
- erase(x): removes the element with value x
- count(x): returns 1 if x is in the set, 0 otherwise
- find(x): returns an iterator to x, or end() if absent
- All operations: O(log n)
Set: Unique Sorted Student IDs
C++Duplicate inserts are silently dropped. Iteration always produces sorted output.
Map: Key-Value Pairs
A map stores key-value pairs sorted by key. Each key is unique. Accessing a key with [] creates the entry if it does not exist; use count() or find() to check before accessing. Include <map>.
map
map[key] is convenient but inserts a default value if the key is absent. Prefer find() or count() when you only want to check existence without creating an entry.
- Insert: m[key] = value; or m.insert({key, value});
- Access: m[key] (inserts default if missing) or m.at(key) (throws if missing)
- Check existence: m.count(key) returns 1 or 0
- Iterate: for (auto& [k, v] : m), structured bindings (C++17)
- All operations: O(log n)
Map: Student Names and Scores
C++Keys are unique and sorted. Assigning to an existing key updates the value. count() checks existence safely.
Map in Action: Word Frequency Counter
Because map[key] initializes missing keys to zero, incrementing it in a loop is all it takes to count frequencies. This is one of the most common and idiomatic uses of map in C++.
Frequency Counting with map
map[word]++ creates the entry at 0 if absent, then increments it. One line handles both the first occurrence and all subsequent ones.
- First time a word is seen: map[word] = 0, then incremented to 1
- Every subsequent occurrence: value is incremented directly
- The result is automatically sorted alphabetically by word
- Replace map with unordered_map for faster counting on large inputs
Word Frequency Counter
C++freq[word]++ handles both new and existing words in one line. Output is sorted alphabetically.
Unordered Map: Hash Table Lookup
unordered_map stores key-value pairs in a hash table. Lookup, insert, and delete all average O(1), faster than map's O(log n), but the keys are not stored in sorted order. Include <unordered_map>.
unordered_map vs map
Use unordered_map when lookup speed matters and sorted order does not. Use map when you need to iterate in key order or require a guaranteed worst case.
- Same interface as map: [], at(), find(), count(), erase()
- Average O(1) for all operations; O(n) worst case on hash collisions
- Iteration order is not defined, do not rely on it
- Requires the key type to be hashable (all built-in types are; custom types need a hash function)
Unordered Map: Phone Directory
C++find() returns an iterator. it->second is the value. Average O(1) lookup regardless of map size.
Priority Queue: Always Serve the Highest Priority
A priority_queue is a heap-based container. By default it is a max-heap: top() always returns the largest element. Use greater<int> as the comparator for a min-heap. Include <queue>.
priority_queue
Every push re-heapifies in O(log n). top() is O(1). Use it whenever the next item to process is determined by a priority value, not insertion order.
- push(x): insert x, re-heapify
- top(): read the highest-priority element without removing it
- pop(): remove the highest-priority element
- Min-heap declaration: priority_queue<int, vector<int>, greater<int>> pq;
Priority Queue: Task Scheduling
C++The task with the highest priority integer is always served next, regardless of insertion order.
Container Complexity Summary
Choosing the right container reduces algorithm complexity from hours of runtime to milliseconds. The table below summarizes the key operations and their time complexities for quick reference.
Time Complexity at a Glance
n is the number of elements currently in the container. O(1) means constant time regardless of n; O(log n) means the cost grows slowly; O(n) means it scales linearly.
- For random access by index, only vector and deque offer O(1)
- For sorted unique data, set and map both operate in O(log n)
- For maximum throughput on lookup, unordered_map averages O(1)
- For always-next-highest-priority access, priority_queue top() is O(1)
| Container | Insert | Access | Search | Delete |
|---|---|---|---|---|
| stack | O(1) top | top only O(1) | N/A | O(1) top |
| queue | O(1) back | front O(1) | N/A | O(1) front |
| deque | O(1) ends | O(1) by index | O(n) | O(1) ends |
| list | O(1) pos | O(n) by index | O(n) | O(1) pos |
| set | O(log n) | O(log n) | O(log n) | O(log n) |
| map | O(log n) | O(log n) | O(log n) | O(log n) |
| unordered_map | O(1) avg | O(1) avg | O(1) avg | O(1) avg |
| priority_queue | O(log n) | top O(1) | N/A | O(log n) |
Knowledge Check
1. Which STL container follows Last-In, First-Out (LIFO) order?
2. In a std::queue, which method removes an element?
3. What makes std::set different from std::vector?
4. How do you access the value associated with a key in a std::map?
5. What is the main advantage of unordered_map over map?
6. By default, std::priority_queue serves which element first?
7. Which container is best for frequent insertions and deletions in the middle of the sequence?
8. What does deque stand for?
9. Which method checks if a key exists in a map without inserting it?