如何计算C++中两个STL集的交集的大小

Question

我给出了两组（从std :: <set>设置std ::），我想知道大小的交集。我可以使用<algorithm>中的std :: set_intersection，但我必须为它提供一个输出迭代器以将交集复制到其他容器中。

一个直接的方法将是

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

之后v.size（）给出了交集的大小。但是，交叉点也必须存储，即使我们对此不做任何处理。

为了避免这种情况，我想实现一个虚拟输出迭代器类，仅计算，但它不会给：

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

使用，我们可以做

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

之后计数器保存交集的大小。

然而，这是更多的代码。我的问题是：

1）是否有标准（库）方式或标准技巧来获取交叉点的大小而不存储整个交集？ 2）独立于是否存在，是否使用自定义虚拟迭代器是一种好方法？

Answer 1

这并不难写一个循环，通过两套移动寻找匹配的元素，或者你可以做到这一点，这是比一个自定义的迭代器简单得多：

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

你可以这样做：

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

这不是最为有效的，但应该是多数目的不够快。

Answer 3

编写这样做的函数并不是很难。 This展示了如何set_intersection完成[虽然实际执行当然可以是微妙的不同]

因此，我们可以只取代码，并修改它一点点：当

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

虽然在我的经验，你想知道交叉口有多少人，你通常迟早会想知道哪些元素。

Answer 4

可以简化的使用你的方法一点点：

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;