以下代码是否使用std::set“合法”？

Question

我有这段代码：

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中编译和运行得很好。然而，在之前的问题中，人们表示set的迭代器应该是const。我没有在标准中看到这样的说明。有人能告诉我在哪里可以找到这个说明，或者这是否是明确定义的行为吗？

如果不是，请提供满足我的需求的代码。有没有一种方法可以在不创建临时set的情况下实现这一点？

- rlbond

Answer 1

您的代码违反了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()));

std::inserter的第二个参数是一个提示，用于指示元素应插入的位置。然而，这只是一个提示，您可以放心，元素最终会出现在正确的位置上。由于set3最初为空，因此我们能够提供的提示只有begin()。

调用set_difference后，set3将包含您在原始代码中尝试使set1包含的内容。如果您喜欢，可以继续使用set3或将其与set1交换。

更新：

我不确定这样做的性能如何，但如果您只想从set1中删除所有出现在set2中的元素，可以尝试：

for (std::set<int>::iterator i = set2.begin(); i != set2.end(); ++i)
{
    set1.erase(*i);
}

- Michael Kristofik

Answer 2

一种解决方法是：

一个建议解决此问题：

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

除了迭代容器并对个别元素执行erase操作外，我无法想到不使用临时集合的方法来完成它。

- CAdaker

Answer 3

不，不是这样的。来自SGI STL参考手册。

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

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

- Harper Shelby

Answer 4

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

- Nikolai Fetissov

Answer 5

C++标准并没有明确规定将值分配给set迭代器是不允许的，但它确实指定了对于set_difference，“生成的范围不得与原始范围重叠”（25.3.5.3）。

这可能之前可以工作，只是因为您运气好，set1和set2的内容刚好适合。

- Nathan Kitchen