Thread: iterating through a std::set, removing and adding elements back

Hi, I am trying to remove an element of a std::set at a time, then add it back, without invalidating the iterator, is it possible?

eg.

Code:

void someFunction(const std::set<int> &someset);
...

for (std::set<int>::iterator it = someset.begin(); it != someset.end(); ++it) {
	int removedValue = *it;
	someset.erase(it);
	someFunction(someset);
	someset.insert(removedValue);
}

is it possible without copying the set? (or should the above code snippet work?)

Thank you very much

By the way, what exactly are you doing, as it seems rather awkward to erase and insert each item in the set? Perhaps pass the value of the item to ignore and skip it in the loops in someFunction?

this is actually part of someFunction (a recursive function), so passing the value of the item to ignore is not possible (easily).

In the code you suggested, would the relative position of the iterator be reserved? eg, if someset is (1, 2, 3, 4, 5), and the removedValue is 3, would "it" point to 4 at the beginning of the block on the next iteration? (with 5 left to go)

Thank you

A set is sorted automatically so you will definitely point in the right area.

I understand this logic, but is it guranteed by the standard? (is a set required to be sorted?)

Actually, if someFunction is recursively modifying the set

someFunction doesn't modify the set in the sense that data in the set is the same at the beginning and when the function returns. (it is only modified by removing and subsequently adding back elements)

Thank you

>> I understand this logic, but is it guranteed by the standard?
Yes.

>> someFunction doesn't modify the set in the sense that data in the set is the same at the beginning and when the function returns. (it is only modified by removing and subsequently adding back elements)

If you saved the iterator, then called someFunction, and then someFunction removed and re-inserted the value that was referred to by the saved iterator, then you'd have a problem. I don't think removing or inserting invalidate other iterators, but they definitely invalidate any iterators to the element that was removed and re-inserted.

i think i get it now. But just to make sure - so something like this would work:

Code:

void someFunction(std::set<int> &someset);
...

for (std::set<int>::iterator it = someset.begin(); it != someset.end(); ++it) {
	int removedValue = *it;
	someset.erase(it);
	someFunction(someset);
	it = someset.insert(removedValue);
}

but it is not possible to do the optimization you mentioned because "it" would be invalidated by the time someFunction returns.

Is that correct?

Thank you very much for your help

Yes. I can't say with 100% certainty, but I'm pretty sure that's fine.

on a second thought, why would removing and inserting an element invalidate the iterator? if it is guaranteed that erasing a value and inserting it back puts it back to where it used to be, and an iterator is like a pointer to an element in the data structure, shouldn't the iterator still be valid?

As an experiment, I wrote this:

Code:

#include <iostream>
#include <set>

int main() {
	std::set<int> s;
	s.insert(1);
	s.insert(2);
	s.insert(3);

	std::set<int>::iterator before = s.find(2);

	s.erase(before);
	//s.erase(2) works, too

	s.insert(2);

	std::cout << (s.find(2) == before) << std::endl;
}

on my configuration (gcc 4.1.3 on Linux), the output is "1", suggesting that the iterator is still valid. Is this behaviour implementation specific?

Thank you

Yes, it would be both implementation specific and situation specific. For a small sample size it might put it back in the same place, but in a large program something else could come and take up that memory and then the re-inserted item would be placed somewhere else.

Basically, it isn't guaranteed and it is very possible for it not to work, so it's not worth it just for a potential optimization. In most cases that optimization won't make much difference with the application's speed anyway. If it was guaranteed to work I'd recommend it because there's no reason to avoid optimization if it has no other side effects. In this case, though, it does have the extremely important side effect that it might cause your program to fail.

I see what you mean. Thank you very much for your help and great explanations.

I don't see how it = someset.insert(removedValue); can work. These are the only overloads I see for set.insert():

Code:

pair<iterator, bool> insert(const value_type& x);
iterator insert(iterator it, const value_type& x);
void insert(const value_type *first, const value_type *last);

Originally Posted by MSDN

The second member function returns insert(x), using it as a starting place within the controlled sequence to search for the insertion point. (Insertion can occur in amortized constant time, instead of logarithmic time, if the insertion point immediately follows it.)

So shouldn't the code be more like this:

Code:

void someFunction(std::set<int> &someset);
...

for (std::set<int>::iterator it = someset.begin(); it != someset.end(); ++it) {
	int removedValue = *it;
	it = someset.erase(it);
	--it;
	someFunction(someset);
	it = someset.insert(it, removedValue);
}

If you're referring to the optimization I mentioned earlier, then you might be right, but I don't think so. Technically the iterator refers to the correct location where the item would be inserted, so it would be a good hint. But maybe a better hint is the position just before that.

Regardless, that optimization isn't appropriate here. anon's solution using it = someset.insert(removedValue); does work because it uses the first overload. It returns the pair, and the first item in the pair is the new iterator to the inserted object. You can then use that to continue looping.

>> Which iterator are you referring to?
The iterator erase() returns. It refers to the next element in the set. The correct place to insert the erased element is before that location. I believe the common idiom for STL containers when inserting with an iterator, is to insert the object before the element pointed to by the iterator, so the iterator returned by erase() would make sense as the hint.

If the set is (1, 2, 3, 4, 5), and you erase 3, then the iterator returned by erase points to 4.

If you were using a list, and you wanted to insert 3 into the proper place in a list of (1, 2, 4, 5), you would first make an iterator point to the 4, then use my_list.insert(iter, 3);.

So, I'm assuming, but don't know for sure, that the hint would work the same way. To hint that the 3 should come before the 4, pass an iterator that points to the 4 as the hint.

In fact, that's the only way to do it. Otherwise, how would you hint that you want the item to be placed at the front? The begin() iterator points to the spot after you want, so it has to work that way.

>> You mean the one where he suggested: it = someset.insert(removedValue).first;
Yes, I meant the one with the .first. It doesn't matter if the insert fails or not. If it does fail, then the iterator points to the element that was already in the set (the only reason it can fail is because the value already exists).