The C++ Standard Template Library (STL): Containers, Iterators and Algorithms

The Standard Template Library (STL) is the part of the C++ standard library that provides ready-made containers (data structures) and algorithms (operations on them). It is fast, well tested, and available with every compiler. Knowing it well is one of the most valuable C++ skills: most problems become a few lines once you pick the right container and algorithm.

Three building blocks#

1. Containers store elements: std::vector, std::map, std::unordered_set, …
2. Iterators point at elements inside a container and move between them, like generalized pointers.
3. Algorithms such as std::sort, std::find and std::count_if work on any range described by a pair of iterators.

Because algorithms talk to containers only through iterators, one std::sort works for vectors, arrays and deques alike:

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {5, 2, 9, 1};
    std::array<int, 4> a = {8, 3, 7, 4};

    std::sort(v.begin(), v.end());
    std::sort(a.begin(), a.end());

    for (int x : v) std::cout << x << ' ';
    std::cout << "| ";
    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';
}

1 2 5 9 | 3 4 7 8

The containers#

Sequence containers#

Elements are kept in the order you insert them.

Associative containers (sorted)#

Elements are kept sorted by key, implemented as balanced binary trees.

Unordered containers (hash tables)#

Elements are stored by hash, with no particular order, for very fast average lookups.

Container adaptors#

These wrap another container to provide a restricted interface.

Choosing a container#

Ask what you will do most often:

When unsure, start with std::vector. Its elements sit next to each other in memory, which modern processors read extremely fast; it often beats "theoretically better" containers for small and medium sizes.

Costs of common operations#

"Big-O" notation describes how the cost grows with the number of elements n:

* amortized: an occasional insert triggers a reallocation, but the average cost stays constant.

A taste of what the STL does for you#

Counting word frequencies, sorted by word, takes a few lines with a std::map:

#include <iostream>
#include <map>
#include <sstream>
#include <string>

int main() {
    std::string text = "the cat and the hat and the bat";
    std::map<std::string, int> counts;

    std::istringstream words(text);
    std::string word;
    while (words >> word) {
        ++counts[word];
    }

    for (const auto& [w, n] : counts) {
        std::cout << w << ": " << n << '\n';
    }
}

and: 2
bat: 1
cat: 1
hat: 1
the: 3

counts[word] creates the entry with value 0 the first time a word appears, then ++ increments it.

Where to go next#

• Iterators: how algorithms move through containers.
• map, set and unordered_map: fast lookups.
• stack, queue and priority_queue: ordered processing.
• Algorithms: sorting, searching, counting and transforming without writing loops.

Key takeaway#