Comment trier un std :: vector en fonction des valeurs d'un autre std :: vector?

Question

J'ai plusieurs std :: vector , tous de la même longueur. Je souhaite trier l'un de ces vecteurs et appliquer la même transformation à tous les autres vecteurs. Y a-t-il une manière élégante de faire ceci? (de préférence en utilisant le STL ou Boost)? Certains des vecteurs contiennent des int et d'autres std :: string s.

Pseudo-code:

std::vector<int> Index = { 3, 1, 2 };
std::vector<std::string> 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" };

Answer 1

L'approche de friol est bonne lorsqu'elle est associée à la vôtre. Commencez par construire un vecteur composé des nombres 1 et # 8230; n , ainsi que des éléments du vecteur dictant l'ordre de tri:

typedef vector<int>::const_iterator myiter;

vector<pair<size_t, myiter> > 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 trier ce tableau à l'aide d'un trieur personnalisé:

struct ordering {
    bool operator ()(pair<size_t, myiter> const& a, pair<size_t, myiter> const& b) {
        return *(a.second) < *(b.second);
    }
};

sort(order.begin(), order.end(), ordering());

Vous avez maintenant capturé l'ordre de réarrangement dans ordre (plus précisément, dans le premier composant des éléments). Vous pouvez maintenant utiliser cet ordre pour trier vos autres vecteurs. Il existe probablement une variante sur place très intelligente exécutée dans le même temps, mais jusqu'à ce que quelqu'un d'autre la propose, voici une variante qui n'est pas sur place. Il utilise order comme table de correspondance pour le nouvel index de chaque élément.

template <typename T>
vector<T> sort_from_ref(
    vector<T> const& in,
    vector<pair<size_t, myiter> > const& reference
) {
    vector<T> 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;
}

Answer 2

Mettez vos valeurs dans un conteneur Boost Multi-Index Ensuite, parcourez pour lire les valeurs dans l'ordre de votre choix. Vous pouvez même les copier sur un autre vecteur si vous le souhaitez.

Answer 3

typedef std::vector<int> int_vec_t;
typedef std::vector<std::string> str_vec_t;
typedef std::vector<size_t> 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 les " indices " vecteur pour indexer dans " Values ??" vecteur.

Answer 4

Une seule solution approximative me vient à l’esprit: créer un vecteur qui soit la somme de tous les autres vecteurs (un vecteur de structures, comme {3, Third, ...}, {1, First, ...}) triez ensuite ce vecteur par le premier champ, puis divisez à nouveau les structures.

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

Answer 5

Vous pouvez probablement définir une "façade" personnalisée. itérateur qui fait ce dont vous avez besoin ici. Il stockerait les itérateurs de tous vos vecteurs ou, sinon, dériverait les itérateurs de tous les vecteurs sauf le premier vecteur du décalage du premier. La partie la plus délicate est ce à quoi l’itérateur déréférence: pense quelque chose comme boost :: tuple et utilise intelligemment boost :: tie. (Si vous souhaitez développer cette idée, vous pouvez créer ces types d'itérateurs de manière récursive à l'aide de modèles, mais vous ne souhaiterez probablement jamais en écrire le type - vous avez donc besoin de c ++ 0x auto ou d'une fonction d'encapsulation pour un tri prenant des plages).

Answer 6

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 ordre quelconque.

Plutôt que de réorganiser ma collection originale, j’emprunterais un concept de la conception de base de données: conserver un index, ordonné selon un critère donné. Cet index est un indirection supplémentaire qui offre une grande flexibilité.

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

using namespace std;

template< typename Iterator, typename Comparator >
struct Index {
    vector<Iterator> 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<Iterator,Comparator> index ( Iterator from, Iterator end, Comparator& c ){
    return Index<Iterator,Comparator>(from,end,c);
}

struct mytype {
    string name;
    double number;
};

template< typename Iter >
struct NameLess : public binary_function<Iter, Iter, bool> {
    bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->name < t2->name; }
};

template< typename Iter >
struct NumLess : public binary_function<Iter, Iter, bool> {
    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<mytype*, NameLess<mytype*> > byname( v, vend, NameLess<mytype*>() );
    Index<mytype*, NumLess <mytype*> > bynum ( v, vend, NumLess <mytype*>() );

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

}

Answer 7

La réponse de ltjax est une excellente approche - qui est en réalité 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 forme un tuple, quels que soient les itérateurs que vous lui fournissez.

Vous pouvez ensuite créer votre propre fonction de comparaison pour un tri basé sur toute combinaison de valeurs d'itérateur dans votre tuple. Pour cette question, ce ne serait que le premier itérateur de votre tuple.

Une caractéristique intéressante de cette approche est qu’elle vous permet de garder la mémoire de chaque vecteur contigu (si vous utilisez des vecteurs et c’est ce que vous voulez). De plus, vous n’avez pas besoin de stocker un vecteur d’index séparé.

Answer 8

Une variante légèrement plus compacte de la réponse de xtofl si vous souhaitez simplement parcourir tous vos vecteurs en vous basant sur l'un des vecteurs clés . Créez un vecteur de permutation et utilisez-le pour indexer vos autres vecteurs.

#include <boost/iterator/counting_iterator.hpp>
#include <vector>
#include <algorithm>

std::vector<double> keys = ...
std::vector<double> values = ...

std::vector<size_t> indices(boost::counting_iterator<size_t>(0u), boost::counting_iterator<size_t>(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;
}

Answer 9

Cela aurait été un addendum à la réponse de Konrad car il s’agissait d’une approche pour une variante sur place consistant à appliquer l’ordre de tri à un vecteur. De toute façon, puisque le montage ne sera pas accepté, je le mettrai ici

Voici une variante sur place avec une complexité temporelle légèrement supérieure, due à une opération primitive de vérification d'un booléen. La complexité d'espace supplémentaire provient d'un vecteur qui peut être une implémentation dépendante d'un compilateur optimisant l'espace. La complexité d’un vecteur peut être éliminée si l’ordre donné peut être modifié.

Voici une variante sur place avec une complexité temporelle légèrement supérieure, due à une opération primitive de vérification d'un booléen. La complexité d'espace supplémentaire provient d'un vecteur qui peut être une implémentation dépendante d'un compilateur optimisant l'espace. La complexité d'un vecteur peut être éliminée si l'ordre donné 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 de 3 ---> 0; 0 --- > 1; 1 ---> 3; 2 ---> 4; 4 ---> 2.

template<typename T>
struct applyOrderinPlace
{
void operator()(const vector<size_t>& order, vector<T>& vectoOrder)
{
vector<bool> 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;
}
}
};

Answer 10

Voici une implémentation relativement simple utilisant la mise en correspondance d'index entre les de codes commandés et non ordonnés qui sera utilisée pour faire correspondre les âges aux noms commandés. noms :

void ordered_pairs()
{
    std::vector<std::string> names;
    std::vector<int> ages;

    // read input and populate the vectors
    populate(names, ages);

    // print input
    print(names, ages);

    // sort pairs
    std::vector<std::string> sortedNames(names);
    std::sort(sortedNames.begin(), sortedNames.end());

    std::vector<int> 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<int> 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<std::string>& n, std::vector<int>& a)
{
    std::string prompt("Type name and age, separated by white space; 'q' to exit.\n>>");
    std::string 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<std::string>& n, const std::vector<int>& 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 finalement, main () devient:

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>

void ordered_pairs();
void populate(std::vector<std::string>&, std::vector<int>&);
void print(const std::vector<std::string>&, const std::vector<int>&);

//=======================================================================
int main()
{
    std::cout << "\t\tSimple name - age sorting.\n";
    ordered_pairs();
}
//=======================================================================
// Function Definitions...

Answer 11

**// C++ program to demonstrate sorting in vector
// of pair according to 2nd element of pair
#include <iostream>
#include<string>
#include<vector>
#include <algorithm>

using namespace std;

// Driver function to sort the vector elements
// by second element of pairs
bool sortbysec(const pair<char,char> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
}

int main()
{
    // declaring vector of pairs
    vector< pair <char, int> > 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<n; i++)
        vect.push_back( make_pair(arr[i],arr1[i]) );

    // Printing the original vector(before sort())
    cout << "The vector before sort operation is:\n" ;
    for (int i=0; i<n; i++)
    {
        // "first" and "second" are used to access
        // 1st and 2nd element of pair respectively
        cout << vect[i].first << " "
             << vect[i].second << endl;

    }

    // Using sort() function to sort by 2nd element
    // of pair
    sort(vect.begin(), vect.end(), sortbysec);

    // Printing the sorted vector(after using sort())
    cout << "The vector after sort operation is:\n" ;
    for (int i=0; i<n; i++)
    {
        // "first" and "second" are used to access
        // 1st and 2nd element of pair respectively
        cout << vect[i].first << " "
             << vect[i].second << endl;
    }
    getchar();
    return 0;`enter code here`
}**

Answer 12

avec les lambdas C ++ 11 et les algorithmes STL basés sur les réponses de Konrad Rudolph et Gabriele D'Antona:

template< typename T, typename U >
std::vector<T> sortVecAByVecB( std::vector<T> & a, std::vector<U> & b ){

    // zip the two vectors (A,B)
    std::vector<std::pair<T,U>> zipped(a.size());
    for( size_t i = 0; i < a.size(); i++ ) zipped[i] = std::make_pair( a[i], b[i] );

    // sort according to B
    std::sort(zipped.begin(), zipped.end(), []( auto & lop, auto & rop ) { return lop.second < rop.second; }); 

    // extract sorted A
    std::vector<T> sorted;
    std::transform(zipped.begin(), zipped.end(), std::back_inserter(sorted), []( auto & pair ){ return pair.first; }); 

    return sorted;
}

Answer 13

Beaucoup ont posé cette question et personne n’a eu de réponse satisfaisante. Voici un assistant std :: sort qui permet de trier deux vecteurs simultanément, en tenant compte des valeurs d’un seul vecteur. Cette solution est basée sur un RadomIt (itérateur aléatoire) personnalisé et agit directement sur les données vectorielles d'origine, sans copies temporaires, sans réarrangement de structure ni index supplémentaire:

C ++, triez un vecteur à partir d'un autre