curiousexplorer curiousexplorer - 1 year ago 134
C++ Question

boost zip_iterator and std::sort

I have two arrays

both of the same length.
I want to sort-by-key the
array using the
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
. 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 Source

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download