[Cs3] CSIII Question: Map Memory Growth

[Mikhail Nesterenko]

> 
> 
> How does the memory growth for maps (and sets while we're on the subject) compare to sequential containers like lists and vectors? If the memory use is higher, is this cost offset by faster access and update operations?
> 
> 
> 

It looks like SGI (an early reference implementation of STL)
implementation honestly implements a red-black tree is a collection of
nodes in a heap. However, to minimize allocation/deallocation system
calls, it keeps a linked list of free nodes to be used in case there
is a need for additional nodes.

Here is more info:   http://www.drdobbs.com/cpp/stls-red-black-trees/184410531

Thanks,
--
Mikhail