How do we iterate through all elements of a set while inserting new elements to it?

Question

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.

output is 3 4 5 6

1,2 are not printed.

how do we code such a situation.

Answer 1

Actually, the iterator is still 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.

Answer 2

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).

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.

Answer 3

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.

    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, this says:

Set has the important property that inserting a new element into a set does not invalidate iterators that point to existing elements.

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.

Answer 4

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

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.

It's still not clear why you'd want to insert the list after getting an iterator. Why can't you insert the elements before iterating over them, like @camh has mentioned?

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.

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.