Sequences and Containers

Suppose you have a container full of values and a task to perform on them. Sometimes the task looks as if it should change how many values the container holds. You might want to add a new value at the end, or drop a value you no longer need. It is natural to wonder whether the algorithm doing the work can simply grow or shrink the container as part of the job. This article explains why that is not automatic, and how the two kinds of work differ.

The source for this topic makes one central point: changing what is stored and changing how many elements are stored are different jobs. Algorithms such as replace() and sort() can change element values without changing the number of elements. Keep that idea in mind as you read, because the rest of the article follows from it.

An algorithm works on a sequence of elements. The sequence is the run of positions it reads and, when the operation requires it, writes. The algorithm is handed a range of positions, usually described by a beginning and an end, and it moves through that range doing its work. This is the whole of what it knows about the data.

Here is the key consequence. A sequence does not identify the container that holds its elements. The algorithm gets a view of the positions, not a handle to the container object itself. So when an algorithm finishes, it has no built-in way to say that the container should now have more positions or fewer. Changing a value at a position is possible because the position is right there in the range. Changing how many positions exist is a different action on a different object, and the sequence alone does not provide it.

Read the diagram from the bottom up. The algorithm reaches the elements through the sequence. The container holds the elements, and nothing in the sequence points back to the container. Because of that missing link, the algorithm can rewrite the values it reaches, but it has no route to alter the container's count.

The source gives a practical test for telling these apart. The distinction is useful whenever an operation's result seems to require a different number of elements. If the task is to change values, an algorithm such as replace() or sort() may be suitable. If the task is to add or remove elements, the operation must also have a way to act on the container itself.

Sometimes an algorithm does need to add elements, and the task is best done with an algorithm rather than a loop you write by hand. The source handles this with the back_inserter. Its role is to act as the missing connection between an algorithm and the container that should grow. Without a way to refer to the container, the sequence alone does not tell the algorithm where added elements belong.

Think of the back_inserter as an adapter placed where the algorithm writes its output. Each time the algorithm produces a value, that value is handed to the back_inserter, which adds it to the end of the container. The algorithm itself still works on a sequence, but the back_inserter gives it a way to reach the container when new elements need a home.

Read the flow from left to right. The copy-style algorithm takes each value from the source and writes it through the back_inserter. Each write is routed to a push_back() on the destination, which appends the value. Because every write appends one element, the destination grows as the copy proceeds. The growth comes from the connection, not from the algorithm knowing anything about containers.

When you are adding or removing elements directly, you do not need an algorithm in the middle. The source names two direct container operations: push_back(), which adds an element to the end of the container, and erase(), which removes elements. You call these on the container itself, so they can change the element count as part of their own action.

The following example is an original illustration built to follow the rule from the source. It uses a container of three values and a replace() call that changes every 3 to a 9. Trace what happens to the values and to the size.

Compare the two states in the diagram. Positions 1 and 3 changed, and position 2 did not. The number of positions stayed at three in both states. That is the behavior the source describes: replace() changes element values without changing the number of elements.

Once you know the distinction, the choice of tool follows from the task. Start by asking whether the operation must change the number of elements. If it only needs to change values, an algorithm such as replace() or sort() is a suitable choice, and it does not need a container operation at all. If the task must add or remove elements, the operation needs a way to act on the container itself.