Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

C++ Programming

Invalidating iterators after insertion/removal


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?

"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?
On 7 Juni, 09:58, desktop <f@sss.com> wrote:

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

--
Erik Wikstrm

Erik Wikstrm 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 Wikstrm 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 Wikstrm

On Jun 7, 2:07 pm, Erik Wikstrm <eri@student.chalmers.se> wrote:

> On 7 Juni, 12:59, Juha Nieminen <nos@thanks.invalid> wrote:
> > Erik Wikstrm 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.ka@gmail.com
Conseils en informatique oriente objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place Smard, 78210 St.-Cyr-l'cole, France, +33 (0)1 30 23 00 34

Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc