[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 <boost/iterator/zip_iterator.hpp> int main() { std::vector<int> a = { 1, 2 }; std::vector<int> b = { 100, 200 }; auto first = boost::make_zip_iterator( boost::make_tuple(a.begin(), b.begin())); auto last = boost::make_zip_iterator( boost::make_tuple(a.begin() + 1, b.begin() + 1)); std::cout << first->get<0>() << ' ' << last->get<0>() << '\n'; std::cout << first->get<1>() << ' ' << last->get<1>() << "\n\n"; using std::swap; using std::iter_swap; // swap(*first, *last); // doesn't compile iter_swap(first, last); std::cout << first->get<0>() << ' ' << last->get<0>() << '\n'; std::cout << first->get<1>() << ' ' << last->get<1>() << "\n\n"; } Output: 1 2 100 200 2 2 200 200 Expected Output: 1 2 100 200 2 1 200 100 Is this a known problem?
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... [2] http://www.boost.org/doc/libs/1_50_0/libs/iterator/doc/new-iter-concepts.htm...
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