Comment trier deux vecteurs de la même manière, avec des critères qui n'utilisent qu'un seul des vecteurs ?

Question

Comment trier deux vecteurs de la même manière, avec des critères qui n'utilisent qu'un seul des vecteurs ?

Par exemple, supposons que j'ai deux vecteurs de la même taille :

vector<MyObject> vectorA;
vector<int> vectorB;

J'ai ensuite trié vectorA en utilisant une fonction de comparaison. Ce tri réordonnait vectorA . Comment faire pour que le même réordonnancement s'applique à vectorB ?

---

Une option consiste à créer une structure :

struct ExampleStruct {
    MyObject mo;
    int i;
};

et ensuite trier un vecteur qui contient le contenu de vectorA y vectorB en un seul vecteur :

// vectorC[i] is vectorA[i] and vectorB[i] combined
vector<ExampleStruct> vectorC;

Cela ne semble pas être une solution idéale. Existe-t-il d'autres options, notamment en C++11 ?

Answer 1

J'ai récemment écrit un itérateur zip approprié qui fonctionne avec les algorithmes stl. Il vous permet de produire un code comme celui-ci :

std::vector<int> a{3,1,4,2};
std::vector<std::string> b{"Alice","Bob","Charles","David"};

auto zip = Zip(a,b);
std::sort(zip.begin(), zip.end());

for (const auto & z: zip) std::cout << z << std::endl;

Il est contenu dans un seul en-tête et la seule exigence est C++17. Consultez-le sur GitHub .

Il y a aussi un post sur revue de code qui contient tout le code source.

Answer 2

Je suppose que le vecteur A et le vecteur B ont la même longueur. Vous pourriez créer un autre vecteur, appelons-le pos, où :

pos[i] = the position of vectorA[i] after sorting phase

et ensuite, vous pouvez trier vectorB en utilisant pos, c'est-à-dire créer vectorBsorted où :

vectorBsorted[pos[i]] = vectorB[i]

et ensuite le vecteurBsorted est trié par la même permutation d'index que le vecteurA.

Answer 3

Je ne suis pas sûr que cela fonctionne mais j'utiliserais quelque chose comme ceci. Par exemple, pour trier deux vecteurs, j'utiliserais la méthode de tri à bulles décroissantes et les paires de vecteurs.

Pour le tri à bulles descendant, je créerais une fonction qui nécessite une paire de vecteurs.

void bubbleSort(vector< pair<MyObject,int> >& a)
{
    bool swapp = true;
    while (swapp) {
        int key;
        MyObject temp_obj;
        swapp = false;
        for (size_t i = 0; i < a.size() - 1; i++) {
            if (a[i].first < a[i + 1].first) {
                temp_obj = a[i].first;
                key = a[i].second;

                a[i].first = a[i + 1].first;
                a[i + 1].first = temp_obj;

                a[i].second = a[i + 1].second;
                a[i + 1].second = key;

                swapp = true;
            }
        }
    }
}

Après cela, je mettrais vos deux valeurs vectorielles dans une paire de vecteurs. Si vous êtes capable d'ajouter des valeurs en même temps, utilisez celle-ci et appelez ensuite la fonction de tri à bulles.

vector< pair<MyObject,int> > my_vector;

my_vector.push_back( pair<MyObject,int> (object_value,int_value));

bubbleSort(my_vector);

Si vous voulez utiliser des valeurs après avoir ajouté à vos 2 vecteurs, vous pouvez utiliser celui-ci et ensuite appeler la fonction de tri à bulles.

vector< pair<MyObject,int> > temp_vector;

for (size_t i = 0; i < vectorA.size(); i++) {
            temp_vector.push_back(pair<MyObject,int> (vectorA[i],vectorB[i]));
        }

bubbleSort(temp_vector);

J'espère que cela vous aidera. Salutations, Caner

Answer 4

Basé sur la réponse de Timothy Shields.
Avec une petite modification de apply_permutaion vous pouvez appliquer la permutation à plusieurs vecteurs de différents types à la fois en utilisant une expression de pliage.

template <typename T, typename... Ts>
void apply_permutation(const std::vector<size_t>& perm, std::vector<T>& v, std::vector<Ts>&... vs) {

    std::vector<bool> done(v.size());
    for(size_t i = 0; i < v.size(); ++i) {
        if(done[i]) continue;
        done[i] = true;
        size_t prev = i;
        size_t curr = perm[i];
        while(i != curr) {
            std::swap(v[prev], v[curr]);
            (std::swap(vs[prev], vs[curr]), ...);
            done[curr] = true;
            prev = curr;
            curr = perm[curr];
        }
    }
}