<p>The documentation on C++'s <a href="https://en.cppreference.com/w/cpp/container/unordered_map/erase" rel="nofollow noreferrer"><code>unordered_map::erase</code></a> states:</p>
<blockquote>
<p>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.)</p>
</blockquote>
<p>This is basically what I would expect from your average hash map with closed hashing: Entries aren't truly &quot;deleted&quot;, space is not reclaimed; entries are merely marked as deleted, and we have to assume that their contents may now be garbage.</p>
<p>Given this, I would have assumed the following to be supported:</p>
<pre class="lang-cpp prettyprint-override"><code>std::unordered_map&lt;int, std::string&gt; m = {
    {-1, &quot;one&quot;}, {-2, &quot;two&quot;}, {-3, &quot;three&quot;},
    {-4, &quot;four&quot;}, {-5, &quot;five&quot;}, {-6, &quot;six&quot;}
};
for (auto it = m.begin(); it != m.end(); ++it)
    if (it.first % 2 == 0)
        m.erase(it);
</code></pre>
<p>but it isn't. Contrast this with Lua, where the following works just fine:</p>
<pre class="lang-lua prettyprint-override"><code>-- negative keys to ensure that these don't end up in the &quot;list&quot; part internally
local m = {
    [-1] = &quot;one&quot;, [-2] = &quot;two&quot;, [-3] = &quot;three&quot;,
    [-4] = &quot;four&quot;, [-5] = &quot;five&quot;, [-6] = &quot;six&quot;,
}
-- 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
</code></pre>
<p>that is, deleting a key <code>k</code> still lets you call <code>next(m, k)</code> to get the next key.</p>
<p>Now of course it is properly documented that calling <code>unordered_map::erase</code> invalidates the iterator:</p>
<blockquote>
<p>References and iterators to the erased elements are invalidated. Other iterators and references are not invalidated.</p>
</blockquote>
<p>My question is: Why does C++ not support advancing an unordered map iterator after erasing it, as Lua for example does?</p>
<p>Is this for simplicity of specification, so that there only needs to be one simple notion of &quot;iterator invalidation&quot;, which can be applied here as well?</p>
<p>Edit: Perhaps for consistency with other containers?</p>
<p>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?</p>
<hr />
<p>2nd Edit: I am aware that you can still iterate an unordered map while deleting elements by using the return value of <code>erase</code> as outlined in the docs. I am asking <em>why</em> this clunkier and more error prone interface is preferred over simply allowing to use erased entries for advancing iterators.</p>
<hr />
<p>3rd Edit:</p>
<p>&quot;An iterator is a reference to an element of the container&quot; is oversimplified: There is the notion of a &quot;non-dereferencable&quot; iterator (<code>unordered_map::end</code> is non-dereferencable, for example).</p>
<p>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?)</p>
<p>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 <code>++it</code> for an iterator &quot;invalidated&quot; by <code>erase</code> is not the same as the iterator returned by <code>erase</code>, and what is the benefit of it?</p>
<p>It is still not quite clear to me why C++ would opt to have the standard deem the iterator <em>invalidated</em> rather than <em>non-dereferencable</em>.</p>
<p>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.</p>

<standard-library><c++><iterators>
Why does C++'s unordered_map::erase fully invalidate iterators, not even supporting advancing?
CC BY-SA 4.0
2024-03-06T14:05:29.517Z
@EldritchConundrum from the perspective of the user, the entries are indistinguishable from deleted entries, except that the keys can still be used for iteration. If you do `for k, v in next, m do print(k, v) end` afterwards, it will print only the odd keys & associated values.
Luatic
CC BY-SA 4.0
2024-03-07T02:27:43.277Z
An iterator is a reference to an element of the container.  When an element is erased, any reference to it is "dangling" and trying to do anything with it is nonsensical.  While in theory you could have an interator-like thing that can either refer to an element of the container, or a special marker for a removed element, this would add a bunch of extra overhead to the iterator and container class.
Chris Dodd
<p>The C++ STL takes the approach of trying to minimize how many implementation details it specifies.  Permitting a &quot;semi-invalidated&quot; 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.</p>
<p>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.</p>

CC BY-SA 4.0
2024-03-13T03:58:02.273Z
2024-03-13T03:58:02.273Z
Cort Ammon
<blockquote>
<p>This is basically what I would expect from your average hash map with closed hashing: Entries aren't truly &quot;deleted&quot;, space is not reclaimed; entries are merely marked as deleted, and we have to assume that their contents may now be garbage.</p>
</blockquote>
<p>Your assumption is faulty.</p>
<p><code>std::unordered_map</code> uses <em>closed addressing</em> (not closed hashing). The hash-map is typically an array of buckets, and the bucket typically a linked-list, empty to start with.</p>
<p>Each element is placed in a <em>separately allocated node</em> which is linked in the linked-list. In fact, this node-based implementation detail leaks into the API: check the <a href="https://en.cppreference.com/w/cpp/container/unordered_map/extract" rel="nofollow noreferrer"><code>std::unordered_map::extract</code></a> function!</p>
<p>When the element is erased from the hash-map, its node is <em>freed</em>.</p>
<p>The technique of using a &quot;deleted&quot; marker is instead used in <em>open</em> hashing.</p>
<blockquote>
<p>Why does C++'s unordered_map::erase fully invalidate iterators, not even supporting advancing?</p>
</blockquote>
<p>Simply put, because the iterator is <em>just</em> 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.</p>
<p>It can't &quot;advance&quot;, because that would require reading the <code>next</code> pointer from the freed node.</p>

CC BY-SA 4.0
2024-03-13T11:42:58.713Z
2024-03-13T12:49:44.970Z
2024-03-13T12:49:44.970Z
Matthieu M.
CC BY-SA 4.0
2024-03-13T12:28:59.797Z
Closed hashing does not use explicit linked lists. Buckets are implicitly determined by probing (see [Wikipedia](https://en.wikipedia.org/wiki/Open_addressing)). Closed hashing can very well use a "deleted" marker ("another technique for removal is simply to mark the slot as deleted"). Might you be confusing addressing and hashing here? The terminology is reversed (open addressing is closed hashing).
Luatic
CC BY-SA 4.0
2024-03-13T12:48:55.947Z
@Luatic: I may be indeed. I was thinking of addressing. Then your confusion is different. `std::unordered_map` uses closed addressing.
Matthieu M.
CC BY-SA 4.0
2024-03-13T13:51:36.670Z
Ah thanks, I see! I'm used to hash maps using closed hashing (for example Lua uses closed hashing, to my knowledge). Do you know why C++ prefers open hashing?
Luatic
CC BY-SA 4.0
2024-03-13T13:56:50.633Z
@Luatic: The goal of the standard committee was to make `std::unordered_map` as close to possible in terms of interface and guarantees as `std::map`, so that people could upgrade as easily as possible. `std::map` has the "memory stability" guarantee: an element, once inserted, will have the same address no matter what operation is performed on the map until the element is erased from the map. Not having this guarantee would have been a footgun on the upgrade path, and therefore it required a node-based design for `std::unordered_map`.
Matthieu M.
<p>Check the return value of <code>std::unordered_map::erase</code>. It returns an iterator. In fact it is the iterator pointing to the element after the removed element.</p>
<p>what you should do is:</p>
<pre><code>for (auto it = m.begin(); it != m.end(); )
    if (it.first % 2 == 0)
        it = m.erase(it);
    else
        ++it;
</code></pre>
<p>So it does support continuing iteration after an erase, but the way to do it is rather clunky.</p>
<p>C++ iterators are based on a pointer going through an array,  an std::vector is just a pointer. The associated notation (<code>operator *()</code> and <code>operator++()</code>) got coopted into other STL containers.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2024-03-06T13:37:23.177Z
2024-03-06T14:18:50.530Z
2024-03-06T14:18:50.530Z
ratchet freak
CC BY-SA 4.0
2024-03-06T13:51:10.760Z
Yes, I am aware of this (this is the example from the docs), but I wonder why it is designed to be like this. Why can't `++it` "just work" for a semi-invalidated iterator? When and why does `erase` return something else? Or in other words: What is the benefit of having this be clunky (and easy to mess up)?
Luatic
CC BY-SA 4.0
2024-03-06T15:57:34.900Z
So you'd say it is historically that way for consistency with `std::vector`, where `erase` does something different and the resulting iterator should not be advanced to get the next element?
Luatic
CC BY-SA 4.0
2024-03-06T21:07:28.373Z
@Luatic Another way to think of it is like linked lists. After you remove a node (which frees its memory), you can't use its `node.next` pointer. So the removal operation has to return something you can use `.next` on to go to the next node.
Barmar
# Why does C++'s unordered_map::erase fully invalidate iterators, not even supporting advancing?
Posted by: username_0 on 2024-03-06
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 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.
**Tags:** standard-library c++ iterators
> **Comments:**
> **username_0**: @EldritchConundrum from the perspective of the user, the entries are indistinguishable from deleted entries, except that the keys can still be used for iteration. If you do `for k, v in next, m do print(k, v) end` afterwards, it will print only the odd keys & associated values.  
> **username_1**: An iterator is a reference to an element of the container.  When an element is erased, any reference to it is "dangling" and trying to do anything with it is nonsensical.  While in theory you could have an interator-like thing that can either refer to an element of the container, or a special marker for a removed element, this would add a bunch of extra overhead to the iterator and container class.  
---
## 3 answers
### Answer by username_4 on 2024-03-06. Score: 5 | Accepted answer
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.
> **Comments:**
> **username_0** (2024-03-06): Yes, I am aware of this (this is the example from the docs), but I wonder why it is designed to be like this. Why can't `++it` "just work" for a semi-invalidated iterator? When and why does `erase` return something else? Or in other words: What is the benefit of having this be clunky (and easy to mess up)?  
> **username_0** (2024-03-06): So you'd say it is historically that way for consistency with `std::vector`, where `erase` does something different and the resulting iterator should not be advanced to get the next element?  
> **username_5** (2024-03-06): @Luatic Another way to think of it is like linked lists. After you remove a node (which frees its memory), you can't use its `node.next` pointer. So the removal operation has to return something you can use `.next` on to go to the next node.  
---
### Answer by username_2 on 2024-03-13. Score: 1
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 by username_3 on 2024-03-13. Score: 1
> 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`](https://en.cppreference.com/w/cpp/container/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.
> **Comments:**
> **username_0** (2024-03-13): Closed hashing does not use explicit linked lists. Buckets are implicitly determined by probing (see [Wikipedia](https://en.wikipedia.org/wiki/Open_addressing)). Closed hashing can very well use a "deleted" marker ("another technique for removal is simply to mark the slot as deleted"). Might you be confusing addressing and hashing here? The terminology is reversed (open addressing is closed hashing).  
> **username_3** (2024-03-13): @Luatic: I may be indeed. I was thinking of addressing. Then your confusion is different. `std::unordered_map` uses closed addressing.  
> **username_0** (2024-03-13): Ah thanks, I see! I'm used to hash maps using closed hashing (for example Lua uses closed hashing, to my knowledge). Do you know why C++ prefers open hashing?  
> **username_3** (2024-03-13): @Luatic: The goal of the standard committee was to make `std::unordered_map` as close to possible in terms of interface and guarantees as `std::map`, so that people could upgrade as easily as possible. `std::map` has the "memory stability" guarantee: an element, once inserted, will have the same address no matter what operation is performed on the map until the element is erased from the map. Not having this guarantee would have been a footgun on the upgrade path, and therefore it required a node-based design for `std::unordered_map`.  
---
