C++ Programming :: Invalidating iterators after insertion/removal


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