c++ - 从第一个集合元素中删除第二个集合包含的元素而无需迭代

Question

我有两组对（我不能使用 c++11）

std::set<std::pair<int,int> > first;
std::set<std::pair<int,int> > second;

我需要从第一个集合中删除第二个集合中的所有元素（如果第一个包含第二个要删除的元素）。我可以通过迭代第二组来做到这一点，如果 first 包含从第一个元素中删除的相同元素，但我想知道有没有办法在没有迭代的情况下做到这一点？

Answer 1

如果我理解正确，基本上你想计算第一和第二的差异。有一个<algorithm>功能。

std::set<std::pair<int, int>> result;
std::set_difference(first.begin(), first.end(), second.begin(), second.end(), inserter(result, result.end()));

Answer 2

我想知道有没有办法在没有迭代的情况下做到这一点。

不。在内部，集合是平衡的二叉树——没有迭代结构就无法对它们进行操作。（我假设您对实现的效率感兴趣，而不是代码的便利性，所以我故意忽略了必须在内部迭代的库例程）。

但是集合是排序的，因此您可以对每个集合进行迭代，边走边删除（因此 # 操作是集合大小的总和）而不是迭代和查找每个元素（其中操作数是您的元素数'正在迭代时间以记录另一组中元素数量的基数 2）。只有当你的一组比另一组小得多时，迭代/查找方法才会胜出。如果您查看set_differenceAmen 的答案中提到的库函数的实现） - 它应该向您展示如何很好地进行两次迭代。

如果你想要更高效的东西，你需要考虑如何更早地实现它：例如，将你的对作为标志存储在相同大小的二维矩阵中，这样你就可以与第二组的否定进行 AND。这是否实用取决于您存储的 int 值的范围，所需的内存量是否适合您的目的......

Answer 3

是的你可以。

如果您想删除，而不仅仅是检测，这里还有另一个<algorithm>功能：remove_copy_if()：

http://www.cplusplus.com/reference/algorithm/remove_copy_if/

恕我直言。理解它的工作原理并不难。