[boost] transform_iterator and ==

From: Kevin S. Van Horn (Kevin.VanHorn_at_[hidden])
Date: 2002-03-22 12:21:15

On Fri, 22 Mar 2002 Roland Richter wrote:

> I recently noticed that adapted iterators (such as transform_iterator)
> might be considered as "equal" even if, when dereferenced, they yield
> different values:
>
>   int x[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
>
>   typedef std::binder1st< std::multiplies<int> > Function;
>   typedef boost::transform_iterator_generator<Function, int*>::type doubling_iterator;
>
>   doubling_iterator i(x, std::bind1st(std::multiplies<int>(), 2));
>   doubling_iterator j(x, std::bind1st(std::multiplies<int>(), 3)); // Somebody wants more
>
> Whoops!
> We have the odd situation that i == j (since both iterators point to the
> same location), but that *i != *j (because dereferencing involves a call
> of transform_iterators' functions; these are different, however
> transform_iterator_policy does not care about that).

The C++ standard has a notion of "domain of ==" for an iterator.  That is,
the expression "a == b" is only well-defined for certain iterator values a and
b.  This is a *specification* issue, not an *implementation* issue -- it may
very well be that "a == b" returns true or false without any other ill effects
even when (a,b) is not in the domain of ==, but you can't count on it.

The solution to the problem you mention is then to very carefully specify the
domain of == for transform_iterator values.  For example, one might consider
(i,j) to be in the domain of == only if i and j were created using
the same function object.