[Boost-users] [iterator] std::sort on zip_iterator

Subject: [Boost-users] [iterator] std::sort on zip_iterator
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-05-02 13:11:36

I would like to sort two separate vectors of numbers, treating 
corresponding elements of the two vectors as tuples and sorting the 
tuples.  In particular, I am only comparing the first elements of the 
tuples; that may or may not be relevant to my problem.  An example program 
is:

#include <vector>
#include <algorithm>
#include <iostream>
#include <boost/tuple/tuple.hpp>
#include <boost/iterator/zip_iterator.hpp>

struct compare_first_elements_in_tuples {
   template <typename Tuple>
   bool operator()(const Tuple& a, const Tuple& b) const {
     return (a.template get<0>()) < (b.template get<0>());
   }
};

int main(int, char**) {
   size_t a_data[5] = {0, 2, 1, 2, 4};
   size_t b_data[5] = {1, 1, 5, 3, 7};
   std::vector<size_t> a(a_data, a_data + 5);
   std::vector<size_t> b(b_data, b_data + 5);
   std::cout << "Before:";
   for (size_t i = 0; i < a.size(); ++i) {
     std::cout << " (" << a[i] << ", " << b[i] << ")";
   }
   std::cout << std::endl;
   typedef std::vector<size_t>::iterator vec_iter;
   typedef boost::zip_iterator<boost::tuple<vec_iter, vec_iter> > zip_iter;
   std::sort(zip_iter(boost::make_tuple(a.begin(), b.begin())),
             zip_iter(boost::make_tuple(a.end(), b.end())),
             compare_first_elements_in_tuples());
   std::cout << "After:";
   for (size_t i = 0; i < a.size(); ++i) {
     std::cout << " (" << a[i] << ", " << b[i] << ")";
   }
   std::cout << std::endl;
   return 0;
}

On gcc 4.0.1, the sort operation results in the element (2, 1) (a pair of 
corresponding elements in a and b) being duplicated, while the element (1, 
5) does not appear in the result at all:

Before: (0, 1) (2, 1) (1, 5) (2, 3) (4, 7)
After: (0, 1) (2, 1) (2, 1) (2, 3) (4, 7)

I suspect the problem is related to the fact that zip_iterator does not 
return a "real" reference when dereferenced.  Am I mistaken about this? 
Is the code above supposed to work?  If not, is there an alternative way 
to sort one sequence while swapping elements in another in a corresponding 
way?  I am not able to join the two input sequences into a single sequence 
of pairs because of other factors in the use case for this code.  Thank 
you for your help.

-- Jeremiah Willcock