Take the 2-minute tour ×

the following question just shot through my head. For the c++ stl iterators, a common practice is to have something like:

for (iterator it=obj.begin(); it!=obj.end(); it++)

what I am wondering is actually that obj.begin() could have told "it" when to stop which would make the for loop look like:

for (iterator it=obj.begin(); !it.end(); it++)

The benefit would be to make the iterator more self contained, and one could save (iterator end()) in the container class.

share|improve this question
Consider a pointer into an array, which is itself a random access iterator. Such a pointer has no information as to where the end of the array is. –  James McNellis Apr 27 '12 at 21:51
Certain libraries, like ITK, have opted for the latter for their iterators. I like the former since 1: it doesn't demand that iterators implement an end() function and 2: allows many iterators to be typedef-ed to pointers, which increases performance by saving a function call. –  smocking Apr 27 '12 at 21:57
An iterator is just an iterator why would you want the overhead of all iterators to have knowledge of the bounds of the container? So you would want obj.begin() to set the bounds to the iterator but you are still calling it.end() as a boolean check, how is this any different? the iterator is like a pointer into to the container it is not the container, the container will know it's bounds, why would you want the iterator to hold this value which could be invalidated in your for loop anyway? –  EdChum Apr 27 '12 at 22:00
@EdChum I think the difference is obvious, either the iterator is stupid but simple, or it's smart but less efficient and less controllable. –  chaiy Apr 27 '12 at 22:18
@smocking: if the obvious implementation of (say) vector::iterator is any slower than a pointer due to function-call overhead, then your compiler is rubbish (or equivalently, you forgot to turn on optimization). That might not have been the case at the time that the design decision was made, though. –  Steve Jessop Apr 27 '12 at 23:43

7 Answers 7

up vote 4 down vote accepted

If the iterator API would be designed like that, a pointer wouldn't be a valid iterator (since a pointer obviously wouldn't have an end()) method. So that would rule out the most straight-forward way to implement iterators for data structures with contiguous memory.

share|improve this answer
thanks. But I am writing my own matrix container at the moment, where you can both iterate vertically and horizontally. For this reason, I cannot simply typedef it from a pointer. But I guess die discussion is how intelligent one expects from a pointer, and I was just asking because I haven't seen any pointer implemented with an end() before. But as smocking pointed out, this has been done already. –  chaiy Apr 27 '12 at 22:16
More importantly, not allowing a pointer to be a valid iterator would rule out the ability to use the STL algorithms to iterate over a C array, which is often very useful. –  abarnert Apr 27 '12 at 22:43
@abarnert: presumably if C++ had opted for iterators that have an end() member function and therefore cannot be implemented as pointers, then it would also have provided a standard class that is an iterator capable of iterating over an array (or more generally, any pair of supplied pointers where the second is reachable from the first by incrementing). And even if it hadn't, you'd only have to write it for yourself once, and it would be pretty trivial. –  Steve Jessop Apr 27 '12 at 23:33

Sometimes you want to do something other than iterate over the entire contents of a container. For example, you can create a pair of iterators that will iterate over only the first half of a container. So having a separate object to represent the end is more flexible since it allows the user more control of where to place the end of a range.

You are right that it is somewhat inconvenient for the most common case of iterating over everything. However, C++11 provides a range based for loop which makes looping over a whole container really easy, so like many things in programming, it's really just a matter of selecting the right construct to best express your intention.

share|improve this answer
But for that, there's ranged-for. There goes all of the inconvenience out the window. –  chris Apr 27 '12 at 22:16

Some libraries provide "java-style iterators" that work like you describe.

However, the big problem with this scheme (hasNext(), etc) is that such iterators are classes.

For example, STL contains <algorithm> header that contains functions like std::copy, std::generate, std::sort, std::lower_bound, std::fill etc. All those routines use begin/end style iterators. As a result, you can use pointers with those functions. If those function were operating on iterators that are classes (i.e. if they called hasNext() instead of != end() internally), then you wouldn't be able to pass pointers into std::sort and such. In this scenario you would have to wrap everything into class, wasting your time, and losing access to <algorithm> is not worth minor convenience you'd get by adding atEnd() method to iterator class. That's probably the reason why iterators are compared to the end().

share|improve this answer

There is no requirement for iterator to "know" about the container. It could just know and care about an offset in a block of memory or a current node (or whatever is appropriate for the data structure being iterated on), without knowing anything about encompassing container. For example, a vector iterator could be implemented as a simple pointer, without knowing (by itself) where the vector ends.

Also, STL algorithms need to work on raw pointers as well, so iterators need to "mimic" pointers.

share|improve this answer

Ultimately it's just the decision made when the STL was invented (by Stepanov in the early 90s), and later ratified in the C++ standardization process, that an iterator would be a generalization of a pointer. From http://www.sgi.com/tech/stl/stl_introduction.html:

In the example of reversing a C array, the arguments to reverse are clearly of type double*. What are the arguments to reverse if you are reversing a vector, though, or a list? ... The answer is that the arguments to reverse are iterators, which are a generalization of pointers.

Iterators didn't have to be a generalization of pointers. The C++ standard libraries (and before that the STL) could in theory have used a different iteration model, in which an iteration would be represented either by a single iterator object or a single range object, instead of by a pair of iterators first and last.

I don't think there would be much performance difference. There certainly wouldn't be with modern C++ compilers. The STL (and the standard libraries based on it) always relied for performance on decent inlining by the compiler, and these classes wouldn't be any worse than what compilers already have to deal with in the bowels of the containers. Nor would there be any major difficulty in providing a simple wrapper that turns a pair of pointers into an iterator or range object.

Some people do prefer other iterator models - James Gosling for one (or if not him, whoever designed Java iterators). And some people prefer ranges (including plenty of C++ programmers: hence Boost.Range).

I suspect the authors of the STL and C++ liked the fact that STL-style iterators retained a kind of compatibility with C, that you could take a C algorithm that used pointers to operate on an array (or other range specified by the user with a pair of pointers), and transform it almost unchanged into a C++ algorithm that uses iterators to operate on a container (or other range). That's the kind of thinking that means your new language can be more easily assimilated by an existing user-base, which was one of the goals of C++ early on.

So questions like, "can we provide a means of testing for end which is a few characters shorter, at the cost of making pointers no longer be iterators and making iterators larger" probably would not have got much interest at the time. But that was then, and for example Andrei Alexandrescu has been banging on for a while now that in his opinion this is not longer the best choice, and that ranges are better than iterators.

share|improve this answer

Having the iterator work the way it does gives you the flexibility to work on subranges. You don't always have to start at begin() or end at end(). For example if you want to work with all the iterators containing a certain value you can use the return value of equal_range() for your beginning and ending.

The D language has a range which incorporates both the beginning and end of an iterator range. It was also proposed for C++: http://groups.google.com/group/comp.lang.c++.moderated/browse_thread/thread/7e52451ed8eea31c

share|improve this answer
bool iterator::end() does not by itself preclude container::end() nor comparing iterators. –  Branko Dimitrijevic Apr 27 '12 at 22:01
@BrankoDimitrijevic, but it does require the iterator to store both its current position and its endpoint. That's the kind of overhead C++ has always tried to avoid. A range is different because it's expected to hold both points. –  Mark Ransom Apr 27 '12 at 22:09
Exactly my point. It's this overhead (and "compatibility" with pointers) that's the main reason for the lack of iterator::end(), not ranges. You can have ranges whether you have iterator::end() or not. –  Branko Dimitrijevic Apr 27 '12 at 22:12

Knowing where your iterator's begin and end (and rbegin and rend) are is certainly useful but the case you state is somewhat handled by C++11's range-based for-loop:

for (auto it: obj)
    // Do something with *it;

It's much easier to get things done in C++11 without writing so much boiler-plate!

share|improve this answer

Your Answer


