Invalidating iterators after insertion/removal

[barcaroller]

If I insert/remove an element in a set, will an iterator to this set
automatically become invalid? Does the position of the iterator before the
insertion/removal matter?

How are vectors and lists affected?

 

[Andre Kostur]

If I insert/remove an element in a set, will an iterator to this set
automatically become invalid? Does the position of the iterator
before the insertion/removal matter?

Insertion doesn't invalidate iterators into a set, deletion will invalidate
iterators (and pointers and references) to that element only.

How are vectors and lists affected?

Lists have the same rules as set. For vectors, insertion may invalidate
_all_ iterators into the vector if the insertion requires a reallocation.
(Hadn't thought about it, but it would invalidate all iterators at the
point of insertion and beyond in all cases. Then again, vectors are most
frequently added to at the end of the container, so there's normally
nothing to invalidate.) Deletion from a vector invalidates that iterator
and all iterators past it.

 

[desktop]

Insertion doesn't invalidate iterators into a set, deletion will invalidate
iterators (and pointers and references) to that element only.


Lists have the same rules as set. For vectors, insertion may invalidate
_all_ iterators into the vector if the insertion requires a reallocation.
(Hadn't thought about it, but it would invalidate all iterators at the
point of insertion and beyond in all cases. Then again, vectors are most
frequently added to at the end of the container, so there's normally
nothing to invalidate.) Deletion from a vector invalidates that iterator
and all iterators past it.

How is a vector implemented? I know that set and map are just
abstractions of a red-black tree, but what about vectors?

 

[=?iso-8859-1?q?Erik_Wikstr=F6m?=]

How is a vector implemented? I know that set and map are just
abstractions of a red-black tree, but what about vectors?

Since all elements must be stored in contiguous memory it is usually
implemented with an array.

 

[Juha Nieminen]

Since all elements must be stored in contiguous memory it is usually
implemented with an array.

Usually? You mean there are other ways?

 

[=?iso-8859-1?q?Erik_Wikstr=F6m?=]

Usually? You mean there are other ways?

Well, it's implementation dependent and there might be some
implementer that does something else (perhaps using malloc to reserve
a piece of memory and then use placement new or something). The point
is that it is not defined in the standard so it can be done however
you wish as long as it's compliant, however an array is probably the
easiest and best way to do it.

 

[James Kanze]

Usually? You mean there are other ways?

[/QUOTE]

Well, it's implementation dependent and there might be some
implementer that does something else (perhaps using malloc to reserve
a piece of memory and then use placement new or something). The point
is that it is not defined in the standard so it can be done however
you wish as long as it's compliant, however an array is probably the
easiest and best way to do it.

The standard requires that the memory be contiguous, i.e. that
&vect+1 == &vect[i+1], for all valid i. Which pretty much
limits the choices in the implementation. The standard also has
pretty strict requirements concerning when constructors of
vector elements are called, and when iterators, pointers and
references are invalidated, which ultimately more or less
require that allocation and initialization be separated, i.e.
that placement new be used for construction. The standard also
requires that all dynamic memory used be allocated by the global
operator new() function (at least when the default allocator is
used). Given all this, an implementation really doesn't have
much freedom. A typical implementation will use three pointers:
one to the start, one to the end of the initialized values, and
one to the end of the raw memory---it may replace the latter two
with integral values, and it may add extra data for error
checking (i.e. a list of active iterators), but that's about it.

Note that vector<T> cannot be implemented using new T[]. It
must separate allocation and initialization.