3

我有这个代码：

set<int>::iterator new_end = 
                   set_difference(set1.begin(), set1.end(),
                                  set2.begin(), set2.end(),
                                  set1.begin());
set1.erase(new_end, set1.end);

它在 Visual Studio 中编译并运行良好。但是，在之前的问题中，人们说 aset的迭代器应该是const. 我在标准中没有看到类似的东西。有人可以告诉我它在哪里说的，或者这是否是明确定义的行为？

如果不是，请提供我需要的代码。有没有办法在不创建临时集的情况下做到这一点？

4

5 回答 5

7

您的代码违反了set_difference. 从Josuttis Book的第 420 页开始：

  • 调用者必须确保目标范围足够大或使用插入迭代器。
  • 目标范围不应与源范围重叠。

您正在尝试回写第一组，这是不允许的。您需要在源范围以外的地方编写 - 为此我们可以使用第三组：

std::set<int> set3;
std::set_difference(set1.begin(), set1.end(),
                    set2.begin(), set2.end(),
                    std::inserter(set3, set3.begin()));

to 的第二个参数std::inserter是提示元素应该插入的位置。这只是一个提示，但是请放心，这些元素最终会出现在正确的位置。 set3最初是空的，所以begin()是我们可以给出的唯一提示。

调用后set_difference，set3将包含您试图set1在原始代码中包含的内容。如果您愿意，您可以继续使用set3或使用swap它。set1

更新：

我不确定这个的性能，但如果你只想删除set1出现在的所有元素set2，你可以尝试：

for (std::set<int>::iterator i = set2.begin(); i != set2.end(); ++i)
{
    set1.erase(*i);
}
于 2009-05-26T20:45:42.953 回答
5

解决它的一个建议：

std::set<int> tmp;
std::set_difference(set1.begin(), set1.end(),
                    set2.begin(), set2.end(),
                    std::inserter(tmp, tmp.begin()));
std::swap(tmp, set1);

我想不出不使用临时集的方法（除了遍历容器并对单个元素进行擦除）。

于 2009-05-26T20:39:00.487 回答
4

不，这不对。来自SGI STL 参考

  1. [first1, last1) 和 [result, result + n) 不重叠。
  2. [first2, last2) 和 [result, result + n) 不重叠。

另外，正如 Nikolai N Fetissov 指出的那样，我不确定 begin() 是否可以用作 OutputIterator。

于 2009-05-26T20:24:41.390 回答
1

的第五个参数set_difference应该是一个OutputIterator，见文档。

于 2009-05-26T20:17:20.437 回答
1

C++ 标准没有明确表示不允许分配给 set 迭代器，但它确实为 set_difference 指定“结果范围不应与任何一个原始范围重叠”（25.3.5.3）。

到目前为止，它可能对你有用，只是因为你对 set1 和 set2 的内容很幸运。

于 2009-05-26T20:46:43.107 回答