Create an unordered_map
to offsets into a std::vector
.
Store your elements in the std::vector
. When you want to remove an element, swap it with the last element of the std::vector
, and delete the last element. Go through the unordered_map
s that store indexes into your std::vector
and repair those that pointed to the last element to point to where the last element now is.
Removing an element is now O(n). If you remove a bunch of elements at once, you can do all of them in one O(n) pass with a little creativity.
Adding an element remains O(1).
Iterating over all of the elements involves iterating over the std::vector
. If you need the hash value while iterating, store it redundantly there, or calculate it on the fly.
Wrap the std::vector
and std::unordered_map
behind a type that enforces the above rules, as otherwise the invariants will never persist, that exposes a map
-like interface externally.
As an alternative to O(n) removal, create a parallel std::vector
storing std::unordered_map<
???>::iterator
s. Keep careful track of when a rehash occurs in the std::unordered_map
(rehashing is deterministic, but you have to work out when it happens yourself), and when it does rebuild it (as all of the iterator
s will be invalidated by a rehash). Rehashes occur rarely, so this has an amortized constant cost1. When you want to erase, you can now update the index in the unordered_map
in O(1) time (remember to update the second std::vector
as well -- swapping position from last to the deleted element). You could store this in the same std::vector
as the raw data, but that would bulk it up (which will slow down iteration).
1 Rehashes happen when the container passes reaches max_load_factor()*bucket_count()
size. The bucket_count
then grows exponentially, and the elements are moved around. Much like a std::vector
's growth algorithm, this guarantees a linear-in-number-of-elements total elements moved -- so it maintains amortized constant insertion. The manual rebuild of your reverse table is no more expensive than the moving of all of the existing elements, so it also contributes an amortized constant insertion time factor.