Comment sortinger un std :: vector par les valeurs d’un autre std :: vector?

J’ai plusieurs std::vector , tous de la même longueur. Je veux sortinger un de ces vecteurs et appliquer la même transformation à tous les autres vecteurs. Y a-t-il une façon intéressante de le faire? (de préférence en utilisant le STL ou Boost)? Certains des vecteurs contiennent int s et certains d’entre eux std::ssortingng s.

Pseudo code:

 std::vector Index = { 3, 1, 2 }; std::vector Values = { "Third", "First", "Second" }; Transformation = sort(Index); Index is now { 1, 2, 3}; ... magic happens as Transformation is applied to Values ... Values are now { "First", "Second", "Third" }; 

L’approche de friol est bonne lorsqu’elle est associée au vôtre. Tout d’abord, construisez un vecteur composé des nombres 1… n , avec les éléments du vecteur qui dictent l’ordre de sorting:

 typedef vector::const_iterator myiter; vector > order(Index.size()); size_t n = 0; for (myiter it = Index.begin(); it != Index.end(); ++it, ++n) order[n] = make_pair(n, it); 

Vous pouvez maintenant sortinger ce tableau à l’aide d’un sortingeur personnalisé:

 struct ordering { bool operator ()(pair const& a, pair const& b) { return *(a.second) < *(b.second); } }; sort(order.begin(), order.end(), ordering()); 

Maintenant, vous avez capturé l'ordre de réarrangement dans l' order (plus précisément, dans le premier composant des éléments). Vous pouvez maintenant utiliser cet ordre pour sortinger vos autres vecteurs. Il y a probablement une variante en place très intelligente qui fonctionne en même temps, mais jusqu'à ce que quelqu'un d'autre arrive, voici une variante qui n'est pas en place. Il utilise l' order comme table de consultation pour le nouvel index de chaque élément.

 template  vector sort_from_ref( vector const& in, vector > const& reference ) { vector ret(in.size()); size_t const size = in.size(); for (size_t i = 0; i < size; ++i) ret[i] = in[reference[i].first]; return ret; } 

Placez vos valeurs dans un conteneur Boost Multi-Index, puis effectuez une itération pour lire les valeurs dans l’ordre souhaité. Vous pouvez même les copier sur un autre vecteur si vous le souhaitez.

 typedef std::vector int_vec_t; typedef std::vector str_vec_t; typedef std::vector index_vec_t; class SequenceGen { public: SequenceGen (int start = 0) : current(start) { } int operator() () { return current++; } private: int current; }; class Comp{ int_vec_t& _v; public: Comp(int_vec_t& v) : _v(v) {} bool operator()(size_t i, size_t j){ return _v[i] < _v[j]; } }; index_vec_t indices(3); std::generate(indices.begin(), indices.end(), SequenceGen(0)); //indices are {0, 1, 2} int_vec_t Index = { 3, 1, 2 }; str_vec_t Values = { "Third", "First", "Second" }; std::sort(indices.begin(), indices.end(), Comp(Index)); //now indices are {1,2,0} 

Vous pouvez maintenant utiliser le vecteur "indices" pour indexer dans le vecteur "Valeurs".

Une seule solution brute me vient à l’esprit: créer un vecteur qui est la sum de tous les autres vecteurs (un vecteur de structures, comme {3, Third, …}, {1, First, …}) vector par le premier champ, puis diviser à nouveau les structures.

Il existe probablement une meilleure solution dans Boost ou en utilisant la bibliothèque standard.

Vous pouvez probablement définir un iterator “façade” personnalisé qui fait ce dont vous avez besoin ici. Il stockera les iterators sur tous vos vecteurs ou dérivera les iterators pour tous sauf le premier vecteur du décalage du premier. La partie la plus délicate est de savoir ce à quoi l’iterator déréférencera: penser à quelque chose comme boost :: tuple et utiliser intelligemment boost :: tie. (Si vous souhaitez étendre cette idée, vous pouvez créer ces types d’iterators de manière récursive à l’aide de modèles, mais vous ne voudrez probablement jamais écrire le type – vous avez donc besoin de c ++ 0x auto ou d’une fonction wrapper

Je pense que ce dont vous avez vraiment besoin (mais corrigez-moi si je me trompe) est un moyen d’accéder aux éléments d’un conteneur dans un certain ordre.

Plutôt que de réorganiser ma collection originale, j’emprunterais un concept du design de la firebase database: garder un index, ordonné par un certain critère. Cet index est une indirection supplémentaire qui offre une grande flexibilité.

De cette façon, il est possible de générer plusieurs indices en fonction des différents membres d’une classe.

 using namespace std; template< typename Iterator, typename Comparator > struct Index { vector v; Index( Iterator from, Iterator end, Comparator& c ){ v.reserve( std::distance(from,end) ); for( ; from != end; ++from ){ v.push_back(from); // no deref! } sort( v.begin(), v.end(), c ); } }; template< typename Iterator, typename Comparator > Index index ( Iterator from, Iterator end, Comparator& c ){ return Index(from,end,c); } struct mytype { ssortingng name; double number; }; template< typename Iter > struct NameLess : public binary_function { bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->name < t2->name; } }; template< typename Iter > struct NumLess : public binary_function { bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->number < t2->number; } }; void indices() { mytype v[] = { { "me" , 0.0 } , { "you" , 1.0 } , { "them" , -1.0 } }; mytype* vend = v + _countof(v); Index > byname( v, vend, NameLess() ); Index > bynum ( v, vend, NumLess () ); assert( byname.v[0] == v+0 ); assert( byname.v[1] == v+2 ); assert( byname.v[2] == v+1 ); assert( bynum.v[0] == v+2 ); assert( bynum.v[1] == v+0 ); assert( bynum.v[2] == v+1 ); } 

La réponse de ltjax est une excellente approche – qui est en fait implémentée dans le zip_iterator de boost http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html

Il regroupe dans un tuple les iterators que vous lui fournissez.

Vous pouvez ensuite créer votre propre fonction de comparaison pour un sorting basé sur une combinaison de valeurs d’iterator dans votre tuple. Pour cette question, ce serait simplement le premier iterator de votre tuple.

Une caractéristique intéressante de cette approche est qu’elle vous permet de conserver la mémoire de chaque vecteur individuel (si vous utilisez des vecteurs et que c’est ce que vous voulez). Vous n’avez pas non plus besoin de stocker un vecteur d’index distinct de ints.

Une variante légèrement plus compacte de la réponse de xtofl si vous cherchez simplement à parcourir tous vos vecteurs sur la base d’un seul vecteur de keys . Créez un vecteur de permutation et utilisez-le pour indexer vos autres vecteurs.

 #include  #include  #include  std::vector keys = ... std::vector values = ... std::vector indices(boost::counting_iterator(0u), boost::counting_iterator(keys.size())); std::sort(begin(indices), end(indices), [&](size_t lhs, size_t rhs) { return keys[lhs] < keys[rhs]; }); // Now to iterate through the values array. for (size_t i: indices) { std::cout << values[i] << std::endl; } 

Cela aurait été un addendum à la réponse de Konrad en tant qu’approche pour une variante sur place de l’application de l’ordre de sorting à un vecteur. Quoi qu’il en soit, puisque l’édition ne sera pas terminée, je la mettrai ici

Voici une variante en place avec une complexité temporelle légèrement supérieure due à une opération primitive de vérification d’un booléen. La complexité de l’espace supplémentaire est celle d’un vecteur qui peut être une implémentation dépendante du compilateur. La complexité d’un vecteur peut être éliminée si l’ordre lui-même peut être modifié.

Voici une variante en place avec une complexité temporelle légèrement supérieure due à une opération primitive de vérification d’un booléen. La complexité de l’espace supplémentaire est celle d’un vecteur qui peut être une implémentation dépendante du compilateur. La complexité d’un vecteur peut être éliminée si l’ordre lui-même peut être modifié. Ceci est un exemple de ce que fait l’algorithme. Si l’ordre est 3 0 4 1 2, le mouvement des éléments comme indiqué par les indices de position serait 3 —> 0; 0 —> 1; 1 —> 3; 2 —> 4; 4 —> 2.

 template struct applyOrderinPlace { void operator()(const vector& order, vector& vectoOrder) { vector indicator(order.size(),0); size_t start = 0, cur = 0, next = order[cur]; size_t indx = 0; T tmp; while(indx < order.size()) { //find unprocessed index if(indicator[indx]) { ++indx; continue; } start = indx; cur = start; next = order[cur]; tmp = vectoOrder[start]; while(next != start) { vectoOrder[cur] = vectoOrder[next]; indicator[cur] = true; cur = next; next = order[next]; } vectoOrder[cur] = tmp; indicator[cur] = true; } } }; 

Voici une implémentation relativement simple utilisant le mappage d’index entre les names ordonnés et non ordonnés qui seront utilisés pour faire correspondre les ages aux names ordonnés:

 void ordered_pairs() { std::vector names; std::vector ages; // read input and populate the vectors populate(names, ages); // print input print(names, ages); // sort pairs std::vector sortedNames(names); std::sort(sortedNames.begin(), sortedNames.end()); std::vector indexMap; for(unsigned int i = 0; i < sortedNames.size(); ++i) { for (unsigned int j = 0; j < names.size(); ++j) { if (sortedNames[i] == names[j]) { indexMap.push_back(j); break; } } } // use the index mapping to match the ages to the names std::vector sortedAges; for(size_t i = 0; i < indexMap.size(); ++i) { sortedAges.push_back(ages[indexMap[i]]); } std::cout << "Ordered pairs:\n"; print(sortedNames, sortedAges); } 

Par souci d'exhaustivité, voici les fonctions populate() et print() :

 void populate(std::vector& n, std::vector& a) { std::ssortingng prompt("Type name and age, separated by white space; 'q' to exit.\n>>"); std::ssortingng sentinel = "q"; while (true) { // read input std::cout << prompt; std::string input; getline(std::cin, input); // exit input loop if (input == sentinel) { break; } std::stringstream ss(input); // extract input std::string name; int age; if (ss >> name >> age) { n.push_back(name); a.push_back(age); } else { std::cout <<"Wrong input format!\n"; } } } 

et:

 void print(const std::vector& n, const std::vector& a) { if (n.size() != a.size()) { std::cerr <<"Different number of names and ages!\n"; return; } for (unsigned int i = 0; i < n.size(); ++i) { std::cout <<'(' << n[i] << ", " << a[i] << ')' << "\n"; } } 

Et enfin, main() devient:

 #include  #include  #include  #include  #include  void ordered_pairs(); void populate(std::vector&, std::vector&); void print(const std::vector&, const std::vector&); //======================================================================= int main() { std::cout << "\t\tSimple name - age sorting.\n"; ordered_pairs(); } //======================================================================= // Function Definitions... 
 **// C++ program to demonstrate sorting in vector // of pair according to 2nd element of pair #include  #include #include #include  using namespace std; // Driver function to sort the vector elements // by second element of pairs bool sortbysec(const pair &a, const pair &b) { return (a.second < b.second); } int main() { // declaring vector of pairs vector< pair  > vect; // Initialising 1st and 2nd element of pairs // with array values //int arr[] = {10, 20, 5, 40 }; //int arr1[] = {30, 60, 20, 50}; char arr[] = { ' a', 'b', 'c' }; int arr1[] = { 4, 7, 1 }; int n = sizeof(arr)/sizeof(arr[0]); // Entering values in vector of pairs for (int i=0; i 

Tant de personnes ont posé cette question et personne n’a trouvé de réponse satisfaisante. Voici une aide std :: sort qui permet de sortinger deux vecteurs simultanément, en prenant en compte les valeurs d’un seul vecteur. Cette solution est basée sur un RadomIt (iterator aléatoire) personnalisé et fonctionne directement sur les données vectorielles originales, sans copies temporaires, réarrangements de structure ou indices supplémentaires:

C ++, Trier un vecteur basé sur un autre