The STL in One Picture: Four Kinds of Thing

Maria has a C program that keeps a shop's price list. It has a hand-written growing array, a hand-written linked list and a hand-written sort. It is about 300 lines long, and it has two bugs she has not found yet.

The same program in C++ with the STL is about 40 lines. The two bugs are gone. Nobody fixed them: the lines that held them no longer exist, because the growing array, the list and the sort now come from the library.

Maria asks the question this whole module answers: "But why should I trust code I did not write?" Before we answer it, you need the map. This lesson is the map.

What the STL is, in one sentence

The STL (Standard Template Library) is the part of the C++ standard library that provides containers, iterators, algorithms and function objects, built to fit together.

The standard library is the code that ships with every C++ compiler, the way printf and qsort ship with every C compiler. You do not download it. You include a header and use it.

The design came from Alexander Stepanov, working with Meng Lee at Hewlett-Packard. The C++ standards committee voted it into the draft standard in 1994. It has been part of every C++ standard since the first one, C++98. The word "Template" in the name means the same code works for any type of element. Module 1 shows you what that means in practice.

So the STL is not a separate product. It is a set of headers, such as <vector> and <algorithm>, that your compiler already has.

The picture: four kinds of thing

Everything in this track belongs to one of four kinds. Learn this picture now. Every later module adds detail to one of its boxes, and you will see it again at the top of each one.

Read the arrows from left to right. A container hands out iterators. Two iterators mark a stretch of elements, called a range. An algorithm works on that range, and a function object, when you pass one, tells the algorithm how to compare or what to do.

So the four kinds are not four piles of features. They are four parts of one machine, and the iterator is the part in the middle that lets the other three meet.

std::sort(prices.begin(), prices.end(), std::greater<int>());

Containers hold things

A container is an object that holds a collection of elements and manages their memory for you. You add to it and remove from it. It grows and shrinks on its own, so you never call malloc or free for it.

std::vector is the one you will use most. It is a growing array: the elements sit next to each other in memory, just like a C array, and you can still write v[0].

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> scores;
    scores.push_back(72);
    scores.push_back(45);
    scores.push_back(90);
    std::cout << "I hold " << scores.size() << " scores\n";
    std::cout << "The first is " << scores[0] << '\n';
}

I hold 3 scores
The first is 72

Iterators point into containers

An iterator is an object that points at one element of a container and can move to the next one. If you know C pointers, you already know the idea: *it reads the element it points at, and ++it moves it forward.

Every container hands out two of them. begin() points at the first element. end() points one step past the last element, a position with nothing in it. Lesson 4 explains why that is the right choice.

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> scores = {72, 45, 90};
    std::vector<int>::iterator it = scores.begin();
    std::cout << *it << '\n';
    ++it;
    std::cout << *it << '\n';
}

72
45

Algorithms work through iterators

An algorithm is a function template in <algorithm> (or <numeric>) that does one job on a range: sort it, search it, count in it, reverse it. There are more than a hundred of them.

Here is the important part. An algorithm takes two iterators, not a container. It never asks "is this a vector?". It only walks from the first iterator to the second. That is why one std::sort works on a vector, on a plain array and on containers that were written years after it.

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

int main()
{
    std::vector<int> scores = {72, 45, 90, 45, 61};
    std::sort(scores.begin(), scores.end());
    std::cout << "sorted:";
    for (int s : scores) std::cout << ' ' << s;
    std::cout << '\n';
    std::cout << "45 appears " << std::count(scores.begin(), scores.end(), 45) << " times\n";
}

sorted: 45 45 61 72 90
45 appears 2 times

Function objects tell an algorithm how

A function object (also called a functor) is anything you can call like a function. You pass one to an algorithm to change how it does its job. std::sort puts the smaller element first by default; give it std::greater<int>() and it puts the bigger one first.

In C you did the same thing with a function pointer, the comparator you pass to qsort. A function object does that job, with the type checked by the compiler. The most common kind today is a lambda, a small function written right where you need it. Module 12 teaches lambdas; here you only need to recognise one.

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> scores = {72, 45, 90, 61};
    std::sort(scores.begin(), scores.end());
    std::cout << "smallest first: " << scores[0] << '\n';
    std::sort(scores.begin(), scores.end(), std::greater<int>());
    std::cout << "biggest first:  " << scores[0] << '\n';
}

smallest first: 45
biggest first:  90

All four in one program

Here is the core of Maria's rewrite: her price list, sorted from the most expensive down, with the top three printed. Point at each line and name its kind before you read the note under it.

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> prices = {450, 1200, 80, 990, 300, 640};
    std::sort(prices.begin(), prices.end(), std::greater<int>());

    std::cout << "Top three prices:\n";
    for (auto it = prices.begin(); it != prices.begin() + 3; ++it) {
        std::cout << "  " << *it << '\n';
    }
    std::cout << "Items over 500: "
              << std::count_if(prices.begin(), prices.end(), [](int p) { return p > 500; }) << '\n';
}

Top three prices:
  1200
  990
  640
Items over 500: 3

What the STL is not

Knowing the edges saves you a long search. Three things people expect to find in the STL are not there.

• Not a GUI library. There are no windows, buttons or images. Programs with a window use a separate library such as Qt.
• Not a network library. Standard C++17 and C++20 have no sockets and no HTTP. A server uses the operating system's calls or a library such as Boost.Asio.
• Not the whole standard library. Input and output (<iostream>), time (<chrono>), threads and files are standard library too. They are not the container, iterator and algorithm design this track is about.

One honest note on the name. Many programmers say "the STL" when they mean the whole standard library, and you will hear it used both ways. This track uses it for the four kinds above, plus std::string, which behaves like a container of characters.

std::vector<int> v = {3, 1, 2};
v.sort();

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {3, 1, 2};
    std::sort(v.begin(), v.end());
}

Next you will see why it is worth learning. Three programs are written twice, once in C and once with the STL, beside the costs nobody puts on the poster.