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

This is a discussion on iterating through a std::set, removing and adding elements back within the C++ Programming forums, part of the General Programming Boards category; Hi, I am trying to remove an element of a std::set at a time, then add it back, without invalidating ...

  1. #1
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,170

    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

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    The set's insert method should return you a pair of <iterator, bool> which you could use.

    Something like this (untested)
    Code:
    for (std::set<int>::iterator it = someset.begin(); it != someset.end(); ++it) {
    	int removedValue = *it;
    	someset.erase(it);
    	someFunction(someset);
    	it = someset.insert(removedValue).first;
    }
    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?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,170
    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

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    A set is sorted automatically so you will definitely point in the right area. The only question is whether the code points at the inserted element or the next element. I'm pretty sure it points at the inserted element, so then the ++it in the for loop would correctly move to the next element.

    Also note that you can speed up insertion is you save the return value of erase, then use that as a hint of where to insert.

    [edit] Actually, if someFunction is recursively modifying the set, then this might be a bad idea because the saved it iterator could be invalidated as you already mentioned... so never mind.
    Last edited by Daved; 12-01-2007 at 04:50 PM.

  5. #5
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,170
    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

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> 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.

  7. #7
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,170
    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

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    Yes. I can't say with 100&#37; certainty, but I'm pretty sure that's fine.

  9. #9
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,170
    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

  10. #10
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    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.

  11. #11
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,170
    I see what you mean. Thank you very much for your help and great explanations.

  12. #12
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    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);
    Quote 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);
    }

  13. #13
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    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.

  14. #14
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by Daved View Post
    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.
    Which iterator are you referring to? The one that erase() returns, the invalidated one passed to erase() or the one insert() returns?

    Here's what the MSDN says about set::erase()
    The first member function removes the element of the controlled sequence pointed to by it. The second member function removes the elements in the range [first, last). Both return an iterator that designates the first element remaining beyond any elements removed, or end() if no such element exists.
    Which is why I moved back one from the one that erase() returned.

    Quote Originally Posted by Daved View Post
    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.
    You mean the one where he suggested: it = someset.insert(removedValue).first;
    I missed the .first when I read it, so yeah that should work, although it doesn't check the bool to see if the insert() failed and I'm not sure whether the iterator would be in a valid state if insert() fails.
    Last edited by cpjust; 12-02-2007 at 01:37 AM.

  15. #15
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> 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).

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21