Re: [Boost-users] [Iterator] swap and iter_swap do not work with zip_iterator

Subject: Re: [Boost-users] [Iterator] swap and iter_swap do not work with zip_iterator
From: Nathan Ridge (zeratul976_at_[hidden])
Date: 2012-07-28 01:28:16

> I wanted to use zip_iterator to concurrently sort two arrays by the
> values in one of them. It didn't work. Most of the values were
> over-written by one of the pairs. I figured out that there was a
> problem with the swapping, so I made this small test case. Compiled
> with GCC 4.6.1 on Ubuntu 11.10
>
> [snip]
>
> Is this a known problem?

The short answer is that zip_iterator is only a Readable Iterator [1],
but sorting requires Swappable Iterators [2].

The misbehaviour of iter_swap can be further reduced to the following:

    typedef boost::tuples::tuple<int&, int&> tuple_type;
    int x1 = 1, y1 = 2, x2 = 3, y2 = 4;
    tuple_type t1(x1, y1), t2(x2, y2);
    tuple_type tmp = t1;
    t1 = t2;
    t2 = tmp;
    std::cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';

Output:

    3 4 3 4

If we use swap() we are fine because swap() is overloaded to do the 
right thing for tuples of references:

    typedef boost::tuples::tuple<int&, int&> tuple_type;
    int x1 = 1, y1 = 2, x2 = 3, y2 = 4;
    tuple_type t1(x1, y1), t2(x2, y2);
    swap(t1, t2);

Output:

    3 4 1 2

The default implementation of iter_swap() on zip_iterator behaves
like the first snippet, because swap() can only be called with
reference arguments, but zip_iterator's reference type is not an
actual reference (it's a temporary tuple constructed from the 
references returned by dereferencing the component iterators; this 
is also the reason why zip_iterator does not automatically model 
Swappable Iterator). Your call to swap() does not compile for the 
same reason.

zip_iterator can be made to model Swappable Iterator (without 
changing its reference_type) by overloading iter_swap for 
zip_iterator as follows:

namespace boost
{
    template <typename IteratorTuple>
    void iter_swap(zip_iterator<IteratorTuple> a, zip_iterator<IteratorTuple> b)
    {
        typedef typename zip_iterator<IteratorTuple>::value_type ReferenceTuple;
        ReferenceTuple ta = *a;
        ReferenceTuple tb = *b;
        swap(ta, tb);
    }
}

Inserting that snippet above main() in your code, we now get the
desired output:

1 2
100 200

2 1
200 100

I can't think, off the top of my head, of any reason not to add this
overload of iter_swap to Boost.

Regards,
Nate

[1] http://www.boost.org/doc/libs/1_50_0/libs/iterator/doc/zip_iterator.html#zip-iterator-models
[2] http://www.boost.org/doc/libs/1_50_0/libs/iterator/doc/new-iter-concepts.html#design