C ++ and iterator invalidation

Question

So, I went through accelerated C ++ and am somewhat unsure of the invalidity of the C ++ iterator. Perhaps this is a problem that never explains how these iterators are constructed.

Here is one example:

Vector with {1,2,3}

If my iterator is turned on in {2} and I am erasing on {2}, my iterator is invalid. What for? In my head, {3} shifts down, so the memory location, where {2} was such that the iterator still points to a valid element. The only way I could see this as a lie is that iterators were made for each element in front of each element, and each iterator had some kind of field containing the address of the next element in this container.

My other question is related to the statement, for example, “invalidates all other iterators”. Erm, when I loop through my vector container, I use one iterator. Do all these elements in the vector implicitly have their own iterator associated with them, or am I missing something?

Answer 1

In my head, {3} shifts down, so the memory location, where {2} was such that the iterator still points to a valid element.

It could be like that. But its equivalent that the whole vector moves to memory, thereby making all iterators point to now inactive memory cells. C ++ simply gives no guarantees. (See Comments for a discussion.)

Do all these elements in the vector implicitly have their own iterator associated with them, or am I missing something?

You simply have not noticed that you can have other iterators referring to the same vector except your loop variable. For example, the following loop is an idiomatic style that caches an end vector iterator to avoid redundant calls:

 vector<int> vec; // … for (vector<int>::iterator i(vec.begin()), end(vec.end()); i != end; ++i) { if (some_condition) vec.erase(i); // invalidates `i` and `end`. } 

(Do not pay attention to the fact that this copy of the final iterator is not really needed by STL for modern compilers.)

Answer 2

The following C ++ defect report (fixed in C ++ 0x) provides a brief description of the value "invalidate":

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#414

 int A[8] = { 1,3,5,7,9,8,4,2 }; std::vector<int> v(A, A+8); std::vector<int>::iterator i1 = v.begin() + 3; std::vector<int>::iterator i2 = v.begin() + 4; v.erase(i1); 

Which iterators are v.erase (i1) invalid: i1, i2, both or none?

In all existing implementations that I know, the status of i1 and i2 is the same: both of them will be iterators pointing to some elements of the vector (although not the same elements that they did before). You will not get collapsed if you use them. depending on what you mean by "invalidate", you can say that none were invalidated because they still point to something, or you can say that both were invalid because in both cases the elements they point to have been modified from under an iterator.

The specification seems to be "playing safe" with respect to the iterator and invalid link. It says that they are invalidated, although, as you and Matt Austern noted, there is still a vector element at the same address. It has a different meaning.

So, those of us that follow the standard should be programmed as if this iterator cannot be used anymore, even if no implementation can do anything that would actually stop their work, with the possible exception of a debug iterator, which could do extra work to tell us that we are SUVs.

In fact, this defect report refers specifically to the case you are talking about. As far as the C ++ 03 standard actually says, at least in this section, your iterator is not invalid. But this was considered a mistake.

Answer 3

The “in your mind” image is an implementation detail, and it may happen that your iterator is not implemented that way. Perhaps it is so, but maybe it is not.

The ivalidates all other iterators language is their way of saying that they are allowed the freedom to do any of their skeevie hearts for their coders when you perform this operation, including things that require internal changes to iterators, since the only iterator to to whom he has access is the one that you transferred, and the only one that he can correct if necessary.

If you need head behavior for a vector, it's easy to get it. Just use an index instead of a vector instead of an iterator. Then it works the way you think.

Answer 4

The iterator basically wraps the pointer. Some container operations result in redistribution of some or all of the data behind the scenes. In this case, all current pointers / iterators remain pointers to invalid memory locations.

Answer 5

Most likely, your iterator actually points to 3 - but it is not defined.

The general idea is to allow vector distribute new storage and move your data from one storage block to another when / if it considers it appropriate. Thus, when you insert or delete data, the data can completely move to some other part of the memory.

At least that was kind of an intention. It turns out that other rules probably do not allow it to move data when it is deleted - but the iterator is still invalid, perhaps because someone did not quite understand all the consequences of these other rules when it was done.

Answer 6

From SGI http://www.sgi.com/tech/stl/Vector.html

[5] Vector iterators are not valid for memory reallocation. In addition, inserting or deleting an element in the middle of the vector invalidates all iterators pointing to elements following the insertion or deletion point. It follows that you can prevent vector iterators from being invalid if you use reserve () to predefine as much memory as the vector will use, and if all insertions and deletes are at the end of the vector.

So you can erase from end to end

 int i; vector v; for ( i = v.size(), i >=0, i--) { if (v[i]) v.erase(v.begin() + i); } 

OR use the iterator returned from vector erase ()

 std::vector<int> v; for (std::vector<int>::iterator it = v.begin(); it != v.end(); ) it = v.erase(it);