Why does C++'s unordered_map::erase fully invalidate iterators, not even supporting advancing?

Question

The documentation on C++'s unordered_map::erase states:

Removes specified elements from the container. The order of the remaining elements is preserved. (This makes it possible to erase individual elements while iterating through the container.)

This is basically what I would expect from your average hash map with closed hashing: Entries aren't truly "deleted", space is not reclaimed; entries are merely marked as deleted, and we have to assume that their contents may now be garbage.

Given this, I would have assumed the following to be supported:

std::unordered_map<int, std::string> m = {
    {-1, "one"}, {-2, "two"}, {-3, "three"},
    {-4, "four"}, {-5, "five"}, {-6, "six"}
};
for (auto it = m.begin(); it != m.end(); ++it)
    if (it.first % 2 == 0)
        m.erase(it);

but it isn't. Contrast this with Lua, where the following works just fine:

-- negative keys to ensure that these don't end up in the "list" part internally
local m = {
    [-1] = "one", [-2] = "two", [-3] = "three",
    [-4] = "four", [-5] = "five", [-6] = "six",
}
-- next to be explicit (this is what pairs uses under the hood)
for k, v in next, m do
    if k % 2 == 0 then
        m[k] = nil
    end
end

that is, deleting a key k still lets you call next(m, k) to get the next key.

Now of course it is properly documented that calling unordered_map::erase invalidates the iterator:

References and iterators to the erased elements are invalidated. Other iterators and references are not invalidated.

My question is: Why does C++ not support advancing an unordered map iterator after erasing it, as Lua for example does?

Is this for simplicity of specification, so that there only needs to be one simple notion of "iterator invalidation", which can be applied here as well?

Edit: Perhaps for consistency with other containers?

Or are there some tangible (for example performance) benefits to not supporting this? Are there concrete examples of these benefits being leveraged in present day C++ stdlib implementations?

---

2nd Edit: I am aware that you can still iterate an unordered map while deleting elements by using the return value of erase as outlined in the docs. I am asking why this clunkier and more error prone interface is preferred over simply allowing to use erased entries for advancing iterators.

---

3rd Edit:

"An iterator is a reference to an element of the container" is oversimplified: There is the notion of a "non-dereferencable" iterator (unordered_map::end is non-dereferencable, for example).

You can test the above code (which just unconditionally advances the iterator) on GCC (11.4.0) and Clang (14.0.0), with different optimization levels, with and without asan and ubsan, and it seems to work as expected. (Edit: It seems to only work sometimes?)

I would be interested to know whether there is a C++ hash table implementation that takes advantage of this / how current implementations take advantage of this - that is, is there a (C++) hash table where ++it for an iterator "invalidated" by erase is not the same as the iterator returned by erase, and what is the benefit of it?

It is still not quite clear to me why C++ would opt to have the standard deem the iterator invalidated rather than non-dereferencable.

It seems most plausible to me that this is indeed about consistency with other containers - for vectors, lists, and (sorted) maps, returning a new iterator is important - rather than about any technical benefit for the hash map implementation.

Answer 1

Check the return value of std::unordered_map::erase. It returns an iterator. In fact it is the iterator pointing to the element after the removed element.

what you should do is:

for (auto it = m.begin(); it != m.end(); )
    if (it.first % 2 == 0)
        it = m.erase(it);
    else
        ++it;

So it does support continuing iteration after an erase, but the way to do it is rather clunky.

C++ iterators are based on a pointer going through an array, an std::vector is just a pointer. The associated notation (operator *() and operator++()) got coopted into other STL containers.

To erase an element based on a pointer in the array you can keep the pointer as is, which now points to the next element. However for iterators in a node based container you need another way of getting the new iterator, so in the STL they return it.

If the iterator was passed by reference and the loop structure remains the same then it would also need to account for the increment at the end of the loop. But that would be different from the pointer case it was based on.

Other languages tend to have more bookkeeping in their iterators, for one to be able to have an integrated end-of-iteration test. Java for example has a remove integrated with the iterator interface, and the iterator is responsible for keeping its own state consistent so the rest of the loop can remain unchanged.

Answer 2

The C++ STL takes the approach of trying to minimize how many implementation details it specifies. Permitting a "semi-invalidated" iterator would require all implementations to keep enough information around to implement operator++. The developers of Lua balance convenient syntax's more heavily than they do avoiding restrictions on implementations. C++ strikes a different balance.

Also remember that C++ is not a garbage collected language. Lots of things that are super-easy with garbage collection behind you become tricky without it.

Answer 3

This is basically what I would expect from your average hash map with closed hashing: Entries aren't truly "deleted", space is not reclaimed; entries are merely marked as deleted, and we have to assume that their contents may now be garbage.

Your assumption is faulty.

std::unordered_map uses closed addressing (not closed hashing). The hash-map is typically an array of buckets, and the bucket typically a linked-list, empty to start with.

Each element is placed in a separately allocated node which is linked in the linked-list. In fact, this node-based implementation detail leaks into the API: check the std::unordered_map::extract function!

When the element is erased from the hash-map, its node is freed.

The technique of using a "deleted" marker is instead used in open hashing.

Why does C++'s unordered_map::erase fully invalidate iterators, not even supporting advancing?

Simply put, because the iterator is just a pointer to the (internal) node of the hash-map, and therefore after erasing the element, since the node is deleted, the iterator points into the nether.

It can't "advance", because that would require reading the next pointer from the freed node.