Skip to main content
Be Bitwise
C++Templates & the STL

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:

cpp
std::vector<int> nums = {1, 2, 3, 4, 5};
nums.push_back(6);
nums[0] = 10;
std::cout << nums.size() << std::endl; // 6

std::array - fixed-size array that knows its own size (.at() checks bounds, [] doesn't):

cpp
std::array<int, 5> arr = {1, 2, 3, 4, 5};
// arr.push_back(6); // ERROR: fixed size

std::deque - double-ended queue, efficient push/pop at both ends.

Associative Containers

std::map - ordered key-value pairs (red-black tree):

cpp
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):

cpp
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

0
1
2
3
4
5
6
7
Empty
Occupied
Collision
Probed
Load: 0.00Collisions: 0Entries: 0
Load
0%

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.

Key Concept

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

NeedContainerComplexity
Dynamic arrayvectorO(1) amortized push_back
Key-value lookupunordered_mapO(1) average
Sorted key-valuemapO(log n)
Unique elementsunordered_setO(1) average
Queuedeque or queueO(1) push/pop
Priority queuepriority_queueO(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.

Try itRun it twice and compare the list's two scan times, then swap std::list for std::deque (and l.sort() for std::sort) and see where it lands.
C++ (GCC 9.2.0)

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:

cpp
std::vector<int> v = {10, 20, 30};
// Range-based for loop (preferred)
for (int x : v) std::cout << x << " ";
// Iterator-based
for (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:

cpp
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.