如何在 C++ 中获取（无序）集差或对称差？

Question

我无法推断我可以使用文档中的 std::set_difference，因为它说集合应该是有序的，这意味着它们不是集合，而是列表。此外，所有示例都是关于有序列表，而不是集合。

如何知道真相？

Answer 1

std::set 已排序。查看 docs:

std::set is an associative container that contains a sorted set of unique objects of type Key. Sorting is done using the key comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Sets are usually implemented as red-black trees.

因此，您可以像使用任何其他提供所需接口的容器一样使用它。 std::set 和 e.g. 之间的区别std::vector 是 std::set 在插入时对其元素进行排序，在 std::vector 的情况下，您需要使用 std::sort 函数对其元素进行排序。

比如你需要std::set_difference换成std::unordered_set，你可以这样做：

#include <set>
#include <iostream>
#include <algorithm>
#include <unordered_set>

int main() {
    std::unordered_set<int> a {3, 1, 4, 6, 5, 9};
    std::unordered_set<int> b {3, 1, 4};

    std::set<int> c;
    std::set<int> d;
    std::copy(a.begin(), a.end(), std::inserter(c, c.end()));
    std::copy(b.begin(), b.end(), std::inserter(d, d.end()));

    std::vector<int> diff;

    std::set_difference(c.begin(), c.end(), d.begin(), d.end(), 
                        std::inserter(diff, diff.begin()));

    for (auto const i : diff)
        std::cout << i << ' ';

    return 0;
}

见live

Answer 2

std::set_difference 用于任意排序的输入（预排序的 std::vectors、std::lists、std::deques、普通数组等），它恰好也适用于 std::set（已排序）。

如果您正在使用 std::unordered_set（或 std::set，并且您可以就地操作），您只需使用 erase 方法删除所有从一个这样的集合中获取另一个集合中的元素以获得差异，例如：

for (const auto& elem : set_to_remove) {
    myset.erase(elem);
}

也可以做成新的集合with std::copy_if；那里的配方很容易适应对称差异的情况（它只是对 std::copy_if 的两次调用，其中每个调用都在一个输入集上运行，并且以其他输入集中不存在的元素为条件）。

如何在 C++ 中获取（无序）集差或对称差？

How to get (unordered) set difference or symmetric difference in C++?

c++

set

set-difference