CODEWITHSUNDEEP
c++iteratorreplaceunordered-set
bitmask
bitmask

Reputation: 34628

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 vectors 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?

Upvotes: 3

Views: 2453

Answers (4)

user666412
user666412

Reputation: 518

I'd put this as a comment on @bitmask's answer. Why not just use the vector for the replaced elements?

std::vector<decltype(as)::value_type> buffer;
buffer.reserve(as.size());
for (auto it = as.begin(); it != as.end(); )
{
  if ((*it)->condition())
  {
    buffer.push_back(*it);
    it = as.erase(it);
  }
  else
  {
    ++it;
  }
}
as.insert(buffer.begin(),buffer.end());

And, if *it is already a shared_ptr<A>, I fail to see a reason to make_shared() again. Just assign and let the copy constructor/assignment operators work their magic.

Upvotes: 0

zahir
zahir

Reputation: 1432

In your case you can just swap in my opinion:

for(auto iter = as.begin(); iter != as.end(); ++iter)
{
    if(/*Check deletion condition here*/)
    {
        auto newItem = std::make_shared<A>(/*...*/);
        swap(*iter, newItem);
    }
}

Upvotes: -1

Dietmar K&#252;hl
Dietmar K&#252;hl

Reputation: 153810

When you call as.erase(it) the iterator it become invalidated. Inserting into an unordered associative containers invalidates all iterators. Thus, the insertion needs to be separated from the iterator. Avoiding the insertions is also necessary to avoid processing the newly inserted objects:

std::vector<std::shared_ptr<A>> replaced;
for (auto it = as.begin(); it != as.end(); ) {
    if ((*it)->condition()) {
        replaced.push_back(std::make_shared<A>(**it));
        as.erase(it++);
    }
    else {
        ++it;
    }
}
std::copy(replaced.begin(), replaced.end(), std::inserter(as, as.begin());

Upvotes: 1

bitmask
bitmask

Reputation: 34628

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());

Upvotes: 1

Related Questions