[Iterator] swap and iter_swap do not work with zip_iterator
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
#include <utility>
#include <iostream>
#include
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
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.
I just realized that, while this will make your example code work correctly, std::sort will still not work because its implementation explicitly qualifies calls to iter_swap as std::iter_swap, rather than making an unqualified call (which would allow the zip_iterator overload to be found by argument-dependent lookup). (At least, GCC 4.7's implementation of std::sort does this). Is this intentional? Regards, Nate
Hi, I don't think that this is intentional. On the other hand: GCCs iter_swap detects whether the reference_type is an actual reference and uses a move-implementation when this is not the case(which is a copy when move is not available). I was a bit flushed about the fact, that the implementation of iter_swap is different from swap(*a,*b). In this case it would have been possible to just overload swap for the reference type of zip_iterator. Greetings, Oswin On 2012-07-28 07:51, Nathan Ridge wrote:
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.
I just realized that, while this will make your example code work correctly, std::sort will still not work because its implementation explicitly qualifies calls to iter_swap as std::iter_swap, rather than making an unqualified call (which would allow the zip_iterator overload to be found by argument-dependent lookup). (At least, GCC 4.7's implementation of std::sort does this). Is this intentional?
Regards, Nate
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (3)
-
Benjamin Lindley -
Nathan Ridge -
Oswin Krause