Specialized Containers in C++

Most of the standard library's containers follow one familiar pattern. They hold elements and provide a common way to work with them. That shared pattern is what lets a programmer learn one container and carry much of that knowledge to the next. Some types in the library also hold elements, yet they do not fit the pattern cleanly. This article is about those types and about the wider family of specialized containers that the standard library provides.

The source names three examples of almost containers: built-in arrays, std::array, and std::string. Each one stores elements, so each counts as a container in the broad sense. Each one also departs from the common STL pattern, and the departure is the reason it is grouped separately.

Why group these types separately at all? The source gives a practical reason. If the general rules of the STL had to absorb every exception, the description of the framework would become harder to follow. Describing the almost containers on their own keeps the description of the STL itself simpler.

A reasonable question follows from the list of almost containers: why does the standard library provide so many containers at all? The source answers that the library's containers serve common needs. Those needs are common, but they are also different from one another, and they often overlap. If the library did not supply these containers, many programmers would have to design and implement their own versions.

The source explains why one container cannot answer every need. Some needs contradict each other. It gives two pairs of conflicting requirements. The first pair is the ability to grow set against being guaranteed to be allocated in a fixed location. The second is elements not moving when new elements are added set against elements being contiguously allocated. A single general-purpose container that satisfies both members of either pair is not possible.

There is a second reason as well. A very general container would carry overhead that is unacceptable for many individual uses. Specialized containers exist so that each one can provide the services a particular group of programmers needs without paying for services it does not need. This is why the library is organized as a set of specialized containers rather than a single all-purpose one.

Rather than memorizing the specialized containers as a flat list, it helps to sort them by three characteristics: the kind of elements they hold, how those elements are allocated in memory, and how elements are accessed. Each characteristic is a question you can ask of any container. The three answers together form a profile that makes a container easier to remember and easier to choose.

Applying the three questions one container at a time shows how the characteristics combine. Work through each container below, answering the element type question, then the allocation question, then the access question.

The characteristics are most useful when applied to a concrete need. The scenario below is an original illustration built on the three characteristics. It is not taken from the source. Imagine you must store a single record that holds a name and a count, where the two values are of different types. The first question decides the search: because the elements are of mixed types, a homogeneous container is not the right starting point.

Following the sketch, the mixed-type requirement leads to pair or tuple, both of which the source calls heterogeneous. Pair is the simpler choice when only two values are stored. The flowchart is a simplified reading of the source's three characteristics rather than a complete selection rule, so a real decision should also weigh the conflicting requirements discussed earlier.