Cách tính kích thước giao điểm của hai bộ STL trong C++

Question

Tôi có hai bộ (std :: đặt từ <set>) trong đó tôi muốn biết kích thước của giao lộ. Tôi có thể sử dụng std :: set_intersection từ <algorithm>, nhưng tôi phải cung cấp cho nó một bộ lặp đầu ra để sao chép giao lộ vào một số vùng chứa khác.

Một cách đơn giản sẽ là

set<int> s1{1,2,3,4,5}; 
    set<int> s2{4,5,6,7,8,9,0,1}; 

    vector<int> v; 

    set_intersection(
     s1.begin(), s1.end(), s2.begin(), s2.end(), 
     inserter(v, v.begin())); 

sau đó v.size() cung cấp cho các kích thước của giao lộ. Tuy nhiên, giao lộ cũng sẽ được lưu trữ, mặc dù chúng tôi không làm gì với nó.

Để tránh điều đó, tôi cố gắng thực hiện một lớp đầu ra iterator giả, mà chỉ đếm, nhưng nó không gán:

template<typename T> 
class CountingOutputIterator { 
private: 
    int* counter_; 
    T dummy_; 
public: 
    explicit CountingOutputIterator(int* counter) :counter_(counter) {} 
    T& operator*() {return dummy_;} 
    CountingOutputIterator& operator++() { // ++t 
    (*counter_)++; 
    return *this; 
    } 
    CountingOutputIterator operator++(int) { // t++ 
    CountingOutputIterator ret(*this); 
    (*counter_)++; 
    return ret; 
    } 
    bool operator==(const CountingOutputIterator& c) { 
    return counter_ == c.counter_; // same pointer 
    } 
    bool operator!=(const CountingOutputIterator& c) { 
    return !operator==(c); 
    } 
}; 

sử dụng mà chúng tôi có thể làm

set<int> s1{1,2,3,4,5}; 
    set<int> s2{4,5,6,7,8,9,0,1}; 

    int counter = 0; 
    CountingOutputIterator<int> counter_it(&counter); 
    set_intersection(
     s1.begin(), s1.end(), s2.begin(), s2.end(), counter_it); 

sau đó bộ đếm giữ kích thước của giao lộ.

Tuy nhiên, đây là mã nhiều hơn nữa. Câu hỏi của tôi là:

1) Có cách nào (thư viện) tiêu chuẩn hoặc thủ thuật tiêu chuẩn để có được kích thước giao lộ mà không lưu trữ toàn bộ giao lộ không? 2) Không phụ thuộc vào việc có hay không, là cách tiếp cận với trình lặp giả định tùy chỉnh hay không?

Answer 1

Nó không khó để viết một vòng lặp mà di chuyển qua hai bộ tìm kiếm phù hợp với các yếu tố, hoặc bạn có thể làm được điều này, đó là đơn giản hơn nhiều so với một iterator tùy chỉnh:

struct Counter 
{ 
    struct value_type { template<typename T> value_type(const T&) { } }; 
    void push_back(const value_type&) { ++count; } 
    size_t count = 0; 
}; 

template<typename T1, typename T2> 
size_t intersection_size(const T1& s1, const T2& s2) 
{ 
    Counter c; 
    set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(c)); 
    return c.count; 
} 

Answer 2

Bạn có thể làm điều này:

auto common = count_if(begin(s1), end(s1), [&](const auto& x){ return s2.find(x) != end(s2); }); 

Đó không phải là cách tối ưu hiệu quả nhưng phải đủ nhanh đối với hầu hết các mục đích.

Answer 3

Không khó để viết một hàm thực hiện điều này. This cho thấy cách set_intersection được thực hiện [mặc dù việc thực hiện thực tế có thể đương nhiên được tinh tế khác nhau]

Vì vậy, chúng ta có thể chỉ mất mã, và sửa đổi nó một chút:

template <class InputIterator1, class InputIterator2> 
    size_t set_intersection_size (InputIterator1 first1, InputIterator1 last1, 
           InputIterator2 first2, InputIterator2 last2) 
{ 
    size_t result = 0; 
    while (first1!=last1 && first2!=last2) 
    { 
    if (*first1<*first2) ++first1; 
    else if (*first2<*first1) ++first2; 
    else { 
     result++; 
     ++first1; ++first2; 
    } 
    } 
    return result; 
} 

Mặc dù kinh nghiệm của tôi, khi bạn muốn biết có bao nhiêu người trong giao lộ, bạn thường sớm hay muộn cũng muốn biết những yếu tố nào.

Answer 4

Bạn có thể đơn giản hóa việc sử dụng cách tiếp cận của bạn một chút công bằng:

struct counting_iterator 
{ 
    size_t count; 
    counting_iterator& operator++() { ++count; return *this; } 
    // other iterator stuff 
}; 

size_t count = set_intersection(
    s1.begin(), s1.end(), s2.begin(), s2.end(), counting_iterator()).count;