bitmask bitmask -4 years ago 93
C++ Question

How to efficiently replace elements in an unordered_set while iterating over it?

Suppose you have an

std::unordered_set<std::shared_ptr<A>> as;
// (there is an std::hash<std::shared_ptr<A>> specialisation)


and you want to replace some of its elements while iterating over it:

for (auto it = as.begin(); it != as.end(); ++it) {
if ((*it)->condition()) {
as.erase(it);
as.insert(std::make_shared<A>(**it));
}
}


This could invalidate the iterator at
erase
and
insert
(if rehashing takes place), so this loop will exhibit undefined behaviour and will most likely crash horribly.

The one solution I can think of is using two separate
vector
s to buffer the
insert
and
erase
operations and later use the overloads that take iterator pairs for erasing and inserting (this is presumably more rehashing-friendly).

Even if I use the buffer approach, this still seems bloated code and could result in two rehashes that might possibly both be unnecessary.

So, is there a better way to do it?

Answer Source

I just thought of a possible approach (just after asking) but maybe there are even better ones.

Copying everything to a vector and then rebuilding the set from the vector should be faster:

std::vector<std::shared_ptr> buffer;
buffer.reserve(as.size());
for (auto it = as.begin(); it != as.end(); ++it) {
  if ((*it)->condition()) {
    buffer.push_back(std::make_shared<A>(**it));
  } else {
    buffer.push_back(*it);
  }
}
as = std::unordered_set<std::shared_ptr<A>>(buffer.begin(),buffer.end());
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download