Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 757
f1191994 Avatar asked Jul 30 '14 21:07

f1191994


People also ask

Can you loop through unordered_map C++?

Iterating over a map by using STL Iterator: By creating an iterator of std::map and initializing it to the starting of map and visiting upto the end of map we can successfully iterate over all the elements of map.

How do you delete a map while iterating?

Remove entries from a map while iterating it in C++ Since calling the erase() function invalidates the iterator, we can use the return value of erase() to set the iterator to the next element in the sequence.

Does unordered_map allow duplicates?

Because unordered_map containers do not allow for duplicate keys, this means that the function actually returns 1 if an element with that key exists in the container, and zero otherwise.

Which is more efficient map or unordered_map?

Insertion of spread keys in std::map tends to outperform std::unordered_map when map size is under 10000 elements. Insertion of dense keys in std::map doesn't present performance difference with std::unordered_map under 1000 elements. In all other situations std::unordered_map tends to perform faster.


1 Answers

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. :-/

like image 134
Caladain Avatar answered Oct 20 '22 09:10

Caladain