Container Characteristics in the STL

Most of the standard library's containers follow one familiar pattern: they hold elements and give you a common way to work with them. You learn the pattern once and it applies across many types. But some types in the library hold elements too, and yet they do not fit that pattern cleanly. This article is about those types and about the larger question they raise: why does the library offer so many containers in the first place, and how do you choose among them?

The key phrase is 'holds elements and is therefore a container.' Membership in the group does not depend on whether a type is useful or famous. It depends on two things together. First, the type stores a collection of elements. Second, it is shaped differently from the typical STL container, usually because of a restriction it places on how it can be used or because of an extra facility it adds. The difference is what makes it 'almost' a container rather than a full one.

The source names three examples: built-in arrays, the array type, and the string type. Each holds elements, and each is shaped differently from a typical STL container. Built-in arrays are the arrays that come with the core language rather than with the library. The array type is a library type for holding a sequence of elements. The string type holds characters. Listing them under one label lets the description of the STL itself stay simpler, because the general rules of the framework do not have to absorb every exception.

A natural question follows from the list of almost containers: why does the standard library provide so many containers at all? The source's answer is that they serve common needs. Those needs are common to many programmers, but they differ 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 of the same structures.

The reason one container cannot cover every need is that some needs contradict each other. The source 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 pair 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. The diagram below lays out these conflicts.

There is a second reason as well, and it concerns cost rather than possibility. 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. Read this way, the variety of containers is a design choice that trades one general tool for several focused ones.

The source describes the specialized containers as providing services needed by large communities of programmers. Rather than memorizing them 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. The concept map below shows how these three axes divide the specialized containers. After it, each axis is explained in turn.

The classification is most useful when it is applied to a concrete need. The flowchart below turns the three questions into a sequence: first ask about element types, then about bits, then about allocation. The scenario that follows is an original illustration built on the characteristics in the table, not an example taken from the source.