How is STL iterator equality established?

Question

I was wondering, how is equality (==) established for STL iterators? Is it a simple pointer comparison (and thus based on addresses) or something more fancy?

If I have two iterators from two different list objects and I compare them, will the result always be false?

What about if I compare a valid value with one that's out of range? Is that always false?

Answer 1

Iterator classes can define overloaded == operators, if they want. So the result depends on the implementation of operator==.

You're not really supposed to compare iterators from different containers. I think some debug STL implementations will signal a warning if you do this, which will help you catch cases of this erroneous usage in your code.

Answer 2

I was wondering, how is equality (==) established for STL iterators?

Not all iterators can be compared (e.g. Output Iterators are not required to provide op==). You can use the operator== when the concept of a range is well-defined for the iterator category under consideration.

Is it a simple pointer comparison (and thus based on addresses) or something more fancy?

Iterators are always implemented with pointers. Edit: I say implemented with -- which refers not to a Standard requirement but rather to the practice of using poitners as the underlying construct. Implementations (like VS) may have special validation checks inserted though.

If I have two iterators from two different list objects and I compare them, will the result always be false?

You are invoking Undefined Behavior.

What about if I compare a valid value with one that's out of range? Is that always false?

Again, you will be invoking UB. The only valid comparison are between two iterators in the same range or between one in the range and another to one past the last element. Note, you can only compare against the iterator to one-past the last element, dereferencing the same leads to UB.

Answer 3

The equality test is specific to the type of iterator you are using, or may not exist at all. If you really want to know, you can always check the source code of the implementation of STL you are using, look for operator==() in the iterator class.

Iterators are NOT always pointers, and indeed in some "safe" versions of the STL, are never pointers. Iterators for vectors and strings are commonly implemented as pointers because they can be. Iterators for deques, lists, sets and maps cannot be pointers in any half efficient implementation.

What iterators are is a type of smart pointer. They follow the generic principle that if they look and behave like a pointer, then they are a pointer as far as the user is concerned.

Answer 4

Daniel asked: I was wondering, how is equality (==) established for STL iterators? Is it a simple pointer comparison (and thus based on addresses) or something more fancy?

It depends on implementation. Right now, on Visual C++ 2008, I see the following code (for the list iterator):

bool operator==(const _Myt_iter& _Right) const
{   // test for iterator equality

#if _HAS_ITERATOR_DEBUGGING
    _Compat(_Right);
#else
    _SCL_SECURE_TRAITS_VALIDATE(this->_Has_container() && this->_Same_container(_Right));
#endif /* _HAS_ITERATOR_DEBUGGING */

    return (_Ptr == _Right._Ptr);
}

You'll see above that there is both code for verification of iterator validity, and _Ptr being a pointer to a list node.

So I guess there is both verification, and simple, raw pointer comparison.

Daniel asked: If I have two iterators from two different list objects and I compare them, will the result always be false?

Until now, it appears the standard was somewhat unclear on the subject. Apparently, they will explicitly write that this kind of operation has undefined results:

Quoting: http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#446

The result of using any iterator operation (24.2.1 [input.iterators], 24.2.2 [output.iterators], 24.2.3 [forward.iterators], 24.2.4 [bidirectional.iterators], 24.2.5 [random.access.iterators]) that uses two iterator values as arguments (footnote) which 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.

footnote) Among others these operations are ==, <, binary -, and copy assignment

So I guess it is evil to compare iterator from different containers... ^_^

Daniel asked: What about if I compare a valid value with one that's out of range? Is that always false?

Same as above.