Understanding Container Algorithms
The pair of iterators is the whole definition of a sequence. Nothing else is needed to say which values an algorithm should consider.
Why Algorithms Need a Precise Group
When you write an algorithm, you usually want it to work on a group of values rather than on one value at a time. Before you can design that algorithm, you need a precise answer to a simple question: exactly which group of values will the algorithm work on? In this part of the course, that group is called a sequence. A sequence is the unit an algorithm is applied to, and understanding how it relates to the containers that hold data is the first step toward writing algorithms that work across many different kinds of storage.
This article follows one idea from start to finish: a sequence is not a special object with its own fields. It is the stretch of values between two positions, and those two positions are what you hand to an algorithm. Once you can trace which values fall between two boundaries, the rest of the topic follows naturally.
Predicting Which Values an Algorithm Sees
What do you think happens?
A container holds five values at positions 0 through 4. A sequence is given with begin at position 1 and end at position 4. Before reading on, which values do you think the algorithm will process?
Reveal answer
The values at positions 1, 2, and 3, with position 4 left out
The pair of positions is written as a half-open range: the begin position is included and the end position is excluded. That is the rule the rest of this article builds on.
A Sequence Is Defined by Two Boundaries
A sequence is defined by a pair of iterators written as $[\text{begin} : \text{end})$. The begin iterator marks the first position in the sequence, and the end iterator marks the position just past the last element. The sequence is the stretch of values between those two boundaries.
The square bracket on the left means the begin position is included in the sequence. The round bracket on the right means the end position is not included. This is why the notation is called half-open: one boundary belongs to the range and the other does not. The end position is still a meaningful location, because it marks where the sequence stops, but no element at that position is part of the sequence.
The pair of iterators is the whole definition of a sequence. Nothing else is needed to say which values an algorithm should consider.
Tracing Coverage from Begin and End
To trace a sequence, start at the begin position, walk forward one position at a time, and stop as soon as you reach the end position. Every position you visited before reaching end is covered; the end position itself is not. The diagram below shows this for a container of five values with begin at position 1 and end at position 4.
Tracing a Range from Begin and End
A container holds five values at positions 0 through 4: 10, 20, 30, 40, and 50. The sequence is given by begin at position 1 and end at position 4. Which values does the sequence cover?
- 1Read the begin boundary
Begin is position 1, so the first covered element is the value at position 1, which is 20.
- 2Read the end boundary
End is position 4. It marks where the sequence stops, so the value at position 4 is not part of it.
- 3Collect the positions in between
Starting at begin and stopping before end gives positions 1, 2, and 3.
- 4Map positions to values
Position 1 holds 20, position 2 holds 30, and position 3 holds 40.
The sequence covers the values 20, 30, and 40. The values 10 and 50 lie outside the range.
Empty Sequences When Begin Equals End
Because the begin position is included and the end position is excluded, a sequence whose begin and end point to the same position covers nothing. The notation $[\text{begin} : \text{begin})$ includes no positions at all. This is the empty sequence. It is still a valid sequence, and an algorithm given it simply has no values to process.
Container and Sequence Are Not the Same Thing
The two ideas are easy to blur together, because in practice a container and its contents are usually handled as one thing. Separating them clarifies what each one does. A container is the holder of contents. A sequence is a definition of which contents an algorithm should consider, given by a pair of iterators.
Notice the direction of the relationship. The container is where the data lives. The sequence is not a second copy of that data; it is a way of naming a stretch of it. This is why algorithms are most often applied to sequences that are the contents of a container: the container supplies the values, and the iterator pair tells the algorithm which ones to process.
| Aspect | Container | Sequence |
|---|---|---|
| Role | Holds the contents | Describes which contents to consider |
| What defines it | Its stored values | A pair of iterators, begin and end |
| Copies data | It is where the data lives | No; it names a stretch of existing data |
| Requirement | Is a specific holder of values | Is general and does not require a particular container |
| Typical use with algorithms | Supplies the values | Is the unit an algorithm is applied to |
Container and sequence compared. The sequence is the more general idea, though it is most often used with a container.
Mistakes Learners Make with Ranges
Common mistake Treating the end position as part of the sequence
What it looks likeWith begin at 1 and end at 4, including the value at position 4 and reporting 20, 30, 40, and 50.
Why it failsThe end position is excluded by the half-open notation $[\text{begin} : \text{end})$.
Do this insteadStop collecting positions just before end. For begin 1 and end 4, the covered positions are 1, 2, and 3.
Common mistake Assuming a sequence is a separate copy of the data
What it looks likeBelieving that building a sequence duplicates the stored values before an algorithm runs.
Why it failsA sequence is a way of naming a stretch of the container's data, not a second copy of it.
Do this insteadThink of the iterator pair as a pointer to a region of existing values, and of the container as the place the values are stored.
Common mistake Thinking an empty range is an error
What it looks likeExpecting a failure when begin and end point to the same position.
Why it failsEqual boundaries include no positions, which is a valid empty sequence.
Do this insteadRecognize that an empty sequence simply means the algorithm has no values to process.
Common mistake Confusing the container with the sequence when describing what an algorithm works on
Reading Ranges Carefully
When you design an algorithm, describe its input as a sequence defined by a begin and end. This keeps the algorithm independent of how the values happen to be stored, which is the flexibility the source highlights.
Practicing Range Tracing
A container holds five values at positions 0 through 4: 10, 20, 30, 40, and 50. A sequence is defined with begin at position 0 and end at position 3. Which values does the sequence cover, and which position is excluded?
Hints
- Start at the begin position and walk forward one position at a time.
- Stop before you reach the end position; the end position itself is not covered.
- Position 3 is the end, so the positions covered are 0, 1, and 2.
Key Takeaways
- A sequence is defined by a pair of iterators written as $[\text{begin} : \text{end})$, in which begin is included and end is excluded.
- To find the covered elements, start at begin and stop just before end; equal begin and end positions give an empty sequence.
- A container holds the contents, while a sequence is a definition of which contents to consider; the sequence does not copy the data.
- Algorithms are most often applied to sequences that are the contents of a container, because the container supplies the values and the iterator pair selects which ones to process.