The list Container

Suppose you already know how to add an element to the end of one kind of container, and now you need to use a different kind. Do you have to learn a completely new vocabulary for the second one, or does the vocabulary carry over? The standard library answers this question in a specific way, and the answer shapes how you read almost any container code you meet.

The short answer is that the vocabulary carries over. The standard containers, such as vector and list, are built so that their basic operations look alike when you write them down. A call that works on one container is written with the same name and the same shape of syntax on another, so you can read the code without first checking which container you are looking at. This shared notation is deliberate.

An operation named for finding the start of a sequence means the start of the sequence whether the container underneath is a vector, a list, or another container type. What differs between containers lies in how each one stores its elements, not in what the basic operations are supposed to mean. So when you see begin(), push_back(), size(), or end(), you can rely on the idea behind the name even before you know the container's internal layout.

begin() and end() are best read together. begin() gives an iterator to the first element, and end() gives an iterator to the position one beyond the last element. Together they mark the boundaries of the whole sequence: the first position you can visit, and the position where a walk through the elements stops.

Notice that end() is not an element you can read. It is a marker that sits past the final element. Because it works as a stopping point for a walk through the container, it is described as one-beyond-the-last rather than as the last element. Picture the elements as a row of slots: begin() points at the first slot, and end() points at the empty slot just after the final one.

push_back() adds an element to the end of a container, and size() returns the number of elements. Together these two operations let you watch a container change. Each push_back() call grows the container by one element at its end, and size() reports the new count afterward.

Uniformity has conditions. An operation applies where it makes sense and can be efficiently implemented. This means that a shared name does not guarantee identical cost everywhere. The name tells you what the operation is meant to do; it does not promise that every container will do it at the same price.

Read this way, the conditions for a basic operation come down to two questions. First, does the operation make sense for this container? Second, can it be implemented efficiently for this container? When both answers are yes, the call reads the same as it would on any other standard container. When either answer is no, the shared name still tells you the intended meaning, but you should not assume the operation is equally suited to that container.