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 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 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...
[2] http://www.boost.org/doc/libs/1_50_0/libs/iterator/doc/new-iter-concepts.htm...
