boost zip_iterator y std :: sort

Question

Tengo dos matrices values y keys ambas de la misma longitud. Quiero clasificar por clave la matriz values usando la matriz keys como claves. Me han dicho que el iterador zip del boost es la herramienta correcta para que bloquea dos arreglos juntos y les hace cosas al mismo tiempo.

Aquí está mi intento de utilizar el boost :: zip_iterator para resolver el problema de ordenación que no se puede compilar 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 <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; 
} 

NOTA: Mensaje de error en la compilació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*)’ 

Answer 1

No se puede ordenar un par de zip_iterators.

En primer lugar, make_zip_iterator toma una tupla de iteradores como entrada, por lo que podría llamar:

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

pero que no se compilará tampoco, porque keys y keys+N no tiene el mismo tipo. Tenemos que forzar keys para convertirse 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))); 

este compilará, pero el resultado ordenados sigue siendo incorrecto, porque un zip_iterator modelos sólo un Readable iterator, pero std::sort también necesita la entrada para ser Writable como described here, por lo no puedes ordenar usando zip_iterator.

Answer 2

boost::make_zip_iterator dar un impulso :: tupla.

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

Answer 3

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

Pensé en aclararle el 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<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; 
} 

no probado, pero cualquier error debe haber errores de sintaxis simples

Answer 4

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

Aquí es un posible duplicado de esta pregunta: Sorting zipped (locked) containers in C++ using boost or the 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 compilador actualizado.

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

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