Is there a way to loop over the elements in multiset or unordered_set while deleting and insert elements in c++

Question

I want to loop over each element in the multiset or unordered_set and during the loop, I could insert and remove the element. For example:

unordere_set<int> myset = { 1, 2, 3, 4 };
for (auto it = myset.begin(); it != myset.end(); ++it) {
    myset.erase(*it);
    // do something that needs to use the set without *it like in a recursion function that takes the reference of the set
    myset.insert(*it);      
}

I don't want to create a copy of the set since the set could be very large and it is not very efficient.

Answer 1

I don't see a problem with this code (untested though)

unordered_set<int> myset = { 1, 2, 3, 4 };
for (auto it = myset.begin(); it != myset.end(); ) {
    auto save = *it;
    it = myset.erase(it);
    // do something that needs to use the set without *it like in a recursion function that takes the reference of the set
    myset.insert(save);      
}

My reasoning is that mysave.insert(save) should not invalidate the iterator it because it will not cause rehashing of the unordered_set, since all you are doing is adding back an element that was previously deleted. But of course it does depend on exactly what you are doing with // do something ...

Answer 2

Try to avoid inserting and deleting while traversing. Here is a bad suggestion.

#include <vector>
#include <unordered_set>
using namespace std;

int main() {
  unordered_set<int> s { 1, 2, 3, 4, 5, 6, 7 };
  vector<unordered_set<int>::const_iterator> s_add;
  vector<unordered_set<int>::const_iterator> s_del;
  for (auto itr = s.begin(); itr != s.end(); ++itr) {
    // Some conditions
    s_add.push_back(itr);
    // Some conditions
    s_del.push_back(itr);
  }

  for (auto itr : s_add) {
    s.insert(*itr);
  }

  for (auto itr : s_del) {
    s.erase(itr);
  }

  return 0;
}

Answer 3

According to the cpprefrence, insertion may affect all the iterators over unordered_set container.

If rehashing occurs due to the insertion, all iterators are invalidated. Otherwise iterators are not affected. References are not invalidated. Rehashing occurs only if the new number of elements is greater than max_load_factor()*bucket_count().

If the insertion is successful, pointers and references to the element obtained while it is held in the node handle are invalidated, and pointers and references obtained to that element before it was extracted become valid.

I was wondering if you just want to iterate over a container and do some insert/delete operations on it, why don't you just use std::vector container and element indexes to insert/delete them.

If you insist on using unordered_set, you can use std::next in a while loop to iterate over your unordered_set container and do some insert/delete operation on it.

Note that because you will insert the same element at the end of the loop, it will not trigger the rehashing algorithm.

unordered_set<int> myset = { 1, 2, 3, 4 };
unordered_set<int>::iterator it = myset.begin();
int i = 0;

while (it != myset.end()) {

    myset.erase(*it);
    // do something that needs to use the set without *it like in a recursion function that takes the reference of the set
    myset.insert(*it);
    it = next(myset.begin(), ++i);
}

Answer 4

You can do something like this -

multiset<int> myset = { 1, 2, 3, 4 };
while(myset.begin()!=myset.end()) {
    myset.erase(myset.begin());
    //     or
    myset.erase(3);
}