c++ - 计算一组中与另一组不同的元素数量

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::accumulateor计算它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" as 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;
};