CODEWITHSUNDEEP
c++stlconstants
user877329
user877329

Reputation: 6210

The rationale for non-const for "end" pointer in STL

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;
    }

Upvotes: 1

Views: 118

Answers (2)

Dietmar K&#252;hl
Dietmar K&#252;hl

Reputation: 153915

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.

Upvotes: 2

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275650

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).

Upvotes: 0

Related Questions