STL complexity and problem-solving patterns
Choose containers and algorithms by complexity and combine them to solve common coding problems.
Learning objectives
- Compare complexity for common STL containers and algorithms.
- Choose a container from the operations a problem needs.
- Combine algorithms and containers for frequency counting and deduplication.
- Explain why complexity is a design tool, not a guarantee of wall-clock speed.
Prerequisites: sequence and associative containers, iterators, sorting, and Big-O notation. Review STL containers, Maps and sets, and STL algorithms first.
Container complexity at a glance
| Container | Access / lookup | Insert / remove | Important note |
|---|---|---|---|
vector | Index O(1) | Back amortized O(1); middle O(n) | Contiguous storage and good locality |
deque | Index O(1) | Both ends O(1) | Not one contiguous block |
list | Search O(n) | Known iterator O(1) | Extra links and weaker locality |
map/set | O(log n) | O(log n) | Keys remain ordered |
unordered_map | Average O(1), worst O(n) | Average O(1), worst O(n) | Hashing, no sorted order |
priority_queue | Top O(1) | Push/pop O(log n) | Only top priority is exposed |
Algorithm complexity
| Algorithm | Typical complexity |
|---|---|
find, count_if | O(n) |
sort | O(n log n) |
lower_bound on random-access iterators | O(log n) |
binary_search on forward iterators | O(log n) comparisons; movement may be O(n) |
Pattern 1: frequency counting
std::unordered_map<int, int> frequency;
for (int value : values) {
++frequency[value];
}Average O(n) total time for n values, assuming average constant-time hash operations. Use map instead if you need keys printed in sorted order.
Pattern 2: sort and remove duplicates
std::sort(values.begin(), values.end()); auto new_end = std::unique(values.begin(), values.end()); values.erase(new_end, values.end());
Sorting costs O(n log n); unique then scans linearly. This removes consecutive duplicates, which is why sorting first matters. The erase call removes the unused tail.
Pattern 3: maintain top k values
A min-heap of size k can keep the largest k values seen so far. Push each value; if the heap grows beyond k, pop the smallest. This takes O(n log k) time and O(k) extra space. The heap's top is the smallest among the retained k values.
How to choose
- Write down the operations the problem needs.
- Estimate how often each operation happens.
- Choose a container that supports the expensive operations efficiently.
- Account for ordering, memory, iterator invalidation, and worst-case behavior.
- Measure performance only after correctness is established.
Common mistakes
- Choosing a linked list just because one insertion operation is O(1), ignoring search.
- Calling unordered_map O(1) without saying average case.
- Ignoring the cost of shifting vector elements.
- Using binary search before establishing sorted order.
- Optimizing a tiny operation while overlooking an O(n²) loop.
Practice
- Choose a container for counting word frequencies.
- Choose a container for maintaining values in sorted order with frequent insertion.
- Explain the complexity of sorting then removing duplicates.
- Design an O(n log k) approach to find the k largest numbers.
Show solutions
unordered_map<string,int>for average fast lookup; use map if sorted output is needed.maporset, depending on whether key-value pairs or unique values are needed.- O(n log n) for sort plus O(n) for unique/erase work.
- Maintain a min-heap of size k; replace its top when a larger value arrives.
Summary
Choose STL tools by required operations and complexity. Combine containers and algorithms to express common patterns clearly, and state average-case versus worst-case assumptions.