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

Question

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

如何知道真相？

- Dims

Answer 1

std::set_difference适用于任意排序输入（预排序的std::vector，std::list，std::deque，普通数组等），它碰巧也能处理std::set（已排序）。

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

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

你还可以使用std::copy_if将其复制到一个新的集合中；那里的方法对于对称差分的情况非常容易适应（只需两次调用std::copy_if，每次运行在一个输入集上，并且是在元素不存在于另一个输入集中的条件下）。

- ShadowRanger

---

这个例子中的代码会导致段错误。std::set::erase 的使用仅适用于作为 myset 一部分的迭代器。请参见此处："删除范围 [first; last) 中的元素，该范围必须是 *this 中的有效范围。" - sasquires

@sasquires：哎呀，我的错。虽然不太优雅，但我用一个只迭代“set_to_remove”并使用“erase”的按值版本替换了糟糕的代码。谢谢你发现了这个问题！ - ShadowRanger

Answer 2

std::set是按顺序排序的。查看文档：

std::set是一个关联容器，它包含一组有序的唯一类型为Key的对象。排序使用键比较函数Compare完成。搜索、删除和插入操作具有对数复杂度。通常将集合实现为红黑树。

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

例如，如果您需要对std::unordered_set执行std::set_difference，可以按以下方式执行：

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

参见

- NutCracker

---

所以我需要无序集合。 - Dims