The std convention is to have the last iterator point beyond the last element
I think I can help your mental model by giving you two little replies
(one section each).
- Don't think of it as beyond-last indexing, think of it as edge-based indexing
- Why edge-based indexing (right-open interval indexing) is nice
Don't think of it as beyond-last indexing, think of it as edge-based indexing
I've substantially simplified and C++ified this section thanks to a very helpful comment by
C++ iterators are defined in terms of "which item will it retrieve next" instead of "to which item is it currently pointing?
So, it helps me to think of an iterators as resting not on an item, but on the edge just before it.
For sub-sequences with a start and a stop, instead of numbering the
items, I mentally number the edges between the items. 0 is the edge
before the first item. The
startIt is the edge I start at; the
stopIt is the edge I stop at.
The following picture is adapted from An informal introduction to Python.
item 0 1 2 3 4 5
| P | y | t | h | o | n |
iterator 0 1 2 3 4 5 6
startIt = 2 and
stopIt = 5 leads to
t, h, o.
Why edge-based indexing (right-open interval indexing) is nice
You get some really nice properties:
- number of items in a subsequence:
n = stop - start
- To create neighbouring subsequences,
stop of one == start of the next.
Examples below. I'm using Python syntax below because I don't know C++.
If somebody is willing to translate this section into C++ (Don't bother
leaving the Python), I will be very grateful. Anyway, the notation is
not important: just read
This is the container we'll be using
my_container = [ 'a', 'b', 'c', 'd' ]
## edges ^ ^ ^ ^ ^
## 0 1 2 3 4
Access sub-sequences by slicing like
c[start:stop] -- you get
everything between edges 1 and 3.
my_container[1:3] == ['b', 'c']
To get a slice of length 3, I make sure stop = start + 3
my_container[1:4] == ['b', 'c', 'd']
# or do stop - start to find out how long the slice is:
4 - 1 == 3 # 3 elements in this slice.
I want one slice to start where the previous slice ends. So, I let the first
slice end on edge x, and the second one start on edge x. This way I
cleanly split the container in two.
my_container[0:3] == ['a', 'b', 'c']
my_container[3:4] == ['d']
Do read the essay by Edsger W. Dijkstra in
It's less than 700 words, with crystal-clear thinking and equally-clear
handwriting (and a link to a html version inside).