vmrob vmrob - 5 days ago 9
C++ Question

How do I prevent rehashing of an std::unordered_map while removing elements?

I have an std::unordered_map that I will be removing elements from via iteration.

auto itr = myMap.begin();
while (itr != myMap.end()) {
if (/* removal condition */) {
itr = myMap.erase(itr);
} else {
++itr;
}
}


I would like to prevent the map for performing any expensive operations until I'm done removing all of the elements that I need to remove. Do I have a valid concern? Am I misunderstanding how the internal storage works?

NPE NPE
Answer

As far as I can tell, std::unordered_map is allowed to rehash on erase(itr):

C++11 Table 103 -- Unordered associative container requirements

a.erase(q)

Erases the element pointed to by q. Return value is the iterator immediately following q prior to the erasure.

Average case O(1), worst case O(a.size())

It would therefore seem that you do have a valid concern. As to addressing it, I can suggest several avenues:

  1. Make sure it's an actual problem rather than a hypothetical one. Profile the application, look at the source code for your C++ library, etc.
  2. If it is an actual problem, consider using a different container or a different algorithm.
  3. Consider simply marking the elements for deletion through a boolean flag associated with each element, and sweeping the deleted elements from time to time, thereby amortizing the costs.
  4. Consider experimenting with the load factor, as suggested by @amit in the comments. Even though the container would still be allowed to take O(a.size()) time to erase elements, a different load factor might have an effect on the real-world performance of your application.
Comments