Bug in iterator comparison in C++ standard?
We've encountered an ... anomaly, let's say, in the iterator comparison behaviour in g++ 4.1.1. The STL implementation in this release is fairly standard, so we don't believe it's specific to g++. Just in case we're overlooking something really obvious, I thought I'd post this here first to get some feedback, rather than accusing the (frankly excellent) g++ guys of writing ropey code :-)
Imagine you have two vectors of the same type, and you'd like to iterate over them in order (ie. all of a's stuff, then all of b's stuff). How about writing:
Except this doesn't work in the rare case that the space allocated for b's foos is just in front of the space for a's foos in memory - in this case, a.begin() and b.end() are the same location, and the comparison (at least in g++'s STL) gives them as being equal. Oh dear. Nondeterministic behaviour results because of the dependence on memory layout. Ouch. Took one of our best guys three days to track down ...
vector<foo> a, b;
// Fill in a, b contents here.
for (vector<foo>::iterator it = a.begin(); it != b.end(); ++it)
if (it == a.end())
it = b.begin();
// Do something with *it
Can you compare iterators from two different objects, we thought? Well, the C++ standard doesn't prohibit it. It has a number of things to say on this subject:
"An iterator j is called reachable from an iterator i if and only if there is a finite sequence of applications of the expression ++i that makes i == j. If j is reachable from i, they refer to the same container."
So if i and j are different containers, then i is not reachable from j, and hence !(i==j). Except we have a case where they're coming out equal.
It also says "If a and b are equal, then either a and b are both dereferenceable or else neither is dereferenceable.". Unfortunately, in this case, a.begin() is dereferenceable and b.end() isn't, so they shouldn't be equal. Except they can be.
So we're thinking that there's either a bug in the standard (someone should have said that it's undefined behaviour to compare iterators from different containers) or a bug in the implementation (there should be one element's gap between the start of a container and the end of the previous one in memory). Currently, the code above seems to be valid and correct, and the compiler turns it into something that doesn't work.
Anyone smart enough to work out where we've gone wrong? :-)
Many thanks for any thoughts. Clearly we've re-written the code to have two separate loops, so it now works - we're just worried that our One True Standard (all hail the Standard!) could have missed something.