C++ STL Time Complexity: The Interview Cheat Sheet

You pick std::map because you want fast lookup. Your interviewer asks "what's the complexity?" You say O(1). It's O(log n). The interview shifted.

This is not a rare edge case. It happens constantly, to experienced engineers, because the C++ standard library hides a remarkable amount of sharp machinery behind innocuous names. std::remove does not remove. operator[] inserts on read. std::sort is not the quicksort you remember from class. This guide covers what each container actually costs, where the traps are, and how to talk about it clearly while coding under pressure.

Amortized O(1) Is Not O(1)

This distinction sounds pedantic. Interviewers use it to separate candidates who understand what they are doing from candidates who memorized a table.

When a table says "O(1) amortized," individual operations can spike, but the cost averages out across many calls. vector::push_back is the textbook case: most appends take O(1) time. But every so often the backing array is full, and the whole thing gets doubled and copied, costing O(n) for that one call. Over n pushes, the total work is O(n). Per operation, that is O(1) amortized.

If you tell an interviewer that push_back is always O(1), that is wrong, and they will notice. The same applies to unordered_map inserts and almost anything that involves dynamic resizing. Amortized analysis is worth understanding from first principles, not just as a label to paste on flashcards.

Use `vector`. Override When You Must.

Operation	`vector`	`deque`	`list`
Access by index	O(1)	O(1)	O(n)
Push back	O(1) amort.	O(1) amort.	O(1)
Push front	O(n)	O(1) amort.	O(1)
Insert at middle	O(n)	O(n)	O(1) with iterator
Erase at middle	O(n)	O(n)	O(1) with iterator
Find / search	O(n)	O(n)	O(n)

vector is the right answer for almost everything. Elements sit contiguously in memory, which means the hardware prefetcher can actually help you. deque and list both ruin this. Use deque when you genuinely need O(1) push at both ends and cannot afford a vector shift. Use list almost never: the O(1) erase-by-iterator sounds attractive until you remember that your data is scattered across the heap in little pointer-chained nodes, and every traversal is a cache miss parade.

std::array<T, N> is the fixed-size sibling. Same access patterns as vector, no heap allocation at all.

Ordered Containers: O(log n) Everything

std::map, std::set, std::multimap, and std::multiset are all red-black trees. Every operation costs O(log n). Every single one.

Operation	Complexity
Insert	O(log n)
Erase	O(log n)
Find	O(log n)
`lower_bound` / `upper_bound`	O(log n)
Iteration	O(n), sorted by key

The reason to use std::map is sorted order, not speed. Ordered iteration, range queries, nearest-key lookups via lower_bound: that is the use case. For plain fast lookups where ordering does not matter, unordered_map wins comfortably.

One trap that catches experienced engineers: operator[] on std::map inserts a zero-initialized value if the key is absent. It compiles fine. It silently mutates your map. It corrupts data in any code path that is supposed to be read-only.

// TRAP: inserts "missing_key" with value 0
int val = my_map["missing_key"];

// CORRECT
auto it = my_map.find("missing_key");
if (it != my_map.end()) {
    int val = it->second;
}

This is one of the most common C++ interview bugs. Interviewers know it. Read the hash map internals guide if you want the full picture on why.

Unordered Containers: O(1) Average, O(n) Worst

std::unordered_map, std::unordered_set, and their multi variants are hash tables.

Operation	Average case	Worst case
Insert	O(1)	O(n)
Erase	O(1)	O(n)
Find	O(1)	O(n)
Iteration	O(n)	O(n)

The O(n) worst case is not theoretical. People have exploited it in production. Adversarial inputs can force all keys into the same bucket. The internal bucket count is often a fixed prime (107897 and 126271 appear in common implementations), so keys that are multiples of that prime all collide, turning your O(n log n) algorithm into O(n²) on carefully chosen input. In a standard interview you will not need to worry about this. But if the interviewer asks, know why it happens.

No key ordering on iteration. If you need sorted traversal, use std::map.

One more gap that costs interview time: std::pair and custom struct types have no default hash. You must supply one:

struct PairHash {
    size_t operator()(const pair<int,int>& p) const {
        return hash<long long>()(((long long)p.first << 32) | (unsigned)p.second);
    }
};
unordered_map<pair<int,int>, int, PairHash> grid;

Forgetting this is a compile error. A compile error you will have to debug live, in front of someone taking notes.

The `priority_queue` Default That Bites You

Container	Push	Pop	Peek	Underlying
`stack`	O(1) amort.	O(1)	O(1)	`deque` by default
`queue`	O(1) amort.	O(1)	O(1)	`deque` by default
`priority_queue`	O(log n)	O(log n)	O(1)	`vector` + heap

priority_queue is a max-heap by default. Half of all Dijkstra bugs in interviews come from forgetting this. For a min-heap, pass greater<T>:

priority_queue<int, vector<int>, greater<int>> min_heap;

No decrease-key, no update, no random access. If you need to update a priority that is already inside the heap, use lazy deletion: push a new entry and check for staleness on pop. It wastes a bit of memory and you will feel slightly embarrassed about it, but it is the correct move here.

Which `std::` Algorithm Does What You Think?

Algorithm	Complexity	Notes
`std::sort`	O(n log n) worst	Introsort, not stable
`std::stable_sort`	O(n log² n)	Timsort-like, stable
`std::partial_sort`	O(n log k)	Smallest k elements, sorted
`std::nth_element`	O(n) average	Introselect, not fully sorted
`std::lower_bound`	O(log n)	Sorted range only
`std::upper_bound`	O(log n)	Sorted range only
`std::binary_search`	O(log n)	Returns bool, not iterator
`std::find` / `std::count`	O(n)	Linear scan
`std::unique`	O(n)	Consecutive duplicates only
`std::remove`	O(n)	Does not resize

std::sort is O(n log n) worst case, not just average. It uses introsort: quicksort by default, switching to heapsort when recursion depth exceeds 2·log₂(n) to avoid the O(n²) worst case. This is a deliberate engineering decision that most people do not know about. See merge sort vs quicksort for why the distinction matters in practice.

std::nth_element is O(n) average via introselect. It positions the element at rank k correctly but leaves both partitions unsorted. This is the right answer for "find the k-th smallest element in O(n)."

std::lower_bound and std::upper_bound only give O(log n) on a sorted range. Call them on an unsorted container and you get a silently wrong answer with no error. Nothing will tell you. The tests might not catch it. Ship it and find out later.

The Traps That Catch Experienced Engineers

Trap 1: std::remove does not remove.

std::remove shuffles target elements to the logical end of the container and returns an iterator to the new end. It does not call erase. The container still has the same size. The "removed" elements are still in memory, just sitting at the back looking embarrassed.

// TRAP: v still has the same size
std::remove(v.begin(), v.end(), target);

// CORRECT: erase-remove idiom
v.erase(std::remove(v.begin(), v.end(), target), v.end());

Trap 2: string + in a loop is O(n²).

operator+ creates a new string object on every call. Concatenating n strings allocates and copies O(1 + 2 + ... + n) characters total. That is O(n²). Use +=, which calls append and is O(1) amortized:

// O(n²)
string result = "";
for (auto& s : words) result = result + s;

// O(n)
string result;
for (auto& s : words) result += s;

Trap 3: std::unique requires a sorted range.

std::unique removes consecutive duplicates only. On {3, 1, 3, 2}, it leaves the vector unchanged because the duplicate 3s are not adjacent. Sort first, then unique, then erase:

sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

Trap 4: erasing during vector iteration.

vector::erase invalidates all iterators at and after the erased position. This means your loop variable just became undefined behavior. Use the return value from erase, which points to the next valid element:

for (auto it = v.begin(); it != v.end(); ) {
    if (should_erase(*it)) {
        it = v.erase(it); // points to next element
    } else {
        ++it;
    }
}

Say It Out Loud

Knowing the complexity matters less than stating it clearly while writing correct code. That is the real gap: most candidates pick the right container but stumble when the interviewer asks "why" mid-solution. The knowledge is in their head. The words are not. If you want to build that muscle under actual interview conditions, SpaceComplexity runs voice-based mock interviews where you narrate your data structure choices live and get rubric-based feedback on the explanation quality, not just the code.

C++ STL Time Complexity: Quick Reference

vector is the default. deque for O(1) push at both ends. list almost never.
map and set are O(log n) for everything and iterate in sorted order. operator[] inserts on read.
unordered_map and unordered_set are O(1) average, O(n) worst. Custom hash required for pair keys.
priority_queue is a max-heap by default. greater<T> flips it. No decrease-key.
std::sort is O(n log n) worst case via introsort.
std::nth_element is O(n) average. Use it for k-th element.
std::lower_bound is O(log n) on sorted ranges only.
std::remove does not resize. Use the erase-remove idiom.
String + in a loop is O(n²). Use +=.
std::unique removes consecutive duplicates only. Sort first.