Skip to content
Tutorials Center
My learning

Topics

Lesson 94 of 171 ยท The Standard Library (STL)

The Standard Template Library

Get the big picture of the C++ Standard Template Library - containers, iterators and algorithms, how they fit together, choosing the right container, and Big-O guarantees.

The Standard Template Library (STL) is the part of the C++ standard library that gives you ready-made data structures and the algorithms to work on them: dynamic arrays, linked lists, hash tables, balanced trees, plus sorting, searching, counting, transforming and dozens more. It's built entirely from the class templates and function templates you've just learned, so it works with any element type, and it's fast: the containers have documented complexity guarantees and the algorithms are tuned by people who do nothing else.

The STL's big idea is a clean separation into three parts. Containers store data. Algorithms process data. Iterators connect them: an algorithm never knows which container it's working on, it only sees a pair of iterators marking a range. That's why one std::sort works on a std::vector, a std::deque, a std::array and a plain C array alike. This lesson gives you the map of the whole territory and the rules for choosing a container; the following lessons explore each piece in depth.

The three pieces working together

Here's a small program that uses all three: a container holds words, iterators describe ranges, and algorithms sort, search and count without a single hand-written loop.

C++ Containers, iterators and algorithms

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

std::find_if returns an iterator: a position, not a value. If nothing is found it returns the end iterator, which points one past the last element. Checking it != words.end() before using *it is the STL's standard "not found" pattern.

The std::ranges:: versions (C++20) accept a whole container instead of a begin/end pair, so you can't accidentally mix iterators from two containers. They're the recommended style for new code; the classic iterator-pair versions are everywhere in existing code and still needed for sub-ranges. See Ranges and Views.

The containers

The standard containers fall into four groups.

Sequence containers keep elements in the order you put them:

Container Structure Strengths
std::vector<T> contiguous, growable array the default; fast iteration, indexing, push/pop at the back
std::array<T, N> fixed-size contiguous array no heap allocation, size known at compile time
std::deque<T> blocks of arrays fast push/pop at both ends, indexing
std::list<T> doubly linked list O(1) insert/erase anywhere given an iterator, splice
std::forward_list<T> singly linked list the same, with less memory per node
std::string contiguous characters a vector of char with text operations

Ordered associative containers keep elements sorted by key, usually as red-black trees:

Container Holds
std::set<Key> / std::multiset<Key> unique / repeated keys, sorted
std::map<Key, T> / std::multimap<Key, T> key-value pairs, sorted by key

Unordered associative containers are hash tables: no order, but average O(1) lookups: std::unordered_set, std::unordered_multiset, std::unordered_map, std::unordered_multimap.

Container adapters wrap another container and restrict its interface: std::stack (LIFO), std::queue (FIFO), std::priority_queue (largest first). C++23 adds the flat adapters std::flat_map and std::flat_set (sorted vectors), which GCC 15 supports.

Beyond those there are "almost containers" you'll use alongside them: std::span and std::string_view (non-owning views), std::bitset, std::pair/std::tuple, and std::optional/std::variant.

C++ One task, five containers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

std::println can format all of these directly (a C++23 feature): sequences as [...], sets as {...} and maps as {key: value, ...}.

Complexity guarantees

Unlike many libraries, the C++ standard specifies how fast operations must be, in Big-O terms. That makes the choice of container an engineering decision you can reason about. n is the number of elements:

Operation vector deque list set / map unordered_set / map
Index [i] O(1) O(1) not available not available not available
Find by value/key O(n) O(n) O(n) O(log n) O(1) average, O(n) worst
Insert/erase at back O(1) amortized O(1) O(1) n/a n/a
Insert/erase at front O(n) O(1) O(1) n/a n/a
Insert/erase in the middle O(n) O(n) O(1) given an iterator O(log n) O(1) average
Iterate in sorted order sort first sort first sort first built in not available
Memory overhead per element none small two pointers three pointers + color one pointer + buckets

"Amortized O(1)" for push_back means that the occasional reallocation is O(n), but averaged over many pushes each one costs a constant; std::vector in Depth shows why.

Algorithms are specified the same way: std::sort is O(n log n), std::find is O(n), std::binary_search and std::lower_bound are O(log n) on sorted random-access ranges, std::nth_element is O(n) on average.

Big-O isn't the whole story

Big-O hides constant factors, and on modern CPUs the biggest constant factor is memory access. A std::vector stores its elements next to each other, so iterating it streams through cache lines and lets the CPU prefetch. A std::list or std::map scatters nodes around the heap; every step is a pointer chase that can miss the cache. As a result, a linear search through a small vector often beats a tree lookup, and inserting into the middle of a vector of a few thousand ints is frequently faster than inserting into a list, even though the list "wins" on paper.

C++ Big-O versus the cache

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The exact numbers depend on the machine and on what else the server is doing, so run it a few times. On typical hardware, summing the vector is several times faster than walking the list or the set, even though all three are O(n). And binary_search on a sorted vector, also O(log n), usually beats std::set::contains because the vector's data is compact. The checksum line just stops the optimizer from deleting the work.

Choosing a container

Start with this decision list and only deviate when you have a reason (and ideally a measurement):

  1. Default to std::vector. It's the fastest container for iteration, uses the least memory, and works with every algorithm. Many "I need a list" problems are really "I need a vector".
  2. Size fixed at compile time? Use std::array.
  3. Need fast lookup by key? Use std::unordered_map / std::unordered_set when you don't need order, std::map / std::set when you need sorted iteration, range queries (lower_bound) or a guaranteed worst case. For small or rarely modified collections, a sorted std::vector (or C++23 std::flat_map) is often faster still.
  4. Need to add and remove at both ends? Use std::deque (or std::queue on top of it).
  5. Need stable element addresses while inserting and erasing in the middle, or splice? Use std::list. This is rarer than you'd think.
  6. Need LIFO, FIFO or "always the largest next"? Use std::stack, std::queue or std::priority_queue.

And a few habits that apply to all of them:

  • Store values, not pointers, unless you need polymorphism; then store std::unique_ptr<Base>.
  • Know when iterators are invalidated. Growing a vector can move every element; erasing from a map only invalidates the erased element. The next lesson, Iterators, covers the rules.
  • Prefer algorithms to raw loops. std::ranges::count_if(v, pred) states its intent; a hand-written loop must be read to be understood.
  • Pass containers by const& (or std::span / std::string_view) to functions that only read them; see Parameters.

The algorithms library at a glance

<algorithm> and <numeric> hold over 100 algorithms. You don't need to memorize them, but knowing the families lets you find the right one:

Family Examples Lesson
Searching and counting find, find_if, count_if, any_of, all_of, search Searching, Sorting and Counting
Sorting and order sort, stable_sort, partial_sort, nth_element, lower_bound, min_element Searching, Sorting and Counting
Modifying copy_if, transform, fill, replace, remove_if, unique, reverse, rotate, shuffle Transforming and Modifying
Numeric accumulate, reduce, inner_product, partial_sum, iota, transform_reduce Numeric Algorithms
Set operations on sorted ranges set_union, set_intersection, set_difference, includes, merge std::set and std::unordered_set
Heaps make_heap, push_heap, pop_heap Container Adapters

Most algorithms take a callable to customize them: a lambda, a function, or a function object like std::greater{}.

C++ Algorithms with lambdas

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

&Order::amount is a projection: ranges algorithms apply it to each element before comparing, so max_element(orders, {}, &Order::amount) means "the order with the largest amount" (the {} is the default comparator, std::ranges::less). std::back_inserter is an iterator that calls push_back on every write, letting an algorithm grow a container; you'll meet it in the next lesson.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why can one std::sort work on a vector, a deque and a C array?

    STL algorithms operate on iterator ranges. Any container whose iterators meet the requirements (random access, for sort) works; there is no common base class.
  2. 2. auto it = std::find(v.begin(), v.end(), 42); What does it equal when 42 is not in v?

    Search algorithms return the end of the range to mean "not found". Always compare with end() before dereferencing.
  3. 3. You need to look up users by ID very often, never need them in sorted order, and the set changes frequently. Which container fits best?

    A hash table gives average O(1) lookups and inserts. std::map is O(log n) and keeps an order you don't need; a linear search is O(n).
  4. 4. Both summing a std::vector and summing a std::list are O(n). Why is the vector usually much faster?

    Big-O ignores constant factors. Contiguous memory makes iteration cache-friendly, while each list node may be anywhere in memory.
  5. 5. What does std::ranges::max_element(orders, {}, &Order::amount) return?

    max_element returns an iterator. The projection &Order::amount tells it to compare orders by their amount member.

Summary

  • The STL consists of containers (store data), algorithms (process data) and iterators (connect the two through ranges).
  • Sequence containers (vector, array, deque, list, forward_list), ordered associative (set, map, multi versions), unordered (hash tables) and adapters (stack, queue, priority_queue) cover almost every need.
  • The standard guarantees complexity: O(1) vector indexing, O(log n) map lookups, average O(1) hash lookups, O(n log n) sorting.
  • Big-O hides cache effects: contiguous containers are often faster than node-based ones even when the complexity is equal or worse.
  • Default to std::vector; pick hash tables or trees for keyed lookup, deque for both ends, list only for its special abilities.
  • Prefer algorithms (and the std::ranges versions with projections) over hand-written loops.

Next: Iterators, the glue between containers and algorithms.