The STL Containers in Depth
Pick the right data structure and your program gets faster and clearer for free
Big Idea: The Standard Template Library gives you ready-made containers —
vector, list, map, set, and their hashed cousins unordered_map / unordered_set. They all store data, but each makes a different trade-off between fast access, fast search, ordering, and memory. Choosing well is one of the biggest skills that separates a beginner from an intermediate C++ programmer.
By the end you will be able to:
- describe how
vector,list,map,set,unordered_mapandunordered_setstore data, - read a Big-O table and pick the container that fits your access pattern,
- explain when order matters and when a hash table is the better choice,
- avoid the classic performance traps (middle inserts, unneeded copies, missing
reserve).
1. The three families
Every standard container belongs to one of three families. Knowing the family tells you most of what you need before you read a single method name.
- Sequence containers (
vector,list,deque) keep elements in the order you put them in. You care about position. - Ordered associative containers (
map,set) keep elements sorted by key and are built on a balanced binary search tree. You care about sorted lookup. - Unordered associative containers (
unordered_map,unordered_set) store elements in a hash table. There is no order at all, but average lookup is O(1). You care about raw speed.
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
std::vector<int> v; // dynamic array, contiguous memory
std::list<int> l; // doubly linked list
std::map<std::string, int> m; // sorted key -> value (tree)
std::set<int> s; // sorted, unique keys (tree)
std::unordered_map<int, int> um; // hashed key -> value
std::unordered_set<int> us; // hashed, unique keys