The STL

The Standard Template Library (STL) is why C++ is so productive for data structures and algorithms: battle-tested containers and algorithms that work on any type via templates, each with documented complexity. Reach for these before writing your own.

The right container depends on what each operation costs. The visualizer below inserts the same numbers into three containers: a vector (a growing array that doubles its capacity), an ordered set (kept sorted), and an unordered_set (hashed into buckets). Switch modes and step through to feel the difference.

vectorsetunordered_setinserting [5, 2, 8, 2, 1, 9, 3, 7]

·0

0

size

1

capacity

0%

load

—

this op

Step PlayStep ResetSpeed

1/12

vector: contiguous array · amortized O(1) push_backempty vector, capacity 1

Containers

#include <vector>
#include <map>
#include <unordered_map>
#include <set>

std::vector<int> v = {3, 1, 2};   // dynamic array — O(1) index, O(1) amortized push_back
std::map<string,int> m;           // sorted (red-black tree) — O(log n) ops
std::unordered_map<string,int> h; // hash table — O(1) average ops
std::set<int> s;                  // sorted unique keys — O(log n)

Pick by access pattern: vector for sequences, unordered_map/unordered_set for fast membership, map/set when you need keys kept in order.

Iterators

Containers expose iterators — generalized pointers (begin(), end()) — that let one algorithm work across every container. A range is the half-open [begin, end).

Algorithms

#include <algorithm>

std::sort(v.begin(), v.end());                 // O(n log n)
bool found = std::binary_search(v.begin(), v.end(), 2);
auto it = std::find(v.begin(), v.end(), 3);
int total = std::accumulate(v.begin(), v.end(), 0);

<algorithm> and <numeric> give you sort, search, min/max, partition, unique, and dozens more — all decoupled from the container via iterators.

Why it matters

These are the same structures from the Data Structures track, implemented and optimized for you. Knowing the complexity of each operation (the table above) is what lets you choose the right one — a map lookup is O(log n), an unordered_map lookup is O(1) average.

Takeaways

• The STL gives you containers (vector, map, unordered_map, set) with known complexity.
• Iterators are the glue: one algorithm works on any container via [begin, end).
• <algorithm> provides sort/search/transform — prefer it over hand-rolling.