STL Containers

the STL's shape

The Standard Template Library is built from a few independent, cooperating pieces: containers (the data structures themselves), algorithms (operations like sort/find/transform, written once to work across any container), iterators (the glue that lets an algorithm walk a container without knowing its internal layout), and functors/lambdas (the small callables algorithms take as arguments). This page covers containers; algorithms and iterators get their own page.

Category	Containers	Backing structure	Typical complexity
Sequence	vector, array, deque, list, forward_list	contiguous array or linked nodes	varies — see below
Associative (ordered)	set, map, multiset, multimap	balanced binary search tree	O(log n) search/insert/erase
Unordered	unordered_set, unordered_map, ...	hash table	O(1) average, O(n) worst case
Adaptors	stack, queue, priority_queue	wraps one of the above with a restricted interface	inherits the underlying container's complexity

std::vector internals

A vector is typically three pointers under the hood: one to the start of its data, one to one-past its last element, one to one-past the end of its currently-allocated memory. This 3-pointer layout isn't mandated by the standard, but it's what libstdc++, libc++, and MSVC's implementation all use in practice — which is why sizeof(std::vector<anything>) is 24 bytes (3 × 8 on a 64-bit platform) on those implementations, regardless of how many elements it holds.

Method	What it does
`.size()`	number of elements actually stored — 0 for a default-constructed vector
`.capacity()`	how many elements fit in the current allocation before a reallocation is needed
`.reserve(n)`	grow capacity to at least n, without changing size or content
`.resize(n)`	change size to n — default-constructs new elements if growing, destroys extras if shrinking
`.clear()`	size becomes 0; capacity is unchanged

Size and capacity start equal when a vector is constructed with an explicit size. Each push_back after that either fits within the existing capacity (cheap: just writes to the next slot) or exceeds it, which triggers a reallocation — a new, larger block is allocated (implementations typically double the capacity), every existing element is moved or copied into it, and the old block is freed. That amortized doubling is what makes push_back average O(1) per call despite the occasional expensive reallocation.

Whether a reallocation copies or moves each element depends on whether the element type has a noexcept move constructor — see Move Semantics for why that matters, and Exceptions & File I/O for what noexcept itself promises.

other sequence containers

Container	Use it when
`array<T, N>`	the size is fixed and known at compile time — no heap allocation at all
`deque`	you need fast push/pop at both ends — vector only amortizes O(1) at the back
`list`	frequent insertion/removal in the middle, and you don't need random-access indexing
`forward_list`	same as list, singly-linked — smaller per-node overhead when you never need to walk backward

vector is still the right default even when you're tempted by list for "frequent insertion" — contiguous memory means far better cache behavior for iteration, which in practice outweighs list's O(1) insertion for most workloads unless the container is large and insertions genuinely dominate.

associative containers: map, set, and a custom comparator

map/set keep their elements ordered by key (via a balanced binary search tree internally), giving O(log n) search, insertion, and deletion. A map can take a custom comparator as a third template argument — including a lambda, via decltype, useful for something like ordering by absolute value instead of the default <:


auto byAbsValue = [](int a, int b) { return std::abs(a) < std::abs(b); };
std::map<int, int, decltype(byAbsValue)> ordered(byAbsValue);

std::vector<int> values = {1, -2, 3, 4, 2};
for (int v : values) ordered.insert({v, v});
for (auto &[k, v] : ordered) std::cout << k << " "; // 1 -2 3 4 (2 was a duplicate key by absolute value)

Three equivalent ways to insert into a map — worth knowing all three since existing code uses each of them:


std::map<std::string, int> inventory = {{"espresso", 20}, {"latte", 8}};
inventory["mocha"] = 5;                          // operator[] — inserts if absent, overwrites if present
inventory.insert(std::make_pair("chai", 12));      // insert() — does NOT overwrite an existing key
inventory.insert({"cortado", 3});                    // insert() with brace initialization

The custom-comparator map and all three insert styles above, run together, including proof that insert() really does refuse to overwrite an existing key: TopNotchNote/cpp/stl_containers_custom_comparator_map.cpp

unordered containers

unordered_map/unordered_set trade ordering for speed: a hash table gives average O(1) search/insert/erase, versus a tree's guaranteed O(log n). The catch is in the name — there's no guaranteed iteration order, and worst-case complexity degrades to O(n) if many keys collide into the same bucket (rare with a good hash function, but not impossible). Default to unordered_map when you don't need sorted iteration; reach for map when you do, or when worst-case guarantees matter more than average-case speed.

container adaptors

stack, queue, and priority_queue aren't independent data structures — each wraps one of the containers above (by default deque for stack/queue, vector for priority_queue) and exposes only the restricted interface that structure's name implies (push/pop/top for a stack; no random access, no iteration).

std::stack<int> s; | https://en.cppreference.com/w/cpp/container/stack | LIFO — push(), pop(), top() |'stlc1'

std::queue<int> q; | https://en.cppreference.com/w/cpp/container/queue | FIFO — push(), pop(), front()/back() |'stlc2'

std::priority_queue<int> pq; | https://en.cppreference.com/w/cpp/container/priority_queue | always pops the largest element first (a max-heap by default) |'stlc3'

where to go from here

STL Algorithms & Iterators — operating on these containers generically.
Data Structures & Algorithms — the structures underneath, built by hand instead of via the STL.
Move Semantics — why a vector's reallocation cost depends on your element type's move constructor.

reference

cppreference — containers library