Comparing Iterators from Different Containers

comparing iterators from different containers

If you consider the C++11 standard (n3337):

§ 24.2.1 — [iterator.requirements.general#6]

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 elements of the same sequence.

§ 24.2.5 — [forward.iterators#2]

The domain of == for forward iterators is that of iterators over the same underlying sequence.

Given that RandomAccessIterator must satisfy all requirements imposed by ForwardIterator, comparing iterators from different containers is undefined.

The LWG issue #446 talks specifically about this question, and the proposal was to add the following text to the standard (thanks to @Lightness Races in Orbit for bringing it to attention):

The result of directly or indirectly evaluating any comparison function or the binary - operator with two iterator values as arguments that were obtained from two different ranges r1 and r2 (including their past-the-end values) which are not subranges of one common range is undefined, unless explicitly described otherwise.

Compare two list iterators which point to different lists

Sure, you can do that, as you're not comapring the iterators but the addresses of their referands.

Assuming iterators are from different containers, this comparison cannot ever be true in a well-formed program, though.

Performance cost of comparing two C++ iterators

The draft Standard states that iterator operations are amortized constant time

24.2.1 In general [iterator.requirements.general]

8 All the categories of iterators require only those functions that
are realizable for a given category in constant time (amortized).
Therefore, requirement tables for the iterators do not have a
complexity column.

If you look at the signatures of iterator operations, there are no parameters or return types that correspond to the underlying elements T themselves, only T* and T& are required. Even operator== does not have to directly compare two arbitrarily large elements T themselves.

However, this does not give a hard real-time upper-bound for iterator operations. In particular, iterators can do very costly bounds checking, but these Debug mode security guards can usually be left out in Release builds.

Writing an iterator that makes several containers look as one

boost::join is what you're looking for. You can also study the implementation, especially how to derive the lowest common denominator for container traversal, reference and return value types. To quote:

The intention of the join function is to join two ranges into one longer range.

The resultant range will have the lowest common traversal of the two ranges supplied as parameters.

Note that the joined range incurs a performance cost due to the need to check if the end of a range > has been reached internally during traversal.

are two different iterators on the same collection equal

... to compare objects in the same list:

Yes, that means exactly what you expect, and works fine.

---

Related Topics