计算一个集合中不同于另一个集合的元素数

Question

set_difference算法为您提供第一个范围内而不是第二个范围内的元素的输出。有没有一种算法只会给我计数，而不是差值。

我知道我可以实现我自己版本的链接中描述的算法，或者我可以在得到结果后计算元素的数量。是否有一个现有的API可以有效地为我做这件事。

感谢

Answer 1

您只需编写自己的类似OutputIterator的东西，就可以将其传递到std::set_difference中。OutputIterator需要是可取消引用的、可分配的和可递增的。还要注意，std::set_difference返回一个OutputIterator，因此我们可以通过将其转换为int来利用它。

因此类似于：

struct CountingIterator
    : std::iterator<std::output_iterator_tag, int>
{
    template <typename T>
    CountingIterator& operator=(T&& ) {
        ++count;
        return *this;
    }
    CountingIterator& operator*() { return *this; }
    CountingIterator& operator++() { return *this; }
    operator int() { return count; }
    int count = 0;
};

当修改std::set_difference中的示例时，会产生以下结果：

int main() {
    std::vector<int> v1 {1, 2, 5, 5, 5, 9};
    std::vector<int> v2 {2, 5, 7};
    int count = 
        std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), 
                        CountingIterator());
    std::cout << count << std::endl; // prints 4
}

Answer 2

这是一个非常琐碎的操作，不需要特定的方法。如果你负担不起分配一个临时集来计算差异，然后得到它们的大小，只需使用std::accumulate或std::for_each:计算即可

unordered_set<int> set1 = {1,2,3,4,5};
unordered_set<int> set2 = {2,4,6};    
size_t count = set1.size() - std::accumulate(set1.begin(), set1.end(), 0, [&set2](size_t previous, int value) { return set2.count(value) + previous; });

但如果你没有任何特定的要求或庞大的集合，那么做set_difference+size()就可以了。

Answer 3

您可以创建一个"CountingIterator"作为OutputIterator，类似于：

struct CountingIterator
{
    CountingIterator& operator*() { return *this; }  
    CountingIterator& operator ++() { return *this; }
    CountingIterator& operator ++(int) { return *this; }
    template <typename T>
    CountingIterator& operator =(const T&) { ++counter; return *this; }
    int counter = 0;
};