iterators

[Raven Arkadon]

iterators of which containers are "invariant" to what they point to upon insertion/deletion?

so far i found out that:
vector<>::iterator always points to the same entry in the vector.
thus if you have an iterator pointing to vector.begin(); and insert a new element to the beginning of the vector, the iterator will point to the new element
reason: vector is a linear piece of memory (array), and the iterator always points to the same location in that array. thus insertion requires shifting elements to the right.

list:
if you have an iterator pointing to list.begin() and you insert a new element to the beginning, the iterator will still point to the old element
reason: list is a linked list. iterator points to some element in the list, and linked list elements' location in memory doesnt change as long as it exists (thus the location of the data is invariant upon indel (insertion/deletion)

what about map and set?
i know they use red/black tree structures for organizing their data.
but if i have an iterator to some element and keep indeling elements, does this iterator still point to the correct entry?

of course im not talking about erasing some iterator and useing it after that. of course that causes undefined behaviour.

[Daved]

Actually, in all cases, if the iterator has not been invalidated, then it will point to the old element. In the case of the vector, insertion invalidates all iterators, so you cannot count on the iterator pointing to any location. What you should do is focus on which container methods invalidate iterators and which do not. If the method has not invalidated the iterator, then it is pointing at the old element.

[Daved]

My above response was not fully correct. According to the standard, calling insert on a vector only invalidates iterators if the vector requires a reallocation (the new size is greater than the old capacity). So if you reserve enough space prior to calling insert, your iterator will not be invalidated. I did not find any indication of whether the iterator must point to the original element or the element that exists at that location after the insert.

It makes sense to allow the implementers to leave the iterator pointing to the same location in the underlying array, since vector iterators are often implemented as a pointer or something similar. This would cause the behavior you saw, so your reasoning was correct.

So in response to your actual question about map and set, I believe that it does continue to point to the original entry, but I cannot find a guarantee for that in the standard.

Sorry for the confusion.

[Prelude]

>i know they use red/black tree structures for organizing their data.
A red-black tree is one possible implementation, but it doesn't have to be done that way, and assuming so could cause you problems.

>does this iterator still point to the correct entry?
Yes.

>but I cannot find a guarantee for that in the standard.
Section 23.1.2, Associative Containers, paragraph 8:

The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

[Daved]

> Section 23.1.2, Associative Containers, paragraph 8
I actually saw that, however I don't think the definition of "valid" means that the iterator must point to the same element. There is a similar guarantee of "validity" for vectors, but the iterator does not point at the same element after the insert, it points at the same location.

I am guessing/hoping this will be clarified in the next standard if it hasn't been already.

[Raven Arkadon]

well i did a test run with map of inserting a random number of entries, then randomly pick an iterator to some entry, and keep erasing and inserting new elements.
after that the randomly picked iterator still pointed to the same element.
(of course i made sure that iterator wasent erased)
i guess the reason is, that a tree structure is used, so each node in the tree has its own memory location (like the linked list), thus erasing elements doesnt cause other iterators to point to something else.

[Prelude]

>I don't think the definition of "valid" means that the iterator must point to the same element
Correct, the validity of an iterator, taking into account the vague description in the standard, basically means that the iterator refers to an element in a valid range. But in this case, I think it's safe to assume that "valid" also means that the iterator refers to the same place that it referred to before the operation.

Granted, it's a non-portable assumption, but I have trouble imagining a situation where a conforming implementation of the associative containers would fail to do the expected thing.