Invalidating iterators after insertion/removal - c++

"barcaroller" <barcaroller@music.net> wrote in
news:f47ddd$jch$1@aioe.org:

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

Andre Kostur wrote:
> "barcaroller" <barcaroller@music.net> wrote in
> news:f47ddd$jch$1@aioe.org:
>
>> 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.

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

On 7 Juni, 09:58, desktop <f...@sss.com> wrote:
> Andre Kostur wrote:
> > "barcaroller" <barcarol...@music.net> wrote in
> >news:f47ddd$jch$1@aioe.org:
>
> >> 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.
>
> 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.

--
Erik Wikström

Erik Wikström wrote:
> Since all elements must be stored in contiguous memory it is usually
> implemented with an array.

Usually? You mean there are other ways?

On 7 Juni, 12:59, Juha Nieminen <nos...@thanks.invalid> wrote:
> Erik Wikström wrote:
> > Since all elements must be stored in contiguous memory it is usually
> > implemented with an array.
>
> 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.

--
Erik Wikström

On Jun 7, 2:07 pm, Erik Wikström <eri...@student.chalmers.se> wrote:
> On 7 Juni, 12:59, Juha Nieminen <nos...@thanks.invalid> wrote:

> > Erik Wikström wrote:
> > > Since all elements must be stored in contiguous memory it is usually
> > > implemented with an array.

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

The standard requires that the memory be contiguous, i.e. that
&vect[i]+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.

--
James Kanze (GABI Software) email:james.kanze@
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34