Is it possible to test whether two iterators point to the same object?

Question

Say I'm making a function to copy a value:

template<class ItInput, class ItOutput>
void copy(ItInput i, ItOutput o) { *o = *i; }

and I would like to avoid the assignment if i and o point to the same object, since then the assignment is pointless.

Obviously, I can't say if (i != o) { ... }, both because i and o might be of different types and because they might point into different containers (and would thus be incomparable). Less obviously, I can't use overloaded function templates either, because the iterators might belong to different containers even though they have the same type.

My initial solution to this was:

template<class ItInput, class ItOutput>
void copy(ItInput i, ItOutput o)
{
    if (&*o != static_cast<void const *>(&*i))
        *o = *i;
}

but I'm not sure if this works. What if *o or *i actually returns an object instead of a reference?

Is there a way to do this generally?

Answer 1

I don't think that this is really necessary: if assignment is expensive, the type should define an assignment operator that performs the (relatively cheap) self assignment check to prevent doing unnecessary work. But, it's an interesting question, with many pitfalls, so I'll take a stab at answering it.

If we are to assemble a general solution that works for input and output iterators, there are several pitfalls that we must watch out for:

• An input iterator is a single-pass iterator: you can only perform indirection via the iterator once per element, so, we can't perform indirection via the iterator once to get the address of the pointed-to value and a second time to perform the copy.

• An input iterator may be a proxy iterator. A proxy iterator is an iterator whose operator* returns an object, not a reference. With a proxy iterator, the expression &*it is ill-formed, because *it is an rvalue (it's possible to overload the unary-&, but doing so is usually considered evil and horrible, and most types do not do this).

• An output iterator can only be used for output; you cannot perform indirection via it and use the result as an rvalue. You can write to the "pointed to element" but you can't read from it.

So, if we're going to make your "optimization," we'll need to make it only for the case where both iterators are forward iterators (this includes bidirectional iterators and random access iterators: they're forward iterators too).

Because we're nice, we also need to be mindful of the fact that, despite the fact that it violates the concept requirements, many proxy iterators misrepresent their category because it is very useful to have a proxy iterator that supports random access over a sequence of proxied objects. (I'm not even sure how one could implement an efficient iterator for std::vector<bool> without doing this.)

We'll use the following Standard Library headers:

#include <iterator>
#include <type_traits>
#include <utility>

We define a metafunction, is_forward_iterator, that tests whether a type is a "real" forward iterator (i.e., is not a proxy iterator):

template <typename T>
struct is_forward_iterator :
    std::integral_constant<
        bool,
        std::is_base_of<
            std::forward_iterator_tag,
            typename std::iterator_traits<T>::iterator_category
        >::value &&
        std::is_lvalue_reference<
            decltype(*std::declval<T>())
        >::value>
{ };

For brevity, we also define a metafunction, can_compare, that tests whether two types are both forward iterators:

template <typename T, typename U>
struct can_compare :
    std::integral_constant<
        bool,
        is_forward_iterator<T>::value &&
        is_forward_iterator<U>::value
    >
{ };

Then, we'll write two overloads of the copy function and use SFINAE to select the right overload based on the iterator types: if both iterators are forward iterators, we'll include the check, otherwise we'll exclude the check and always perform the assignment:

template <typename InputIt, typename OutputIt>
auto copy(InputIt const in, OutputIt const out)
    -> typename std::enable_if<can_compare<InputIt, OutputIt>::value>::type
{
    if (static_cast<void const volatile*>(std::addressof(*in)) != 
        static_cast<void const volatile*>(std::addressof(*out)))
        *out = *in;
}

template <typename InputIt, typename OutputIt>
auto copy(InputIt const in, OutputIt const out)
    -> typename std::enable_if<!can_compare<InputIt, OutputIt>::value>::type
{
    *out = *in;
}

As easy as pie!

Answer 2

I think this may be a case where you may have to document some assumptions about the types you expect in the function and be content with not being completely generic.

Like operator*, operator& could be overloaded to do all sorts of things. If you're guarding against operator*, then you should consider operator& and operator!=, etc.

I would say that a good prerequisite to enforce (either through comments in the code or a concept/static_assert) is that operator* returns a reference to the object pointed to by the iterator and that it doesn't (or shouldn't) perform a copy. In that case, your code as it stands seems fine.