8

Suppose we have an array named data of size 5. If we pass this array as an argument to std::end function like

int *ptr = std::end(data);

It will return a pointer pointing to the memory location one past the last element in the array.

Question

What's the point of having a pointer pointing to the memory location one past the last element in the array? Why not just point to the last element in the array?

Niall
  • 30,036
  • 10
  • 99
  • 142
  • 4
    Because of uniformity. This way all iterators act the same across all sorts of different containers. And many containers don't provide random access as array and vector do. This would make `i != j` the only option and `i < j` impossible. – DeiDei Feb 05 '17 at 18:27
  • Because in C++ you usually express ranges with half-closed intervals, which have many convenient properties; in this notation, the range that covers a whole container is [begin, end), with end being one element after the last. – Matteo Italia Feb 05 '17 at 18:30
  • It also makes it easy to check that a range is nonempty: `while (ptr != end(data)) ...` – Greg Kikola Feb 05 '17 at 18:31
  • 1
    It also gives a valid range for an empty sequence, where `end` is the same as `begin`. – Bo Persson Feb 05 '17 at 18:31
  • 2
    Uisng the first possible non-valid location for a given container as the "end" location greatly simplifies looping, too. Using a container that supplies a `ForwardIterator`, for example, you can take any valid iterator for that container, and increment that iterator to loop over the container's contents until you reach the "end" iterator, because all iterators between your starting iterator and the "end" iterator are guaranteed to be valid for that container unless an action is taken that invalidates them. – Justin Time - Reinstate Monica Feb 05 '17 at 18:45
  • This concept is also easily extended to any range in general, where using the first iterator past the end of the range as the "end" iterator guarantees that for any starting iterator `s`, all iterators between `s` and `end` (including `s`) are guaranteed to be valid for that range (unless, of course, they're explicitly invalidated). – Justin Time - Reinstate Monica Feb 05 '17 at 18:51
  • Possible duplicate of [What does"one-past-the-last-element" mean in vectors?](http://stackoverflow.com/questions/34830192/what-doesone-past-the-last-element-mean-in-vectors), [What is the past-the-end iterator in STL C++?](http://stackoverflow.com/q/15252002/608639), [Why are Standard iterator ranges [begin, end) instead of \[begin, end\]?](http://stackoverflow.com/q/9963401/608639), [What if I increment an iterator by 2 when it points onto the last element of a vector?](http://stackoverflow.com/q/1057724/608639), etc. – jww Feb 19 '17 at 07:40

1 Answers1

8

To be able to tell an "empty" container/sequence from one with elements in it.

If a container is empty, a pointer to its first element would be one past the end, the same as the "end" location.

A NULL pointer could also have been used, but since iterators are necessarily pointers, the NULL would not apply. The default value for the iterator could also be used. In generic programming, how would the "default" be determined uniformly across all types (bear in mind pre C++98 implementations here)?

Not all sequences/containers, are contiguous in memory, any attempt to use a comparison such as operator < would not be suitable. The use of equality (or inequality), operators == and != is required, so a single point (or element) is needed to indicate the last element; the "one past the end" solves that.

For uniformity, the "end" is chosen as one past the end; it solves a lot of the issues and brought power to the STL. The half closed interval has become the norm in C++.

On a side note, the ranges library and techniques shines another light on the matter, but this was not around when the foundation for the STL was laid out.

Another side note; not all sequences correlate to a container, some sequences that are required to be iterated over are only a portion of the original container or sequence, the half closed interval offers a uniform technique to access the sequence, independently of where it is in the original container/sequence.

Related.

Community
  • 1
  • 1
Niall
  • 30,036
  • 10
  • 99
  • 142