[Cs3] CS3 - Iterator Invalidation and erase() Function on Containers

[Mikhail Nesterenko]

> 
> When using the erase function on a container, say for example a map, does
> the erase function construct a new object without that element that a
> programmer wants erased?

a map implementation is using a red-black tree which is a bunch of
linked nodes. Implementing a red-black tree in an array is wasteful.

So, in case of an erase, the element (a node in the tree) is
deallocated and the tree is possibly re-balanced which results 
in a number of pointers being updated. The number of such pointer
updates is proportional to the logarithm of the number of nodes in the
tree (elements in the map)

> Also the erase function can return an iterator to the next element in the
> container following the element that was just erased right? And if a new
> object is NOT being created, then the iterator that is being returned by
> the erase function essentially points the original objects' next element in
> the container.
> 
> However, if a new object is being created when the erase function is
> called, then that would mean that the iterator returned by the erase
> function points to the newly created objects' particular element.
> 
> By thinking that new objects and new pointers to those new objects are
> being created, then that would mean we would have to be very careful about
> iterator invalidation within loops AND/OR certain c++ constructs right?
> 
> So my question is what is happening underneath the hood? I suppose it would
> very from case to case say lists vs vectors vs maps.

In case of a map, only iterators to the erased element are
invalidated. All other iterators remain valid.

Invalidation affects random access containers: vector and deque since
update operations may result in complete internal buffer
re-allocation.

Thanks,
-- 
Mikhail