In C++, vector access is constant and push_back is amortized constant. unordered_map find, insert and erase are average constant and worst-case linear. map and set are logarithmic. deque is constant at both ends. priority_queue reads the top in constant time, and pushing or popping takes a logarithmic number of comparisons.
Where these figures come from
C++ has no official documentation site. The authority is the ISO standard, which is sold, so this page uses the free working draft of it, generated on August 23, 2026, which says it is not an ISO publication. Where the draft is hard to read, it also uses cppreference, a community reference. Both were read on November 5, 2026. Each row names which one it came from.
The draft states complexity in the requirements for each kind of container, which is why it can feel strict: any standard library must meet these figures, not just the one you happen to use.
std::vector
| Operation | Cost | Source |
|---|---|---|
Random access: v[i], v.at(i) | Constant, O(1) | cppreference, vector |
At the end: push_back, pop_back | Amortized constant, O(1) | Draft, vector.overview, cppreference |
In the middle: insert, erase | Linear in the distance to the end, O(n) | Draft, vector.overview, cppreference |
std::unordered_map
The draft gives both cases explicitly, which is unusual and useful: you can state the worst case with a source behind it. The figures are for a container with unique keys, so count(k) is at most 1.
| Operation | Average | Worst case | Source |
|---|---|---|---|
find(k) | O(1) | O(size) | Draft, unord.req |
insert, emplace | O(1) | O(size) | Draft, unord.req |
erase(k) | O(count(k)) | O(size) | Draft, unord.req |
rehash(n) | Linear in size | Quadratic | Draft, unord.req |
cppreference sums it up the same way: "Search, insertion, and removal of elements have average constant-time complexity."
std::map and std::set
Both are ordered associative containers with the same requirements. cppreference says they are usually implemented as red-black trees, but the figures below are what is required.
| Operation | Cost | Source |
|---|---|---|
find(k) | Logarithmic | Draft, associative.reqmts |
insert(t) with unique keys | Logarithmic | Draft, associative.reqmts |
lower_bound(k), upper_bound(k) | Logarithmic | Draft, associative.reqmts |
erase(k) | log(size) + count(k) | Draft, associative.reqmts |
So a map is slower than an unordered_map on average, but it has no linear worst case and it keeps keys in order. That is the trade to name when you choose one.
std::deque
| Operation | Cost | Source |
|---|---|---|
Random access: d[i] | Constant, O(1) | cppreference, deque |
At either end: push_front, push_back, pop_front, pop_back | Constant, O(1) | Draft, deque.overview, cppreference |
In the middle: insert, erase | Linear, O(n) | Draft, deque.overview, cppreference |
The draft says a deque is "especially optimized for pushing and popping elements at the beginning and end." Note that it says constant, where vector's end operations are amortized constant.
std::priority_queue
This one is an adaptor over another container, by default a vector, and the draft defines it in terms of the heap algorithms. So its limits are given as a number of comparisons.
| Operation | Cost | Source |
|---|---|---|
top() | Constant | cppreference, priority_queue |
push(x) | At most log(N) comparisons, by way of push_heap | Draft, priqueue.members, push.heap |
pop() | At most 2 log(N) comparisons, by way of pop_heap | Draft, pop.heap |
make_heap over N items | At most 3N comparisons | Draft, make.heap |
cppreference describes the same thing as "constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction." The default is a max-heap, the opposite of Python's and Java's defaults, so a top-k solution has to pass std::greater.
The choices in code
C++
#include <deque>
#include <functional>
#include <map>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// Fewest steps in an unweighted graph: deque as the queue.
int fewestSteps(const std::unordered_map<int, std::vector<int>>& graph, int start, int goal) {
std::deque<std::pair<int, int>> queue{{start, 0}};
std::unordered_set<int> seen{start};
while (!queue.empty()) {
auto [node, dist] = queue.front();
queue.pop_front();
if (node == goal) return dist;
auto it = graph.find(node);
if (it == graph.end()) continue;
for (int next : it->second) {
if (seen.insert(next).second) queue.push_back({next, dist + 1});
}
}
return -1;
}
// The k largest values: std::greater makes this a min-heap holding only k items.
std::vector<int> topK(const std::vector<int>& values, std::size_t k) {
std::priority_queue<int, std::vector<int>, std::greater<int>> heap;
for (int v : values) {
heap.push(v);
if (heap.size() > k) heap.pop(); // evict the smallest
}
std::vector<int> out;
for (; !heap.empty(); heap.pop()) out.push_back(heap.top());
return out;
}
// Average constant-time counts, then keys in order from a map.
std::map<std::string, int> sortedCounts(const std::vector<std::string>& words) {
std::unordered_map<std::string, int> counts;
for (const auto& w : words) ++counts[w];
return std::map<std::string, int>(counts.begin(), counts.end());
}How to say it out loud
I'll use an unordered_map, so find and insert are constant time on average and linear in the worst case, which I don't expect with these keys. If I needed the keys in order, or a bound with no bad case, I'd switch to map and pay logarithmic time per operation. For the heap, priority_queue is a max-heap by default, so I'll pass std::greater to keep the smallest of my top k on top. That's O(n log k) time and O(k) space.
C++ interviewers often go a level deeper, so be ready to say why map is logarithmic and that vector's push_back is amortized because it sometimes reallocates. You can practice it in a coding mock interview, and the Big O cheat sheet covers the structures in general.
What is not in the sections read
This page lists only what was read and checked: the sections linked above. These common costs are not in them, so they have no row:
- Walking a whole
map,setorunordered_mapwith an iterator. vector::reserveand how far apush_backmay reallocate.
Frequently asked questions
What is the time complexity of unordered_map in C++?
The C++ working draft gives find and insert as average case O(1) and worst case O(size), and erasing a key as average case O(count of that key) and worst case O(size). It gives rehash as linear in the size on average and quadratic in the worst case.
Should I use map or unordered_map in a C++ interview?
Default to unordered_map for average constant-time lookups. Choose map when you need keys in order, range queries with lower_bound, or logarithmic operations with no linear worst case. Naming that trade is what the interviewer is listening for, so say why you chose one.
Is vector push_back O(1) in C++?
Amortized O(1). The working draft says a vector supports amortized constant time insert and erase at the end, and linear time in the middle. A single push_back may cost more when the vector has to reallocate, so say amortized when you state it.