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

Trouver une permutation de tri

Étant donné un std::vector<T> et une comparaison pour T nous voulons être en mesure de trouver la permutation que vous utiliseriez si vous deviez trier le vecteur en utilisant cette comparaison.

template <typename T, typename Compare>
std::vector<std::size_t> sort_permutation(
    const std::vector<T>& vec,
    Compare& compare)
{
    std::vector<std::size_t> p(vec.size());
    std::iota(p.begin(), p.end(), 0);
    std::sort(p.begin(), p.end(),
        [&](std::size_t i, std::size_t j){ return compare(vec[i], vec[j]); });
    return p;
}

Application d'une permutation de tri

Étant donné un std::vector<T> et une permutation, nous voulons être capable de construire une nouvelle std::vector<T> qui est réordonné selon la permutation.

template <typename T>
std::vector<T> apply_permutation(
    const std::vector<T>& vec,
    const std::vector<std::size_t>& p)
{
    std::vector<T> sorted_vec(vec.size());
    std::transform(p.begin(), p.end(), sorted_vec.begin(),
        [&](std::size_t i){ return vec[i]; });
    return sorted_vec;
}

Vous pouvez bien sûr modifier apply_permutation pour muter le vecteur que vous lui donnez plutôt que de retourner une nouvelle copie triée. Cette approche est toujours d'une complexité temporelle linéaire et utilise un bit par élément dans votre vecteur. Théoriquement, la complexité spatiale est toujours linéaire, mais en pratique, quand sizeof(T) est importante, la réduction de l'utilisation de la mémoire peut être spectaculaire. ( Voir les détails )

template <typename T>
void apply_permutation_in_place(
    std::vector<T>& vec,
    const std::vector<std::size_t>& p)
{
    std::vector<bool> done(vec.size());
    for (std::size_t i = 0; i < vec.size(); ++i)
    {
        if (done[i])
        {
            continue;
        }
        done[i] = true;
        std::size_t prev_j = i;
        std::size_t j = p[i];
        while (i != j)
        {
            std::swap(vec[prev_j], vec[j]);
            done[j] = true;
            prev_j = j;
            j = p[j];
        }
    }
}

Ejemplo

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

auto p = sort_permutation(vectorA,
    [](T const& a, T const& b){ /*some comparison*/ });

vectorA = apply_permutation(vectorA, p);
vectorB = apply_permutation(vectorB, p);

Ressources

• std::vector
• std::iota
• std::sort
• std::swap
• std::transform

Answer 2

Avec gamme-v3 c'est simple, il faut trier une vue de la fermeture éclair :

std::vector<MyObject> vectorA = /*..*/;
std::vector<int> vectorB = /*..*/;

ranges::v3::sort(ranges::view::zip(vectorA, vectorB));

ou utiliser explicitement la projection :

ranges::v3::sort(ranges::view::zip(vectorA, vectorB),
                 std::less<>{},
                 [](const auto& t) -> decltype(auto) { return std::get<0>(t); });

Démo

Answer 3

Je voudrais contribuer avec une extension que j'ai créée. Le but est de pouvoir trier plusieurs vecteurs en même temps en utilisant une syntaxe simple.

sortVectorsAscending(criteriaVec, vec1, vec2, ...)

L'algorithme est le même que celui proposé par Timothy mais en utilisant modèles variadiques Nous pouvons donc trier plusieurs vecteurs de types arbitraires en même temps.

Voici l'extrait de code :

template <typename T, typename Compare>
void getSortPermutation(
    std::vector<unsigned>& out,
    const std::vector<T>& v,
    Compare compare = std::less<T>())
{
    out.resize(v.size());
    std::iota(out.begin(), out.end(), 0);

    std::sort(out.begin(), out.end(),
        [&](unsigned i, unsigned j){ return compare(v[i], v[j]); });
}

template <typename T>
void applyPermutation(
    const std::vector<unsigned>& order,
    std::vector<T>& t)
{
    assert(order.size() == t.size());
    std::vector<T> st(t.size());
    for(unsigned i=0; i<t.size(); i++)
    {
        st[i] = t[order[i]];
    }
    t = st;
}

template <typename T, typename... S>
void applyPermutation(
    const std::vector<unsigned>& order,
    std::vector<T>& t,
    std::vector<S>&... s)
{
    applyPermutation(order, t);
    applyPermutation(order, s...);
}

template<typename T, typename Compare, typename... SS>
void sortVectors(
    const std::vector<T>& t,
    Compare comp,
    std::vector<SS>&... ss)
{
    std::vector<unsigned> order;
    getSortPermutation(order, t, comp);
    applyPermutation(order, ss...);
}

// make less verbose for the usual ascending order
template<typename T, typename... SS>
void sortVectorsAscending(
    const std::vector<T>& t,
    std::vector<SS>&... ss)
{
    sortVectors(t, std::less<T>(), ss...);
}

Testez-le dans Idéone .

Je l'explique un peu mieux dans cet article de blog .

Answer 4

Triage à la place à l'aide de la permutation

J'utiliserais une permutation comme Timothy, bien que si vos données sont trop grandes et que vous ne voulez pas allouer plus de mémoire pour le vecteur trié vous devriez le faire en place . Voici un exemple d'une méthode O(n) (complexité linéaire) Triage en place par permutation :

L'astuce consiste à obtenir la permutation et la permutation inverse pour savoir où placer les données écrasées par la dernière étape de tri.

template <class K, class T> 
void sortByKey(K * keys, T * data, size_t size){
    std::vector<size_t> p(size,0);
    std::vector<size_t> rp(size);
    std::vector<bool> sorted(size, false);
    size_t i = 0;

    // Sort
    std::iota(p.begin(), p.end(), 0);
    std::sort(p.begin(), p.end(),
                    [&](size_t i, size_t j){ return keys[i] < keys[j]; });

    // ----------- Apply permutation in-place ---------- //

    // Get reverse permutation item>position
    for (i = 0; i < size; ++i){
        rp[p[i]] = i;
    }

    i = 0;
    K savedKey;
    T savedData;
    while ( i < size){
        size_t pos = i;
        // Save This element;
        if ( ! sorted[pos] ){
            savedKey = keys[p[pos]];
            savedData = data[p[pos]];
        }
        while ( ! sorted[pos] ){
            // Hold item to be replaced
            K heldKey  = keys[pos];
            T heldData = data[pos];
            // Save where it should go
            size_t heldPos = rp[pos];

            // Replace 
            keys[pos] = savedKey;
            data[pos] = savedData;

            // Get last item to be the pivot
            savedKey = heldKey;
            savedData = heldData;

            // Mark this item as sorted
            sorted[pos] = true;

            // Go to the held item proper location
            pos = heldPos;
        }
        ++i;
    }
}

Answer 5

1. Faites un vecteur de paires à partir de vos vecteurs individuels.
   initialiser le vecteur de paires
   Ajout à un vecteur de paire

2. Réaliser un comparateur de tri personnalisé :
   Tri d'un vecteur d'objets personnalisés
   http://rosettacode.org/wiki/Sort_using_a_custom_comparator#C.2B.2B

3. Triez votre vecteur de paires.

4. Séparez votre vecteur de paires en vecteurs individuels.

5. Mettez tout cela dans une fonction.

Code :

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

struct less_than_int
{
    inline bool operator() (const std::pair<MyObject,int>& a, const std::pair<MyObject,int>& b)
    {
        return (a.second < b.second);
    }
};

sortVecPair(vectorA, vectorB, less_than_int());

// make sure vectorA and vectorB are of the same size, before calling function
template <typename T, typename R, typename Compare>
sortVecPair(std::vector<T>& vecA, std::vector<R>& vecB, Compare cmp)
{

    std::vector<pair<T,R>> vecC;
    vecC.reserve(vecA.size());
    for(int i=0; i<vecA.size(); i++)
     {
        vecC.push_back(std::make_pair(vecA[i],vecB[i]);   
     }

    std::sort(vecC.begin(), vecC.end(), cmp);

    vecA.clear();
    vecB.clear();
    vecA.reserve(vecC.size());
    vecB.reserve(vecC.size());
    for(int i=0; i<vecC.size(); i++)
     {
        vecA.push_back(vecC[i].first);
        vecB.push_back(vecC[i].second);
     }
}