C++11: Is it safe to remove individual elements from std::unordered_map while iterating?

Question

Consider the canonical algorithm for removing an element from an associative container while iterating:

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

I've been applying this algorithm without a second thought when using the C++11 std::unordered_map container. However, after browsing the documentation for std::unordered_map::erase on cppreference.com, I became a little concerned after reading the following note:

The order of the elements that are not erased is preserved (this makes it possible to erase individual elements while iterating through the container) (since C++14)

Based on this statement, I'm assuming there was language added to the C++14 standard to ensure library implementers guarantee ordering after a call to std::unordered_map::erase. For example, maybe such a requirement constrains the implementation from not rehashing the entire container after an element is removed, but rather only allows it to remove the element from its corresponding bucket?

Without such a guarantee in C++11, and if I desire my code to be portable, do I have to worry that some elements will be visited multiple times or not at all if I remove an element from an std::unordered_map during iteration?

Refer to [this answer](https://stackoverflow.com/a/6442829/241631) which cites the C++11 rules. For erasure from unordered associative containers, only iterators to the erased elements are invalidated. So your code is valid. — Praetorian, Jul 30 '14 at 21:32
@Praetorian: Thanks for the clarification. I understand that the iterator is still valid after the erasure, but my concern is that, in light of the C++14 guarantee above, will continuing the iteration until the end yield the same sequence of elements as if I did not remove the element? If so, do you know why the committee felt that adding the above clarification to C++14 was necessary? — f1191994, Jul 30 '14 at 21:45
Sorry, I misunderstood your question then. [Here's](http://wg21.cmeerw.net/lwg/issue2356) the issue that brought about the wording change. I think the answer to your question is - *not guaranteed by the standard pre-C++14, guaranteed in practice*. The linked report states as much - *not that any actual implementation does that, anyway*. I'll re-open the question, maybe someone will have a better answer for you. — Praetorian, Jul 30 '14 at 22:02
@Praetorian: You have a good answer to a good question. Please put it where I can up vote it. :-) — Howard Hinnant, Jul 31 '14 at 00:48
@Howard Thank you, but I was hoping someone like you, who has intimate knowledge of at least one std library implementation, would post an answer. Anyway, there's already an answer now that states what I did in my comment. — Praetorian, Jul 31 '14 at 02:48
ah, that's right: since C++11, `map::erase` returns an iterator. I had the pattern from Effective STL ingrained in memory: `if( ) myMap.erase(it++); else ++it;` but yours is nicer. — TemplateRex, Jul 31 '14 at 07:06
@Praetorian: I agree with Howard and Caladain: your comment is the answer; please add it as such. The link to Library Working Group issue [2356](http://wg21.cmeerw.net/lwg/issue2356) is what I was looking for. Thanks! — f1191994, Jul 31 '14 at 12:08

score 2 · Accepted Answer · edited Jun 20 '20 at 09:12

2

Edit: The dangers of NoScript. I had noscript running, which displayed the C11 and C14 tabs as one box. Praetorian's answer is correct about it being guaranteed in practice, and formalized in c14.

** Below is wrong due to noscript.

At the bottom of cplusplus it states that

Only the iterators and references to the elements removed are invalidated.

The rest are unaffected.

The relative order of iteration of the elements not removed by the operation is preserved.

http://www.cplusplus.com/reference/unordered_map/unordered_map/erase/

At the top of the page, it states it's for C++11...so unless they updated it for C++14, i think it applies to C++11 as well. Praetorian should put an answer and you should check his for the answer, because even if it's not guaranteed in the standard for C++11 (C++14 being the patch for these sort of things), it's guaranteed in practice.

I couldn't find the STL standard, I seem to have misplaced it, or I'd go see if there was a text guaranteed I could point to. :-/

edited Jun 20 '20 at 09:12

Community

1
1

answered Jul 31 '14 at 00:59

Caladain

4,801
22
24

Thanks for the additional link, but when I view that page, the statement, _"The relative order of iteration of the elements not removed by the operation is preserved,"_ is listed only under the C++14 tab. Please correct me if I misread it. Otherwise, I'd appreciate an edit because I think citing the [cplusplus.com link](http://www.cplusplus.com/reference/unordered_map/unordered_map/erase/) is useful. – f1191994 Jul 31 '14 at 12:00
I had no-script on. It displayed both tabs as one block of text. Sorry :-( – Caladain Jul 31 '14 at 14:56
I accepted this answer because it refers to Praetorian's comment above, which is what I was looking for. – f1191994 Aug 06 '14 at 14:06

C++11: Is it safe to remove individual elements from std::unordered_map while iterating?

1 Answers1

Linked