Standard Library Containers

Suppose you have written a routine that adds up the values in a collection. Today the values are whole numbers, so you write it for int. Next week you need the same total for decimal measurements, and after that for a grid of numbers that represents a matrix. Copying and editing the routine each time works, but it duplicates logic and invites mistakes. Generic programming asks a different question: can one algorithm be written once and still be correct for many kinds of data?

This article follows one thread from that question. First you will see what makes an algorithm generic, then how C++ templates support it, then what a container is, and finally how range checking protects you from asking a container for something it does not hold. Each stage builds on the one before it, so keep the question of valid inputs in mind throughout.

The word that carries the most weight in that definition is requirements. Generic does not mean that every type is automatically acceptable. It means the algorithm is written in terms of what it needs from its inputs rather than in terms of one specific type. If a type supplies what the algorithm needs, the same algorithm body can be used with that type. If it does not, the algorithm's requirements are unmet, and the type is not a valid argument.

In C++, the template is the main language feature that supports generic programming. A template lets you write an algorithm with a type that is not yet fixed. The algorithm is then used with particular concrete types. The source describes this as compile-time parametric polymorphism: one piece of code is written in a parameterized form, and the parameter, which is a type, is supplied when the code is used.

The adjective compile-time tells you when this happens. The choice of type is part of what the compiler works with, not something decided while the program runs. Because of this, one algorithm definition can serve many valid container and element combinations, and each combination that is used is prepared for that particular type when the code is compiled.

The diagram shows the relationship in words: the algorithm is defined once, and each element type that meets its requirement can be used with it. Notice that the algorithm does not change between these uses. Only the type it is applied to changes.

The source uses sum() as its main illustration. The sum() algorithm is generic in two dimensions at once, and each dimension can vary independently while the algorithm itself stays the same. The worked example below follows the reasoning for each dimension.

Notice what this example did not require. It did not need a separate sum() for vectors of int, another for lists of double, and another for matrices. The algorithm's requirements were the only thing that mattered, and those requirements are stated in terms of what the container and the element must support.

Many programs need to hold more than one value at a time. A list of student scores, a set of file names, or a queue of tasks all share the same need: a single object that holds a group of related items. A container is best understood as an object whose job is to hold other things. Those other things are its elements. The container is the outer thing, and the elements are the items inside it. One container can hold many elements, and the relationship is one to many.

Read the diagram from top to bottom. The container sits at the top, and each element hangs beneath it as one of the things it holds. Elements are what a container holds, which is why the two ideas are introduced together in the source.

The reason this check matters is that a request for a position is only useful when that position exists. Asking a container for something beyond the elements it holds is asking for something that is not there. Range checking is the habit of verifying the request before relying on its result.

Because out-of-range requests are cases you must handle, you should not assume the element exists. The check gives you the information you need to decide what to do next.

The example below is an original illustration, not taken from the source. It uses a container that holds five elements and numbers them 1 through 5 for the purpose of this example. The source does not fix a numbering scheme, so the numbers here are only a teaching device. The reasoning follows three steps: identify the range, compare the request against it, and decide.

Now change the request to a position inside the range. Take position 3. The same three steps apply: identify the range of positions 1 through 5, compare 3 against it, and decide. The comparison shows that 3 is at least 1 and at most 5, so the range check passes. The check did not change the container. It only answered whether the request pointed at something the container really holds.