STL Containers
The STL ships battle-tested, high-performance containers for nearly every shape of data you'll meet in practice.
Sequence Containers
std::vector - the workhorse dynamic array:
std::vector<int> nums = {1, 2, 3, 4, 5};nums.push_back(6);nums[0] = 10;std::cout << nums.size() << std::endl; // 6std::array - fixed-size array that knows its own size (.at() checks bounds, [] doesn't):
std::array<int, 5> arr = {1, 2, 3, 4, 5};// arr.push_back(6); // ERROR: fixed sizestd::deque - double-ended queue, efficient push/pop at both ends.
Associative Containers
std::map - ordered key-value pairs (red-black tree):
std::map<std::string, int> ages;ages["Alice"] = 30;ages["Bob"] = 25;
for (const auto &[name, age] : ages) { std::cout << name << ": " << age << std::endl;}std::unordered_map - hash table, O(1) average lookup (O(n) worst case when keys collide, and a rehash invalidates its iterators):
std::unordered_map<std::string, int> cache;cache["key1"] = 100;Inside, libstdc++ and libc++ both build unordered_map as an array of buckets, each holding a chain of the entries whose hashes land there. The explorer below is a small model of that: 8 buckets, chaining, with FNV-1a standing in for std::hash. Add keys until two share a bucket, and keep an eye on the load figure.
Hash Table Explorer
The explorer never resizes, so its chains just keep growing. The real container won't let that happen: once size() / bucket_count() would pass max_load_factor() (1.0 by default), it allocates a bigger bucket array and rehashes every entry, which is the rehash that invalidates iterators.
Reach for std::unordered_map when speed matters and key order doesn't. Pick std::map when you actually need sorted keys. Their interfaces overlap so heavily that swapping one for the other is usually a one-line change.
Choosing the Right Container
| Need | Container | Complexity |
|---|---|---|
| Dynamic array | vector | O(1) amortized push_back |
| Key-value lookup | unordered_map | O(1) average |
| Sorted key-value | map | O(log n) |
| Unique elements | unordered_set | O(1) average |
| Queue | deque or queue | O(1) push/pop |
| Priority queue | priority_queue | O(log n) push/pop |
Big-O hides the memory layout, and the layout often matters more. This runner fills a vector and a list with the same numbers and times a scan of each, before and after sorting. The numbers change from run to run, so pay attention to the ratio between the list's two scans.
A freshly built list usually keeps pace, because its nodes were allocated one after another and sit close together on the heap. l.sort() relinks those nodes without moving them, so the second walk hops all over memory and the cache stops helping. The vector's elements are always contiguous.
Iterators
Every container provides iterators for traversal:
std::vector<int> v = {10, 20, 30};
// Range-based for loop (preferred)for (int x : v) std::cout << x << " ";
// Iterator-basedfor (auto it = v.begin(); it != v.end(); ++it) { std::cout << *it << " ";}Iterators are the glue between containers and algorithms. Write an algorithm against iterators and it works on any container that exposes them.
Structured Bindings
C++17 lets you unpack pairs and tuples cleanly:
std::map<std::string, int> m = {{"a", 1}, {"b", 2}};for (const auto &[key, value] : m) { std::cout << key << " = " << value << std::endl;}No more squinting at it->first and it->second. The runner on this page compiles as C++14, though, so if you try this there, loop with const auto &kv : m and use kv.first and kv.second.