boost zip_iterator e std :: sort

Question

Ho due array values e keys entrambi della stessa lunghezza. Voglio ordinare la matrice values usando l'array keys come chiavi. Mi è stato detto che l'iteratore zip di boost è lo strumento giusto per bloccare due array insieme e fare loro roba allo stesso tempo.

Ecco il mio tentativo di utilizzare boost :: zip_iterator per risolvere il problema di ordinamento che non riesce a compilare con gcc. Qualcuno può aiutarmi a risolvere questo codice?

il problema sta nella linea

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: Messaggio di errore sulla compilazione

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

Non è possibile ordinare un paio di zip_iterators.

Innanzitutto, make_zip_iterator prende una tupla di iteratori come input, quindi si può chiamare:

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

ma che non viene compilato o, perché keys e keys+N non ha lo stesso tipo. Dobbiamo costringere keys per diventare un puntatore:

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

questo compilerà, ma il risultato ordinato è ancora sbagliata, perché una zip_iterator solo modelli un Readable iterator, ma std::sort deve anche l'ingresso di essere Writable come described here, così non puoi ordinare usando zip_iterator.

Answer 2

boost::make_zip_iterator prendere un boost :: 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

Dopo aver visto un altro dei tuoi commenti in un'altra risposta.

Anche se vorrei illuminarti alla std :: map. Questo è un contenitore di valori chiave, che conserva l'ordine delle chiavi. (è fondamentalmente un albero binario, di solito albero nero rosso, ma non è 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; 
} 

non testato, ma qualsiasi errore dovrebbe essere semplici errori di sintassi

Answer 4

Una buona discussione di questo problema può essere trovato qui: https://web.archive.org/web/20120422174751/http://www.stanford.edu/~dgleich/notebook/2006/03/sorting_two_arrays_simultaneou.html

Ecco un possibile duplicato di questa domanda: Sorting zipped (locked) containers in C++ using boost or the STL

L'approccio nel link sopra utilizza std :: sort e nessuno spazio aggiuntivo. Non impiega boost :: zip_iterator, semplicemente incrementa le tuple e la facciata dell'iter iter boost. Std :: tuples dovrebbe funzionare anche se hai un compilatore aggiornato.

Se si è felici di avere un vettore in più (di elementi size_t), il seguente approccio funzionerà in caso di ricorrenza in ~ o (n log n) tempo medio. È abbastanza semplice, ma ci saranno approcci migliori là fuori se li cerchi.

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