boost zip_iterator and std::sort

Question

I have two arrays values and keys both of the same length. I want to sort-by-key the values array using the keys array as keys. I have been told the boost's zip iterator is just the right tool for locking two arrays together and doing stuff to them at the same time.

Here is my attempt at using the boost::zip_iterator to solve sorting problem which fails to compile with gcc. Can someone help me fix this code?

The problem lies in the line

std::sort ( boost::make_zip_iterator( keys, values ), boost::make_zip_iterator( keys+N , values+N ));

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <boost/iterator/zip_iterator.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_comparison.hpp>



int main(int argc, char *argv[])
{
  int N=10;
  int    keys[N];
  double values[N];
  int M=100;

  //Create the vectors.
  for (int i = 0; i < N; ++i)
   {
     keys[i]   = rand()%M;
     values[i] = 1.0*rand()/RAND_MAX;
   }


  //Now we use the boost zip iterator to zip the two vectors and sort them "simulatneously"
  //I want to sort-by-key the keys and values arrays
   std::sort ( boost::make_zip_iterator( keys, values  ), 
               boost::make_zip_iterator( keys+N  , values+N    )
             );
    //The values array and the corresponding keys in ascending order. 
   for (int i = 0; i < N; ++i)
    {
      std::cout << keys[i]   <<  "\t"  << values[i]    << std::endl;  
     }
  return 0;
}

NOTE:Error message on compilation

g++ -g -Wall boost_test.cpp 
boost_test.cpp: In function ‘int main(int, char**)’:
boost_test.cpp:37:56: error: no matching function for call to ‘make_zip_iterator(int [(((unsigned int)(((int)N) + -0x00000000000000001)) + 1)], double [(((unsigned int)(((int)N) + -0x00000000000000001)) + 1)])’
boost_test.cpp:38:64: error: no matching function for call to ‘make_zip_iterator(int*, double*)’

Answer 1

You can't sort a pair of zip_iterators.

Firstly, make_zip_iterator takes a tuple of iterators as input, so you could call:

boost::make_zip_iterator(boost::make_tuple( ... ))

but that won't compile either, because keys and keys+N doesn't have the same type. We need to force keys to become a pointer:

std::sort(boost::make_zip_iterator(boost::make_tuple(+keys, +values)),
          boost::make_zip_iterator(boost::make_tuple(keys+N, values+N)));

this will compile, but the sorted result is still wrong, because a zip_iterator only models a Readable iterator, but std::sort also needs the input to be Writable as described here, so you can't sort using zip_iterator.

Answer 2

A very good discussion of this problem can be found here: https://web.archive.org/web/20120422174751/http://www.stanford.edu/~dgleich/notebook/2006/03/sorting_two_arrays_simultaneou.html

Here's a possible duplicate of this question: Sorting zipped (locked) containers in C++ using boost or the STL

The approach in the link above uses std::sort, and no extra space. It doesn't employ boost::zip_iterator, just boost tuples and the boost iterator facade. Std::tuples should also work if you have an up to date compiler.

If you are happy to have one extra vector (of size_t elements), then the following approach will work in ~ o(n log n) time average case. It's fairly simple, but there will be better approaches out there if you search for them.

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

template <typename T1, typename T2>
void sortByPerm(vector<T1>& list1, vector<T2>& list2) {
  const auto len = list1.size();
  if (!len || len != list2.size()) throw;

  // create permutation vector
  vector<size_t> perms;
  for (size_t i = 0; i < len; i++) perms.push_back(i);
  sort(perms.begin(), perms.end(), [&](T1 a, T1 b){ return list1[a] < list1[b]; });

  // order input vectors by permutation
  for (size_t i = 0; i < len - 1; i++) {
    swap(list1[i], list1[perms[i]]);
    swap(list2[i], list2[perms[i]]);

    // adjust permutation vector if required
    if (i < perms[i]) {
      auto d = distance(perms.begin(), find(perms.begin() + i, perms.end(), i));
      swap(perms[i], perms[d]);
    }
  }
}

int main() {
  vector<int> ints = {32, 12, 40, 8, 9, 15};
  vector<double> doubles = {55.1, 33.3, 66.1, 11.1, 22.1, 44.1};

  sortByPerm(ints, doubles);   

  copy(ints.begin(), ints.end(), ostream_iterator<int>(cout, " ")); cout << endl;
  copy(doubles.begin(), doubles.end(), ostream_iterator<double>(cout, " ")); cout << endl;
}