C++ 我们如何在向集合中插入新元素的同时遍历集合的所有元素？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1547066/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How do we iterate through all elements of a set while inserting new elements to it?
提问by Rohit Banga
consider this:
考虑一下：
// set_iterator.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include <iostream>
#include <set>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
set<int> a1;
set<int> a2;
a1.insert(3);
a1.insert(4);
a1.insert(5);
a2.insert(1);
a2.insert(2);
a2.insert(6);
set<int>::iterator iter;
int x = 0;
for (iter = a1.begin(); iter != a1.end(); ++iter)
{
if (x == 0) {
x = 1;
a1.insert(a2.begin(), a2.end());
}
cout << *iter << endl;
}
system("pause");
return 0;
}
goal is to visit each element of the set exactly once. i think the iterator is not valid after we insert elements into a1.
目标是只访问集合中的每个元素一次。我认为在我们将元素插入 a1 后迭代器无效。
output is 3 4 5 6
输出为 3 4 5 6
1,2 are not printed.
1,2 不打印。
how do we code such a situation.
我们如何编码这种情况。
采纳答案by rlbond
Actually, the iterator isstill valid. A set is a node-based container.
事实上，迭代器是仍然有效。集合是基于节点的容器。
The problem is that in a set the elements are always sorted. Before insertion, your set looks like this:
问题在于集合中的元素总是被排序的。在插入之前，您的集合如下所示：
3 4 5
^
iter
After insertion, your set looks like this:
插入后，您的集合如下所示：
1 2 3 4 5 6
^
iter
You'll have to use a different container if you want to be able to do what you're doing.
如果您希望能够做您正在做的事情，您将不得不使用不同的容器。
回答by rocketmonkeys
i want to visit each element of the set exactly once as its size increases while traversal. any way to do this? – iamrohitbanga 1 hour ago
我想在遍历时随着其大小的增加而恰好访问该集合的每个元素一次。有什么办法可以做到这一点？– iamrohitbanga 1 小时前
In your code, a1 = [3, 4, 5]. Then you get an iterator that points to the start of a1, which is '3'. Then you insert new elements into a1, resulting in [1, 2, 3, 4, 5, 6]. However, you're still pointing to the same value, '3'. So now you keep iterating and you'll print 3, 4, 5, 6.
在您的代码中，a1 = [3, 4, 5]。然后你会得到一个指向 a1 开头的迭代器，它是 '3'。然后将新元素插入 a1，结果为 [1, 2, 3, 4, 5, 6]。但是，您仍然指向相同的值“3”。所以现在你继续迭代，你将打印 3、4、5、6。
It's still not clear why you'd want to insert the list aftergetting an iterator. Why can't you insert the elements beforeiterating over them, like @camh has mentioned?
目前还不清楚为什么要在获得迭代器后插入列表。为什么不能在迭代之前插入元素，就像@camh 提到的那样？
If you still want to do this, use a vector since that will allow you to append elements to the end of the list, meaning that you'll still be pointing to '3', but the list will now be [3, 4, 5, 1, 2, 6] and those will print out in that order.
如果您仍然想这样做，请使用向量，因为这将允许您将元素附加到列表的末尾，这意味着您仍将指向“3”，但列表现在将是 [3, 4, 5, 1, 2, 6] 和那些将按该顺序打印出来。
Or, add this:
或者，添加以下内容：
for (iter = a1.begin(); iter != a1.end(); ++iter)
{
if (x == 0) {
x = 1;
a1.insert(a2.begin(), a2.end());
// Reset the iterator since we've modified the list
iter = a1.begin();
}
cout << *iter << endl;
}
This is ugly hacked code, and will only work in this specific circumstance. The better solution is @camh's. If you have some reason you can't do it that way, then we need more details.
这是丑陋的黑客代码，只能在这种特定情况下工作。更好的解决方案是@camh's。如果您有某种原因不能那样做，那么我们需要更多详细信息。
回答by R Samuel Klatchko
The issue is not iterator validity.
问题不是迭代器有效性。
The issue is that set does not have any defined order (although in this case, it's choosing sorted order, but I do not believe the complexity requirements of STL require that - another implementation may choose another order).
问题是 set 没有任何定义的顺序（尽管在这种情况下，它选择了排序顺序，但我不相信 STL 的复杂性要求要求 - 另一个实现可能会选择另一个顺序）。
So any iterators are still valid after you call insert (so you may continue to deref the pointer and advance it and it is guaranteed to still reach end()). But any elements inserted may come 'before' your iterator and you will not see them unless you call begin() again.
因此，在您调用 insert 之后，任何迭代器仍然有效（因此您可以继续取消引用指针并推进它，并保证它仍然到达 end()）。但是插入的任何元素都可能出现在您的迭代器之前，除非您再次调用 begin()，否则您将看不到它们。
回答by camh
how do we code such a situation.
我们如何编码这种情况。
You recognise that the code within the "if (x == 0)" block is executed only once and that nothing in that block references the loop variable(s), and as such, should be moved outside the loop.
您认识到“if (x == 0)”块中的代码只执行一次，并且该块中的任何内容都没有引用循环变量，因此应该将其移到循环之外。
a1.insert(a2.begin(), a2.end());
for (iter = a1.begin(); iter != a1.end(); ++iter)
{
cout << *iter << endl;
}
I don't know if your real code can be refactored in a similar way, but with regard to the validity of your iterator after insertion, thissays:
我不知道你的真实代码是否可以用类似的方式重构，但关于插入后迭代器的有效性，这说：
Set has the important property that inserting a new element into a set does not invalidate iterators that point to existing elements.
Set 有一个重要的特性，即向集合中插入新元素不会使指向现有元素的迭代器失效。
So, your iterator remains valid, but you cannot necessarily assume that all the elements inserted will come "after" the current position and that they will be reached by any current Forward Iterators.
因此，您的迭代器仍然有效，但您不能假设所有插入的元素都将出现在当前位置“之后”，并且任何当前的前向迭代器都会到达它们。
