Choosing a C++ container: vector, map, unordered_map, deque and list
A practical guide to the standard C++ containers: what each is good at, what its operations cost, iterator invalidation, and how real projects combine them.
Choosing the right container is one of the most important decisions in a C++ design. It decides the cost of every operation and which bugs are possible. Here's a practical map of the standard containers.
The short version
| Container | Good at | Cost of a lookup |
|---|---|---|
std::vector | The default. Contiguous, fast to iterate | O(n) unsorted |
std::unordered_map | Lookup by key | O(1) average |
std::map | Sorted keys, range queries, lower_bound | O(log n) |
std::deque | Push and pop at both ends | O(n) |
std::list | Moving nodes in O(1), stable iterators | O(n) |
std::set / unordered_set | "Have I seen this?" | O(log n) / O(1) |
Start with std::vector. Move to something else when an operation you need is too slow or
impossible.
std::map: when order matters
A std::map keeps keys sorted, which gives you sorted output for free and "find the neighbours"
queries:
std::map<int, Booking> by_start; // start minute -> booking
auto next = by_start.lower_bound(slot.start); // first booking starting at or afterThat's how room bookings for Meetly checks clashes in O(log n): only the booking before and the one after can overlap.
Watch out: map[key] inserts a default value if the key is missing. In a lookup, use find:
const auto it = stock.find(sku);
const int count = it == stock.end() ? 0 : it->second;std::unordered_map: when you only need lookups
Hash maps give average O(1) lookups but no order. If your output must be deterministic, sort it explicitly, with a tie-break, before returning it.
Combining containers
Real designs often pair two containers, each doing what it's good at. The classic example is an LRU cache:
std::list<std::pair<std::string, std::string>> entries; // recency order
std::unordered_map<std::string, decltype(entries)::iterator> index; // key -> nodeThe map finds a node in O(1); entries.splice(entries.begin(), entries, it) moves it to the front in
O(1). Build it yourself in a product cache for Quickcart.
Iterator invalidation
Pointers and iterators into a container can become invalid when it changes:
std::vector: any insertion that grows it can move every element.std::map,std::list: iterators to other elements stay valid on insert and erase.std::unordered_map: a rehash invalidates iterators (but not references to elements).
That's why designs that store iterators, like the order book in
Tickmark Exchange, use std::list and std::map.
Questions and answers
- Should I use std::map or std::unordered_map?
- unordered_map when you only need lookups by key: O(1) on average. map when you need keys in order, range queries or 'the first key at or after x' (lower_bound): O(log n), and iteration is sorted.
- When is std::list the right choice?
- Rarely, but when it is, nothing else does: when you need to move or remove elements in the middle in O(1) while keeping iterators to other elements valid, as in an LRU cache or an order book.
Practise it in a project
These projects put this guide to work, with tickets, tests and code review.
Quickcart
A product cache for Quickcart
Put a least-recently-used cache in front of Quickcart's slow product service, with O(1) operations, statistics and live resizing.
- hash maps
- linked lists
- iterator stability
- amortised O(1)
Meetly
Room bookings for Meetly
Stop double bookings in Meetly's rooms with an ordered index, then find times when everyone is free by merging calendars.
- half-open intervals
- ordered maps
- interval merging
- lower_bound
Tickmark Exchange
An order book for Tickmark Exchange
Build the heart of an exchange: a limit order book with price-time priority, partial fills and O(1) cancels, then market orders, immediate-or-cancel and order amendments.
- ordered maps
- iterator stability
- invariants
- property-based testing
Pantry & Co.
Stock counts for Pantry & Co.
Track stock as goods arrive and leave Pantry's warehouse, and tell the buyers what to reorder.
- classes
- invariants
- std::map
- input validation
Read next
- How to write a design doc: a short guide for junior developers
What a design document is for, a half-page template (components, data structures, trade-offs, open questions) and a worked example, before you write any code.