What Does the Standard Template Library Give You?

The Standard Template Library gives you four things that work together: **containers** that store data, **iterators** that walk over it, **algorithms** that operate on it through those iterators, and **function objects** that let you pass behaviour in as a parameter. Because every container provides the same iterator interface, a single algorithm can sort a vector, a list and a deque without knowing which it has.

The four parts of the STL

The library is built around one idea: separate *what* you are storing from *what* you want to do with it.

• Containers — std::vector, std::list, std::map, std::set, std::deque, std::array, and more.
• Iterators — the uniform way to walk a container. Each container defines a type that behaves like a pointer.
• Algorithms — std::sort, std::find, std::transform, std::accumulate and hundreds more, written once for every container.
• Function objects — classes with an operator(), so a behaviour can be passed around like a value.

Because the algorithms only know about iterators, they work with any container that provides the right kind of iterator.

Containers hold your data

The container you choose depends on how you access the data.

#include 
#include 
#include 
#include 
#include 
#include 

int main() {
    std::vector parcels = {"p-001", "p-002", "p-003"};
    std::list route = {4, 2, 9, 7};
    std::set zones = {1, 2, 3, 3, 3};
    std::map weights = {{"p-001", 4}, {"p-002", 11}};

    std::cout << "parcels: " << parcels.size() << '\n';
    std::cout << "route:   " << route.size() << '\n';
    std::cout << "zones:   " << zones.size() << '\n';
    std::cout << "weights: " << weights.size() << '\n';
    return 0;
}

The output shows the sizes, and the set has collapsed the repeated zone number:

parcels: 3
route:   4
zones:   3
weights: 2

The container that fits the access pattern is the one that performs best: a vector for random access, a list for cheap insertion in the middle, a map for lookup by key.

Iterators walk the containers

Every container provides .begin() and .end(), and those return iterators. The iterator supports * to read the current element, ++ to move to the next, and comparison to test whether you have reached the end.

#include 
#include 
#include 

int main() {
    std::vector parcels = {"p-001", "p-002", "p-003"};

    for (auto it = parcels.begin(); it != parcels.end(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << '\n';

    for (const std::string& parcel : parcels) {
        std::cout << parcel << ' ';
    }
    std::cout << '\n';
    return 0;
}

Both loops print the same thing:

p-001 p-002 p-003 
p-001 p-002 p-003

The second form is the range-based for, which is the same thing written more readably.

Algorithms work through iterators

An algorithm takes a range — a pair of iterators — and does something with it.

#include 
#include 
#include 
#include 

int main() {
    std::vector weights = {12, 4, 30, 8};

    std::sort(weights.begin(), weights.end());

    std::cout << "sorted: ";
    for (int weight : weights) {
        std::cout << weight << ' ';
    }
    std::cout << '\n';

    auto middle = std::find(weights.begin(), weights.end(), 12);
    if (middle != weights.end()) {
        std::cout << "found 12 at position "
                  << (middle - weights.begin()) << '\n';
    }
    return 0;
}

The output shows the sorted weights and the position of the search:

sorted: 4 8 12 30 
found 12 at position 2

Notice that std::find knows nothing about the vector. It takes two iterators and returns an iterator, and the same call works on a list or a set.

Function objects pass behaviour in

Some algorithms need to know *how* to compare or *what* to compute. A lambda or a function object supplies that.

#include 
#include 
#include 
#include 

int main() {
    std::vector parcels = {"p-003", "p-001", "p-012"};

    std::sort(parcels.begin(), parcels.end(),
              [](const std::string& left, const std::string& right) {
                  return left.size() < right.size();
              });

    for (const std::string& parcel : parcels) {
        std::cout << parcel << ' ';
    }
    std::cout << '\n';
    return 0;
}

The output shows the parcels sorted by the length of their identifier:

p-003 p-001 p-012

Headers and namespaces

The STL lives in the std namespace and in a handful of headers.

• <vector>, <list>, <deque>, <map>, <set>, <array> — containers.
• <algorithm> — the non-member algorithms.
• <iterator> — iterator adapters and std::back_inserter.
• <functional> — std::function, std::bind and the function object wrappers.
• <numeric> — std::accumulate, std::iota and friends.

Including a header gives you the declarations, not the definitions, so the compiler only pays for what you use.

What the STL deliberately leaves out

Two things are worth knowing before you start.

First, the STL containers are not thread-safe. Sharing a vector between threads requires external synchronisation.

Second, the standard library does not include a matrix, a graph, a date and time type or a regular expression engine in the core language. Some of those are available in other libraries, and dates and times in particular have their own well-known library.

The generic algorithm pattern

The pattern to remember is this: to write an algorithm that works with any container, write it in terms of iterators.

#include 
#include 
#include 
#include 

template 
int count_long(const Container& container, std::size_t minimum) {
    int count = 0;
    for (const auto& element : container) {
        if (element.size() >= minimum) {
            ++count;
        }
    }
    return count;
}

int main() {
    std::vector parcels = {"p-1", "p-22", "p-333"};
    std::list route = {"r-1", "r-4444"};

    std::cout << "vector: " << count_long(parcels, 4) << '\n';
    std::cout << "list:   " << count_long(route, 4) << '\n';
    return 0;
}

The output shows one template handling two different container types:

vector: 2
list:   1

Quick reference

• The STL has containers, iterators, algorithms and function objects.
• Containers are chosen by access pattern; algorithms are chosen by operation.
• Every container provides .begin() and .end(), and algorithms work on those.
• The same algorithm works on any container with the right iterator category.
• Lambdas and function objects let you pass behaviour into an algorithm.
• Write your own algorithms in terms of iterators so they work with everything.

Try it yourself: store a set of parcel records in a [[std::vector]], then sort them with [[std::sort]] using a custom comparator, then use [[std::find]] to locate one and [[std::accumulate]] to total a field. Next, move the same records into a [[std::map]] keyed by identifier and repeat the total with a loop over the map.