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 ints et certains d'entre eux std :: strings.

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 Tranformation is applied to Values ...
Values is now { "First", "Second", "Third" };
 

Answer 1

friol l'approche est bonne lorsqu'elle est couplée avec le vôtre. Tout d'abord, construire un vecteur comprenant les numéros 1...n, ainsi que les éléments du vecteur de dicter 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);

Maintenant, vous pouvez trier ce tableau à l'aide d'une coutume trieur:

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

Maintenant que vous avez capturé l'ordre de réaménagement à l'intérieur d' order (plus précisément, dans la première composante des articles). Vous pouvez maintenant utiliser cette commande pour trier vos autres vecteurs. Il y a probablement un très habile en place dans la variante d'exécution dans le même temps, mais jusqu'à ce que quelqu'un d'autre arrive, voici une variante qui n'est pas en place. Il utilise order comme une look-up table 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

 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 le vecteur "indices" pour indexer dans le vecteur "Valeurs".

Answer 3

Placez vos valeurs dans un conteneur Boost Multi-Index, puis effectuez une nouvelle itération 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 4

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

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

Answer 5

Vous pouvez probablement définir une coutume "de façade" itérateur qui fait ce que vous avez besoin ici. Il serait de stocker les itérateurs pour tous vos vecteurs ou sinon dériver les itérateurs pour tous, mais le premier vecteur de l'offset de la première. La partie la plus délicate est ce que itérateur déréférence pour: penser à quelque chose comme boost::tuple et de faire une utilisation intelligente de boost::cravate. (Si vous voulez étendre sur cette idée, vous pouvez créer ces types iterator de manière récursive à l'aide de modèles mais vous n'avez probablement jamais vouloir écrire le type de ce - de sorte que vous besoin de c++0x auto ou une fonction wrapper pour le tri qui prend les plages)