1

Why is the prototypes for STL functions like this

template <class RandomAccessIterator>
void sort (RandomAccessIterator first, RandomAccessIterator last);

and not

template <class RandomAccessIterator,ConstRandomAccessIterator>
void sort (RandomAccessIterator first, ConstRandomAccessIterator last);

We must never write to the element represented by last. Yet the library requires functions to return the end iterator as non-const like this for a very simple array class:

T* Container::end()
    {
    return begin+N; //I will screw up the heap if I ever wrote to the address returned here!
    }

rather than the formally correct

const T* Container::end() const
    {
    return begin+N;
    }
user877329
  • 6,717
  • 8
  • 46
  • 88
  • You're not allowed to read that element either, so by your logic it shouldn't even return anything – M.M Dec 25 '14 at 20:57
  • 2
    The short version: `end[-1] = begin[0]` (if `begin != end`) is perfectly valid. – Dietmar Kühl Dec 25 '14 at 20:58
  • Somewhat related: [const and pointers in C](http://stackoverflow.com/q/27588918/978917). – ruakh Dec 25 '14 at 21:01
  • It seems to me that the iterator is passed by copy so the caller's constness is guaranteed to be preserved and there is no point adding a nedless restriction on the callee, given that the implementation may want to move the end parameter. – Galik Dec 25 '14 at 21:09
  • @Matt Well that’s not a very good reason because **if** that invariant could be statically enforced (without getting incompatible iterator types) that would be phenomenal. – Konrad Rudolph Dec 25 '14 at 21:37

2 Answers2

2

The primary reason STL uses one iterator type for the begin and the end of a range seems to be mostly a design preference of the creators, primarily of Alexander Stepanov. A secondary reason is that STL started out complex enough the way it is without dealing with different begin and end iterator.

Since, a lot was learned about uses of algorithms and it may be worth reconsidering whether the begin and end iterator should always use the same type, although probably not for the reason you quote: making the end iterator reference a constant object doesn't really help as you are neither allowed to read nor write it. Also, for bidirectional iterators it would be actively hostile to make the end read-only as it would be necessary to traverse the sequence with the start iterator to build a writable end iterator (for random access iterator you can obtain the end iterator in constant time from the begin iterator, i.e., it isn't much of an issue).

Note that merely using a different deduced type for the end iterator actually creates a huge amount of flexibility which is way more than creating a read-only version of the iterator. To just add constness to the iterator type of the begin you'd rather use something along the lines of

template <typename RndIt>
void sort(RndIt begin, typename iterator_traits<RndIt>::const_iterator);

Of course, that doesn't work right now and, as mentioned above, it would be a bad idea: you definitely want to be able to use both iterators to write to in algorithms, although you'd obviously not write through the end iterator.

The reason to make the end iterator a different type is that for input and forward iterators the end is actually not movable: you can't move it forward without moving beyond the end known to the algorithm and there is no way to move it backward. Thus, it really is just an end point rather than an iterator. Giving an end point a different type can make the use of alorithms more efficient and the creation of new iterators simpler. For more details on this line of reasoning see the Eric Niebler's blogs on this topic.

Dietmar Kühl
  • 150,225
  • 13
  • 225
  • 380
  • 1
    *"as you are neither allowed to read nor write it"* I think this is a crucial point. Making it merely a `const_iterator` is possible, but we could go further: we could disallow accessing it completely. The type could express that it merely serves as an end-point. And when we want to include "an end-point of what?", we end up with a single *range*-like parameter that includes both begin and end. – dyp Dec 25 '14 at 21:30
  • @dyp: actually, there is a huge gap between iterator/end-point and range! Ranges need to determine their end themselves while an iterator/end-point still splits the responsibility. In particular, and positional information for the end is still only held by the end-point. This separation into two separate objects with different types [where appropriate] allows for nice ways to break out of algorithms before the end is reached. – Dietmar Kühl Dec 25 '14 at 21:36
  • 1
    Maybe I'm running into the issue of ambiguity of the term "range". What I was referring to in my comment is simply a requirement between two function parameters, expressed as the invariant of a class. In other words: Algorithms require their begin and end parameters to describe *one* range, so there's a single requirement that needs to be described by using both parameters. This connection is typically expressed as a comment, but it might be expressible in the form of a single parameter which implements a concept: provide begin and end, with the guarantee that [begin, end) is an iterator-range – dyp Dec 25 '14 at 21:43
  • @dyp: at the moment it seems the terminology isn't quite settled but _ranges_ seem to become single entities which describe a sequence, primarily by providing a `begin()` and an `end()` [in some form]. Implementing algorithms in terms of pairs of a begin iterator and an end which may either be an iterator or an end-point does have some value, though. Although the begin/end may be conflated into one _concept_ I don't see them conflated into one _object_ (or one _type_ for that matter) when interacting with algorihms. – Dietmar Kühl Dec 25 '14 at 21:55
  • Indeed, but IIRC, the main reason Eric Niebler mentions why we should keep the two-parameter form is because it's far easier to upgrade existing algorithms. Then, add an adapter for the desired interface `std::sort(my_vector)`. -- Returning to the OP: If the second parameter must have the same type as the first, those algorithms that don't need to traverse back from end are overconstrained. For those, a better constraint would be *the type of `end` must fulfil the EndPoint concept for the type of `begin`*. But that doesn't include the requirement that [begin,end) must be an iterator-range. – dyp Dec 25 '14 at 22:36
0
std::prev(it);

is an iterator of the same type as it. If end() was a const_iterator instead of an iterator, that wouldn't work.

There are good reasons to allow sentinel types instead of iterator types for the end() of a range in many algorithms, but there are also good reasons to not allow them.

The std library, at this point, simply assumes that your begin and end iterators will be the same type, as for most containers this is reasonable.

There are some proposals being worked on to split the type of begin and end iterators, which would both allow for constness on forward end iterators, and allow some other optimizations (like efficient null-termination iteration in standard library algorithms).

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524