Containers and Algorithms in the Standard Library

The C++ standard library is large. It contains facilities for memory allocation, text handling, input and output, data collections, mathematics, concurrency, and more. A programmer who meets this collection for the first time can easily feel overwhelmed, because the individual names do not explain how they relate to one another. Knowing a name such as the one for a container tells you very little about where it fits among the other facilities.

Before reading on, try a small exercise. Imagine you are designing a library that programs could build on. What kinds of help would you expect it to offer? Keep your answer in mind. The categories you are about to see are the standard library's own answer to that question, and comparing your list with theirs is a useful check on your intuition.

The standard library solves the overwhelm problem in its own documentation by classifying its facilities into groups. Once you know the groups, a new facility has a place to live in your mental map, and you can predict roughly what it is for before you read its details. The goal of this article is not to memorize every facility. It is to build a picture of the whole library that you can keep returning to as you learn each part in more depth.

The source describes the standard library as a set of facilities that can be classified into eleven groups: run-time language support, the C standard library, strings, regular expression matching, I/O streams, containers and algorithms, numerical computation, concurrent programming, template metaprogramming, smart pointers, and special-purpose containers. Each group answers a different kind of need. Some support the language machinery underneath every program, some support handling text and data, and some support building larger or more general code.

The diagram shows the eleven groups as siblings under one library. They are not stacked on top of one another. Each is a separate kind of support that the library offers. Read the sublabels as a rough orientation: they name the role each group plays, drawn from what the source says about each one, and the rest of this article explains those roles in turn.

The first two categories form the foundation on which the rest of the library rests. Run-time language support provides facilities for allocation and for run-time type information. Allocation is the act of obtaining memory while a program runs. Run-time type information lets a program inspect type information while it executes. These are facilities the language needs in order to operate, which is why they are grouped first. You rarely make them the main topic of a program, but many other facilities depend on them.

The second foundational category is the C standard library. The source states that it is included in the C++ standard library with very minor modifications, and that those modifications exist to minimize violations of the type system. This tells you something about the design. The C++ library did not discard the older C facilities. It adapted them so that they fit the stricter type rules of C++ as closely as possible.

The worked example above can be turned into a sequence of questions. Each question checks the purpose of the facility against one family of groups. The flowchart below follows that sequence. A facility leaves the chain at the first question it answers yes, and the order of the questions reflects the order in which the source introduces the groups: foundations first, then text, then data, then advanced concerns, and finally the narrower special-purpose containers.

Follow the chain with the example from the previous section. The first question, whether the facility supports the language machinery, gets a no, because regular pattern searching does not allocate memory or inspect types. The second question, whether the facility handles text or I/O, gets a yes, and the chain ends in the text groups. Notice that the chain never asked about the facility's name. Every question was about what the facility does.

A useful distinction runs across the eleven groups. Some facilities support the language itself: the machinery under every program, such as allocation and run-time type information, and the C standard library that the C++ library adapts. Other facilities support everyday programming tasks: storing and searching text, moving data through input and output, and organizing data in collections. The first kind is rarely the main subject of a program. The second kind is used constantly.

Many programs spend much of their time with text, so the source groups three related kinds of support together: strings, regular expression matching, and I/O streams. These categories are about how a program stores character data, how patterns are matched inside that data, and how data moves in and out of a program. They are separate because each answers a different question.

The next two categories cover organizing data and computing with it. Containers and algorithms, the STL, and numerical computation are both large and used constantly, which is why they are often the first parts of the library that programmers learn in depth. The last three categories address more advanced concerns: concurrent programming for running work at the same time, template metaprogramming for code that works across many types, and smart pointers for managing resources so that they are handled correctly.

The final group is special-purpose containers. The source lists three: array, bitset, and tuple. All three are containers, but the word special-purpose signals that each serves a narrower role than the general containers of the STL. The source records what each one is for in a separate table, which is the best place to look up the details of a specific member of this group.