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*)’

Matrilineal

As pointed out by carl-cook, there is more recent (duplicate) question in which a working solution is given. Also note that Eric Niebler's range library provides view::zip which just works. Said library has been proposed for standardization. – Yorktown

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.

Shanell

Thank you. This was useful But then how would I go about sorting-by-key the values array? I am sure it is a very common operation one encounters in C++ – Matrilineal

@curiousexplorer: The easiest way is to make it an array of std::pair<int, double> or boost::tuple<int, double>. – Shanell

It does not compile: gcc.godbolt.org/z/aWPYbYvr9 – Degradation

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;
}

Lyndes

Answer 3

After seeing another of your comments in another answer.

I though I would enlighten you to the std::map. This is a key value container, that preserves key order. (it is basically a binary tree, usually red black tree, but that isn't important).

size_t elements=10;
std::map<int, double> map_;
for (size_t i = 0; i < 10; ++i)
{
    map_[rand()%M]=1.0*rand()/RAND_MAX;
}
//for every element in map, if you have C++11 this can be much cleaner
for (std::map<int,double>::const_iterator it=map_.begin(); 
         it!=map_.end(); ++it) 
{
    std::cout << it->first   <<  "\t"  << it->second  << std::endl;  
}

untested, but any error should be simple syntax errors

Spiraea

The key/value vectors have advantages compared to map. See #13224104 – Tarboosh

Answer 4

boost::make_zip_iterator take a boost::tuple.

#include <boost/iterator/zip_iterator.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_comparison.hpp>

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>

int main(int argc, char *argv[])
{
  std::vector<int> keys(10);      //lets not waste time with arrays
  std::vector<double> values(10);
  const int M=100;

  //Create the vectors.
  for (size_t i = 0; i < values.size(); ++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(
                    boost::make_tuple(keys.begin(), values.begin())), 
               boost::make_zip_iterator(
                     boost::make_tuple(keys.end(), values.end()))
             );
    //The values array and the corresponding keys in ascending order. 
   for (size_t i = 0; i < values.size(); ++i)
    {
      std::cout << keys[i]   <<  "\t"  << values[i]    << std::endl;  
     }
  return 0;
}

Spiraea

ok this compiles. But it gives me a junk answer. Of the two columns which are being printed the first one is entirely 93 and the second entriely 0.197551 – Matrilineal

I am actually surprised it compiled at all at first, you need to make you own comparison function – Spiraea

It does not compile nowadays: gcc.godbolt.org/z/va9ddo15d – Degradation