3
\$\begingroup\$

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.

\$\endgroup\$
5
  • 2
    \$\begingroup\$ Is the sort order in the result important? Does it matter if the result is sorted? Is the input sorted? If not, is it ok to sort it? Also, is there a reason for limiting it to pointers? \$\endgroup\$
    – Ted Lyngmo
    Sep 10, 2020 at 23:24
  • \$\begingroup\$ No, it was just that pointers were what I got (the existance of a == operator is what was important or else there is no "sameness" to have the "both" defined). I have the feeling like the answers are very different depending on sortedness, so I am rather interested in both cases. Right now this is just data, so maybe there isn't even a way to sort the lists anyway. As such pointers also help as there is an order on addresses. Though to be precise: In my particular case where I actually use this function I HAVE to use pointers as I decompose lists of UI Elements that are beneath a mouse. \$\endgroup\$
    – salbeira
    Sep 10, 2020 at 23:40
  • 1
    \$\begingroup\$ If you can compare them for equality you can usually sort them, but that's perhaps not that important. Are there duplicates? I'm asking all this because a possible answer could include std::set_difference and std::set_intersection like in this example - but it does come with some limitations. \$\endgroup\$
    – Ted Lyngmo
    Sep 10, 2020 at 23:47
  • \$\begingroup\$ No duplicates should be in the tree structure these lists drop out of (they each represent the list of elements beneath a mouse cursor and usually this means that each item is part of only one branch of the ui element tree (I do not know of any ui element that can be part of two pieces of an interface at once) \$\endgroup\$
    – salbeira
    Sep 10, 2020 at 23:50
  • 1
    \$\begingroup\$ Welcome to CodeReview@SE. (intertwined loops made me think of coroutines, nested would seem more common.) \$\endgroup\$
    – greybeard
    Sep 11, 2020 at 5:59

1 Answer 1

4
\$\begingroup\$

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.

First, I would not start by copying a and b into only_a and only_b respectively. Instead, take inspiration from the example implementations for the standard functions I linked to above and create your own similar algorithm. This requires that Ts can be compared with 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));
}

Or make it even more generic and let it work with iterators only and add the possibility for the user to supply a Compare functor. This do require the ranges to be sorted in the same order as they would be if the Compare functor was used with std::sort on the ranges. The default Compare functor is here std::less<> that, if not specialized for the type involved, uses operator< to compare the elements.

#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<>
);
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.