두 벡터 분해

Question

"분해"라는 단어가 정확하길 바라지 만 문제는 간단합니다. 작업 후 두 개의 목록이 있고 한 목록에서 다른 목록으로 어떤 변화가 발생했는지 알고 싶습니다. 따라서 두 개의 목록 A와 B를 "Both", "Only A"및 "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++;
            }
        }
    }
}

두 번 얽힌 3 개의 루프보다 더 빠른 방법이 있어야한다고 생각합니다.

Answer 1

읽고 유지 관리하기 쉬운 것을 사용 set_difference하고 set_intersection중복이없는 정렬 된 범위에서 잘 작동합니다.

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

...하지만이를 위해서는 범위를 세 번 반복해야하며 더 효율적인 것을 찾고 있다고 생각합니다.

첫째, 나는 복사하여 시작되지 것입니다 a및 b에 only_a와 only_b각각. 대신 위에 링크 한 표준 함수에 대한 예제 구현에서 영감을 얻어 자신 만의 유사한 알고리즘을 만듭니다. 이를 위해서는 Ts를 다음과 비교할 수 있어야합니다 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));
}

또는 더 일반적으로 만들고 반복자에서만 작동하도록하고 사용자가 비교 펑터 를 제공 할 수있는 가능성을 추가 하십시오 . 이를 위해서는 범위에서 비교 펑터가 사용 된 경우와 동일한 순서로 범위를 정렬 std::sort해야합니다. 기본 비교 펑 터는 std::less<>관련된 유형에 대해 전문화되지 않은 경우 operator<요소를 비교하는 데 사용 합니다.

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

그런 다음 기본 비교 펑터를 사용하여 다음과 같이 호출 할 수 있습니다 .

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

또는 아래와 같이 비교 펑터를 제공합니다 . 이 예에서는 범위를 내림차순으로 정렬해야합니다.

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