Decompose two vectors

Question

I hope that the word "decompose" is correct, but the problem is simple: I got two lists after an operation and I want to know what change happend from one list to the other. As such I want to "decompose" the two lists A and B into "Both", "Only A" and "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++;
            }
        }
    }
}

I feel like there should be a faster way to do this than three twice intertwined loops.

Answer 1

For something easy to read and maintain I'd use set_difference and set_intersection which would work well on sorted ranges with no duplicates:

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

...but that requires that you iterate over the ranges three times, and I think you are looking for something more efficient.

In primo luogo, non vorrei iniziare copiando ae bin only_ae only_b, rispettivamente. Invece, prendi ispirazione dalle implementazioni di esempio per le funzioni standard che ho collegato sopra e crea il tuo algoritmo simile. Ciò richiede che Ts possa essere confrontato con 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));
}

Oppure rendilo ancora più generico e lascia che funzioni solo con gli iteratori e aggiungi la possibilità per l'utente di fornire un funtore di confronto . Ciò richiede che gli intervalli siano ordinati nello stesso ordine in cui sarebbero se il funtore Confronta fosse utilizzato con std::sortsugli intervalli. Il funtore di confronto predefinito è qui std::less<>che, se non specializzato per il tipo coinvolto, utilizza operator<per confrontare gli elementi.

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

Which can then be called like this using the default Compare functor:

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

Or like below, supplying a Compare functor. In this example the ranges are required to be sorted in descending order:

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