Giảm hai vectơ

Question

Tôi hy vọng rằng từ "phân rã" là đúng, nhưng vấn đề rất đơn giản: Tôi nhận được hai danh sách sau một thao tác và tôi muốn biết điều gì sẽ xảy ra từ danh sách này sang danh sách kia. Vì vậy, tôi muốn "phân tách" hai danh sách A và B thành "Cả hai", "Chỉ A" và "Chỉ 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++;
            }
        }
    }
}

Tôi cảm thấy cần có một cách nhanh hơn để thực hiện điều này hơn là ba vòng lặp đan xen hai lần.

Answer 1

Đối với thứ gì đó dễ đọc và dễ bảo quản, tôi sẽ sử dụng set_differencevà set_intersectionsẽ hoạt động tốt trên các phạm vi được sắp xếp mà không có bản sao:

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

... nhưng điều đó đòi hỏi bạn phải lặp lại phạm vi ba lần và tôi nghĩ bạn đang tìm kiếm thứ gì đó hiệu quả hơn.

Đầu tiên, tôi sẽ không bắt đầu bằng cách sao chép avà bvào only_avà only_btương ứng. Thay vào đó, hãy lấy cảm hứng từ các triển khai ví dụ cho các hàm tiêu chuẩn mà tôi đã liên kết ở trên và tạo thuật toán tương tự của riêng bạn. Điều này yêu cầu rằng Ts có thể được so sánh với 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));
}

Hoặc làm cho nó chung chung hơn và chỉ cho phép nó hoạt động với các trình vòng lặp và thêm khả năng cho người dùng cung cấp một bộ chức năng So sánh . Điều này yêu cầu các phạm vi phải được sắp xếp theo thứ tự giống như chúng sẽ có nếu công cụ So sánh được sử dụng với std::sortcác phạm vi. Chức năng So sánh mặc định ở đây std::less<>, nếu không chuyên biệt cho loại liên quan, sẽ sử dụng operator<để so sánh các phần tử.

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

Sau đó có thể được gọi như thế này bằng cách sử dụng chức năng So sánh mặc định :

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

Hoặc giống như bên dưới, cung cấp một trình so sánh . Trong ví dụ này, các phạm vi bắt buộc phải được sắp xếp theo thứ tự giảm dần:

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