curiousexplorer curiousexplorer - 22 days ago 7
C++ Question

boost zip_iterator and std::sort

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

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.