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

Question

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.

possible duplicate of [Iterator invalidation rules](http://stackoverflow.com/questions/6438086/iterator-invalidation-rules) — Anthony, May 30 '13 at 02:53
After the edit, this is no longer a duplicate of the question suggested above. — jogojapan, May 30 '13 at 03:11
Your example, and the question in your title, are only slighly related. Are you asking the question in your title, or are you asking about your example? — Yakk - Adam Nevraumont, May 30 '13 at 03:33
An iterator into a typical red-black-tree `std::map` is essentially a pointer to the node containing a certain element, and not something like "the node left then right of the root". So an iterator which is not invalidated continues pointing at the same element when the tree rebalances. I'm having trouble finding the Standard quotes to prove all this is guaranteed, though. — aschepler, May 30 '13 at 03:51

score 5 · Accepted Answer · answered May 30 '13 at 03:39

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).

i Code 4 Food · Answer 2 · 2013-05-30T03:33:02.750

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.

Your example is different than the OP's example. The OP's example had the iterator advanced before the element was possibly deleted. You had an element deleted before the iterator was advanced. — Yakk - Adam Nevraumont, May 30 '13 at 03:31
True, but the question refers to inserting/erasing elements, not just the example. In the OP's code it will run just fine because past elements do not affect the order of future elements, just like my inserting example demonstrates. — i Code 4 Food, May 30 '13 at 03:34
@Yakk I was specifically talking about advancing the iterator before erasing, but it's still useful to have this caveat mentioned here. — Dominic Gurto, May 30 '13 at 04:31

score 1 · Answer 3 · edited May 23 '17 at 11:51

1

Erasing an element from a map does not invalidate iterators, so I would expect it to continue to iterate properly.

See https://stackoverflow.com/a/6438087/5987

edited May 23 '17 at 11:51

Community

1
1

answered May 30 '13 at 02:49

Mark Ransom

299,747
42
398
622

It really depends on how the std::map iterator is implemented: whether it uses the structure of the tree, or whether it uses an ordering of the keys (which it seems to do). – Dominic Gurto May 30 '13 at 03:03
@DominicGurto, no it does not depend on the implementation - if the standard guarantees it, the implementation has no choice but to conform. – Mark Ransom May 30 '13 at 03:07
And if the standard doesn't specify, then the implementation can do whatever it wants... – Dominic Gurto May 30 '13 at 03:09
@DominicGurto, in case it wasn't clear, that was my point - in this case the standard *does* specify. – Mark Ransom May 30 '13 at 03:13

score 0 · Answer 4 · answered May 30 '13 at 03:21

0

Yes, the iteration sequence changes. This is due to §23.2.4.1/10 and /11:

(p10) The fundamental property of iterators of associative containers is that they iterate through the containers in the non-descending order of keys where non-descending is defined by the comparison that was used to construct them. For any two dereferenceable iterators i and j such that distance from i to j is positive,
value_comp(*j, *i) == false
(p11) For associative containers with unique keys the stronger condition holds,
value_comp(*i, *j) != false.

If, after an insert, the new element were added at the beginning of the iteration sequence regardless of the ordering of elements (so as to not to modify the sequence ahead of any existing iterator position), the above requirement would be violated.

answered May 30 '13 at 03:21

jogojapan

68,383
11
101
131

I think that what you mean when you say *"the iteration sequence changes"* is completely different from what the OP is thinking of when he is asking if the iteration sequence changes. And so, your answer will be confusing, and will seem to be contradictory. – Benjamin Lindley May 30 '13 at 03:39
@BenjaminLindley What the above means is that when you advance an iterator, you'll get the next element _in order_ (as defined by `value_comp`). So if you make an insert and _then_ advance the iterator, the element you'll get may be different than if there hadn't been an insert. Isn't that what the OP wants to know? Sorry if I misunderstood. – jogojapan May 30 '13 at 03:42
Read the OP's paragraph directly following his code. Note that there are 2 propositions, which the OP considers to be in opposition. The first proposition seems pretty clear. *"is it guaranteed that every element in the map will be visited exactly once?"* -- And the answer is clearly yes. The second proposition, *"Or will modifying the map cause ... the iteration sequence to change?"* -- It's unclear what the OP means by this, but if it is in opposition to the first proposition, then it must be false. I'm not saying your answer is wrong, but I think the wording is confusing for that reason. – Benjamin Lindley May 30 '13 at 03:53

score 0 · Answer 5 · answered May 30 '13 at 03:46

In spite of your note, for the erase case this question is exactly about iterator invalidation, because if no iterator is invalidated, the order necessarily remains the same. This is because map is a sorted container, so no matter what internal representation changes may happen, the iteration order has to remain exactly the same.

To address specifically your example, it will traverse each element exactly once, because you save off the iterator to check and increment your traversal iterator.

In the case of insertion, if you insert before the current point of iteration that element won't be visited. Inserting after the current iterator will result in the new item being traversed.

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

5 Answers5