The vector 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.

In this article, the vector container is the running example. A vector and a list are two standard containers that hold elements. The point to learn is that the same operation names appear on both, and the same names carry the same meanings. Once you can trace what the four basic operations begin(), end(), push_back(), and size() do to a vector, you will be able to read the same calls on other containers without first checking which container you are looking at.

Start with an empty vector and then store three elements in it: red, green, and blue. The two operations begin() and end() are best read together. begin() gives an iterator to the first element. 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.

Read the diagram from left to right. The begin() position lands on the first stored element, red. The end() position sits after blue, the last stored element, and it does not hold a value of its own. That is why end() is described as one-beyond-the-last rather than as the last element. Because it sits past the final element, it works as a stopping point for a walk through the container: you move forward from begin() and stop when you reach end().

The standard containers 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. The notation is deliberately shared.

Sharing a notation is only half of the design. The meaning of each shared operation is also equivalent across containers. 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.

Read the two columns row by row. Each row holds one operation name, and the meaning in each row is the same in both columns. The column headings are the only things that change. This is the practical benefit of the design: knowing what begin() means on a vector tells you what begin() means on a list.

push_back() adds an element to the end of a container, and size() returns the number of elements. The two work together: each push_back() call grows the contents by one element at the end, and a following size() call reports the new count. The next diagram traces three calls on an initially empty vector.

Uniformity has conditions. An operation applies where it makes sense and can be efficiently implemented. A shared name therefore does not guarantee identical cost everywhere. The same name written on two containers means the same thing, but the operation may be easy on one container and expensive on another, or it may not be expected to apply at all.

Read the flowchart as a checklist. First ask whether the operation makes sense for the container you are using. If it does not, the shared name gives you no reason to expect it to apply. If it does, ask whether it can be implemented efficiently there. Only when both answers are yes is the operation expected to apply with its shared meaning. A yes on the first question and a no on the second still leaves you with the same name and meaning, but with a different cost.

The vector container shows the design of the standard containers in a concrete form. Its operations are written with the same names as those of other containers, and those names carry equivalent meanings. begin() and end() mark the first element and the position one beyond the last, push_back() grows the contents at the end, and size() reports how many elements are stored. Each of these operations is expected to apply where it makes sense and can be efficiently implemented, which means that a shared name does not promise identical cost everywhere.