boost zip_iterator y std :: sort

Tengo dos values matrices y keys de la misma longitud. Quiero ordenar por clave la matriz de values usando la matriz de teclas como claves. Me han dicho que el iterador zip del boost es la herramienta adecuada para bloquear dos matrices juntas y hacerles cosas al mismo tiempo.

Aquí está mi bash de usar el boost :: zip_iterator para resolver el problema de clasificación que no se puede comstackr con gcc . ¿Alguien puede ayudarme a arreglar este código?

El problema radica en la línea

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

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

NOTA: mensaje de error en la comstackción

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

No puedes ordenar un par de zip_iterators.

En primer lugar, make_zip_iterator toma una tupla de iteradores como entrada, para que pueda llamar:

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

pero eso tampoco comstackrá, porque las keys y las keys+N no tienen el mismo tipo. Necesitamos forzar keys para convertirnos en un puntero:

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

esto se comstackrá, pero el resultado ordenado sigue siendo incorrecto, porque un zip_iterator solo modela un iterador legible, pero std::sort también necesita que la entrada sea escribible como se describe aquí , por lo que no puede ordenar usando zip_iterator.

Puede encontrar una muy buena discusión de este problema aquí: https://web.archive.org/web/20120422174751/http://www.stanford.edu/~dgleich/notebook/2006/03/sorting_two_arrays_simultaneou.html

Aquí hay un posible duplicado de esta pregunta: Ordenando contenedores comprimidos (bloqueados) en C ++ usando boost o STL

El enfoque en el enlace de arriba usa std :: sort, y no tiene espacio adicional. No emplea boost :: zip_iterator, solo aumenta las tuplas y aumenta la fachada del iterador. Std :: tuples también debería funcionar si tiene un comstackdor actualizado.

Si está contento de tener un vector adicional (de elementos size_t), el siguiente enfoque funcionará en el caso promedio de ~ o (n log n). Es bastante simple, pero habrá mejores enfoques si los buscas.

 #include  #include  #include  #include  using namespace std; template  void sortByPerm(vector& list1, vector& list2) { const auto len = list1.size(); if (!len || len != list2.size()) throw; // create permutation vector vector 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 ints = {32, 12, 40, 8, 9, 15}; vector doubles = {55.1, 33.3, 66.1, 11.1, 22.1, 44.1}; sortByPerm(ints, doubles); copy(ints.begin(), ints.end(), ostream_iterator(cout, " ")); cout << endl; copy(doubles.begin(), doubles.end(), ostream_iterator(cout, " ")); cout << endl; } 

Después de ver otro de tus comentarios en otra respuesta.

Pensé que lo iluminaría al std :: map. Este es un contenedor de valores clave, que preserva el orden de las llaves. (Básicamente es un árbol binario, generalmente un árbol negro rojo, pero eso no es importante).

 size_t elements=10; std::map 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::const_iterator it=map_.begin(); it!=map_.end(); ++it) { std::cout << it->first << "\t" << it->second << std::endl; } 

no probado, pero cualquier error debería ser un simple error de syntax

boost::make_zip_iterator toma un impulso :: tuple.

 #include  #include  #include  #include  #include  #include  #include  #include  #include  int main(int argc, char *argv[]) { std::vector keys(10); //lets not waste time with arrays std::vector 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; }