[boost] [iterator] std::sort on zip_iterator

Subject: [boost] [iterator] std::sort on zip_iterator
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-05-04 14:45:55

(Resubmitting to Boost list because I did not receive any answers on 
boost-users.)

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