Décomposer deux vecteurs

Question

J'espère que le mot "décomposer" est correct, mais le problème est simple: j'ai obtenu deux listes après une opération et je veux savoir quel changement s'est produit d'une liste à l'autre. En tant que tel, je veux "décomposer" les deux listes A et B en "Both", "Only A" et "Only B".

template <class T>
void decompose(std::vector<T*> &a, std::vector<T*> &b, std::vector<T*> &only_a, std::vector<T*> &only_b, std::vector<T*> &both) {
    only_a = a;
    only_b = b;
    for (T* x : a) {
        for (T* y : b) {
            if (x == y) {
                both.push_back(x);
            }
        }
    }

    {
        auto it = only_a.begin();
        while (it != only_a.end()) {
            bool erase = false;
            for (T* x : both) {
                if (x == *it) {
                    it = only_a.erase(it);
                    erase = true;
                }
            }
            if (!erase) {
                it++;
            }
        }
    }

    {
        auto it = only_b.begin();
        while(it != only_b.end()) {
            bool erase = false;
            for (T* x : both) {
                if (x == *it) {
                    it = only_b.erase(it);
                    erase = true;
                }
            }
            if (!erase) {
                it++;
            }
        }
    }
}

Je pense qu'il devrait y avoir un moyen plus rapide de faire cela que trois boucles entrelacées deux fois.

Answer 1

Pour quelque chose de facile à lire et à maintenir que j'utiliserais set_differenceet set_intersectionqui fonctionnerait bien sur des plages triées sans doublons:

std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(both));

only_a.reserve(a.size() - both.size());
std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(only_a));

only_b.reserve(b.size() - both.size());
std::set_difference(b.begin(), b.end(), a.begin(), a.end(), std::back_inserter(only_b));

... mais cela nécessite que vous répétiez trois fois sur les plages, et je pense que vous recherchez quelque chose de plus efficace.

Premièrement, je ne commencerais pas par copier aet bdans only_aet only_brespectivement. Au lieu de cela, inspirez-vous des exemples d'implémentation des fonctions standard auxquelles j'ai lié ci-dessus et créez votre propre algorithme similaire. Cela nécessite que Ts puisse être comparé à operator<:

#include <algorithm>
#include <iterator>

template <class T>
void decompose(std::vector<T>& a,
               std::vector<T>& b,
               std::vector<T>& only_a,
               std::vector<T>& only_b,
               std::vector<T>& both)
{
    // Sort the input or require the input to be sorted like some algorithms do
    // If you'd like the input to be unchanged, make a and b const and make
    // copies of them instead and sort those copies.
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());

    // clear destination vectors or skip this if you want to append instead
    only_a.clear();
    only_b.clear();

    // the actual algorithm - loop for as long as both vectors have elements

    auto ait = a.begin();
    auto bit = b.begin();

    while(ait != a.end() && bit != b.end()) {
        if(*ait < *bit) {
            only_a.push_back(*ait++);  // can only be in a
        } else if(*bit < *ait) {
            only_b.push_back(*bit++);  // can only be in b
        } else {
            both.push_back(*ait++);    // must be in both
            ++bit;
        }
    }

    // Add the remaining elements if not both ait and bit have reached their end()
    if(ait != a.end()) std::copy(ait, a.end(), std::back_inserter(only_a));
    else if(bit != b.end()) std::copy(bit, b.end(), std::back_inserter(only_b));
}

Ou rendez-le encore plus générique et laissez-le fonctionner uniquement avec des itérateurs et ajoutez la possibilité pour l'utilisateur de fournir un foncteur de comparaison . Cela nécessite que les plages soient triées dans le même ordre que si le foncteur Compare était utilisé avec std::sortsur les plages. Le foncteur de comparaison par défaut est ici std::less<>qui, s'il n'est pas spécialisé pour le type impliqué, utilise operator<pour comparer les éléments.

#include <functional> // less
#include <iterator>   // iterator_traits

template <
    class First1, class Last1, class First2, class Last2,
    class OnlyAinserter, class OnlyBinserter, class BothInserter,
    class Comp = std::less<typename std::iterator_traits<First1>::value_type>
    // class Comp = std::less<> // <- is sufficient in C++14 and forward
>
void decompose(First1 ait, Last1 aend, First2 bit, Last2 bend,
               OnlyAinserter onlyait, OnlyBinserter onlybit, BothInserter bothit,
               Comp comp = Comp{})
{
    // loop for as long as both vectors have elements
    while(ait != aend && bit != bend) {
        if(comp(*ait, *bit)) {
            *onlyait++ = *ait++;  // can only be in a
        } else if(comp(*bit, *ait)) {
            *onlybit++ = *bit++;  // can only be in b
        } else {
            *bothit++ = *ait++;   // must be in both
            ++bit;
        }
    }

    // Add the remaining elements if not both ait and bit have reached aend/bend
    if(ait != aend) std::copy(ait, aend, onlyait);
    else if(bit != bend) std::copy(bit, bend, onlybit);
}

Qui peut alors être appelé comme ceci en utilisant le foncteur de comparaison par défaut :

decompose(a.begin(), a.end(), b.begin(), b.end(), 
    std::back_inserter(only_a), std::back_inserter(only_b), std::back_inserter(both));

Ou comme ci-dessous, en fournissant un foncteur de comparaison . Dans cet exemple, les plages doivent être triées par ordre décroissant:

decompose(a.begin(), a.end(), b.begin(), b.end(), 
    std::back_inserter(only_a), std::back_inserter(only_b), std::back_inserter(both),
    [](auto& A, auto& B) { return A > B; } // std::greater<>
);