Increase zip_iterator and std :: sort

Question

I have two arrays of values and keys with the same length. I want to sort the values array by key, using the keys array as keys. I was told that the zip iterator accelerator is just the right tool to lock two arrays together and do things at the same time.

Here is my attempt to use boost :: zip_iterator to solve a sorting problem that does not compile with gcc . Can someone help me fix this code?

The challenge lies in a straight 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. Compilation error message

 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 cannot sort a pair of zip_iterators.

First, make_zip_iterator takes a tuple of iterators as input, so you can call:

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

but this also does not compile, because keys and keys+N do not have the same type. We need to make keys 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, since zip_iterator only models the Readable iterator , but std::sort also needs a Writable input as described here , so you cannot 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 is a possible duplicate of this question: Sorting compressed (locked) containers in C ++ using boost or STL

The connection above uses std :: sort with no extra space. It does not use boost :: zip_iterator, it simply increases the tuples and facade of the boost iterator. Std :: tuples should also work if you have a modern compiler.

If you are happy to have one additional vector (from the elements of size_t), then the following approach will work in a tool with a time interval of ~ o (n log n). It's pretty simple, but there will be better approaches if you find 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; } 

Answer 3

After viewing another comment in another answer.

I would enlighten you on std :: map. This is a container of key values ​​that preserves the order of the keys. (this is basically a binary tree, usually red ebony, but that doesn't matter).

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

unchecked, but any error should be a simple syntax error

Answer 4

boost::make_zip_iterator take 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; }