Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Does inserting/erasing an element from a std::map modify the iteration sequence?

Say I have the following code:

typedef std::map< int, std::string >::iterator Iterator;
Iterator iter = myMap.begin();

while (iter != myMap.end())
{
    Iterator current = iter;
    ++iter;

    maybeDeleteElement( current ) // may call erase.
}

Given that std::map is implemented as a red-black tree, is it guaranteed that every element in the map will be visited exactly once? Or will modifying the map cause the tree to rebalance, and thus the iteration sequence to change?

Note: This is not a question about whether or not any iterators will be invalidated. But an iterator remaining valid does not necessarily mean that incrementing it will give you the same next element that it did before.

like image 684
Dominic Gurto Avatar asked May 30 '13 02:05

Dominic Gurto


People also ask

Does map insert invalidate iterator?

Set, map, multiset, multimapOnly iterators and references to the erased elements are invalidated.

How do you delete a map while iterating?

While iterating, check for the key at that iteration to be equal to the key specified. The entry key of the Map can be obtained with the help of entry. getKey() method. If the key matches, remove the entry of that iteration from the HashMap using remove() method.

Does map return an iterator?

map() loops over the items of an input iterable (or iterables) and returns an iterator that results from applying a transformation function to every item in the original input iterable.

What does std::map insert return?

map insert() in C++ STL Return Value: The function returns a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to the element with an equivalent key in the map.


2 Answers

In a std::map the elements will be visited in order.

If you store an iterator that refers to an element that is not deleted, and hence not invalidated, the iterator will still refer to that same element. (If it was the end iterator, it remains the end iterator, as it is not invalidated).

When you advance that iterator, it will advance to the next element in order after the element you refer to.

For your particular example, yes, every element will be visited exactly once, because all deletion of elements was elements that are before the current iterator state of your loop.

If you insert elements ahead of whatever iterator you are using to iterate, then you'll eventually reach them as you iterate forward with your iterator. If you delete elements ahead of whatever iterator you are using to iterate, then they are no longer part of the future elements you'll reach if you iterate with that iterator.

If you insert or delete elements that are before the current location of the iterator, unless you start calling -- or similar functions, your current iteration will continue without noticing that they went away.

This is because ++ on a valid iterator in an ordered container is guaranteed to return the next element in the order, and operations on other iterators that do not invalidate an iterator don't change that iterator's invariants (like what element they refer to).

like image 181
Yakk - Adam Nevraumont Avatar answered Sep 22 '22 17:09

Yakk - Adam Nevraumont


Yes, inserting/erasing can modify the iteration sequence. It does not happen in your example, as you erase iterators you've already passed by, but if you erase/insert elements that are positioned ahead of your current iterator, then it will modify the rest of the sequence.

Here is a short code which displays such behavior:

int main (){
    map<int,int> mapa;
    for(int i = 0; i < 5; ++i) mapa[i] = i;
    bool add = false;
    for(auto it = mapa.begin(); it != mapa.end(); ++it){
        int x = it->second;
        printf("%d\n", x);
        if(add) mapa.erase(x+1);
        add = !add;
    }
    return 0;
}

The example above will print 0 1 3 4 (instead of 0 1 2 3 4). Additionally, if you erase the current iterator, its reference to the next element will be invalidated and your program will crash at the next iteration.

Alternatively, you can also test the insertion, by substituting the if(add) above with:

if(add) mapa[x+5] = x+5;
else mapa[x-20] = x-20;

The example will print the extra elements {6, 8, 11, 16}, and not print the negative ones, since those are being inserted in a position prior to your current one.

like image 36
i Code 4 Food Avatar answered Sep 20 '22 17:09

i Code 4 Food