[Exceptional C++ Style] Item 21: Containers in Memory, Part 2: How Big Is It Really?

[Kevlin Henney]

In message <009901c4f96e$eede95a0$0a02a8c0 at bpxp>, Balog Pal 
<pasa at lib.hu> writes
>
>2. How much memory do the various standard containers use to store the 
>same number of elements of the same type T?
>
>First we see a recap on Knuth Vol1 material about data structures and 
>the theory.
>
>- vector<T> uses a single block of continuous memory and nothing else.
>- list<T> is a double-linked list of individual elements, so it stores 
>2 pointers beside each element.
>- deque<T> is like a list of vectors -- elements live on 'pages' 
>(supposedly) several at a time, and those pages are linked.  The amount 
>of overhead will depend on the item count for a page, and can be as 
>small as 1/32 bit per element.

Actually, a deque is more like a vector of equal-sized arrays than a 
list of vectors. It is an important assumption for the implementation 
and interface of a deque that the pages are the same size.

>-set/multiset<T> is represented as a binary tree with a must of 2 
>pointers/item, but most implementations use also a third "up" pointer 
>for convenience, so we wan expect that 3 poiter/item overhead.
>-map/multimap<T> is similar to set/multiset just its items are not T 
>but pair<key, T>.

I pretty much thought that to meet all of the functional and operational 
requirements on them, the associative containers required 3 links: one 
up, two down. Having 2 down links is not enough to make it work 
according to contract.

Kevlin
-- 
____________________________________________________________

   Kevlin Henney                   phone:  +44 117 942 2990
   mailto:kevlin at curbralan.com     mobile: +44 7801 073 508
   http://www.curbralan.com        fax:    +44 870 052 2289
   Curbralan: Consultancy + Training + Development + Review
____________________________________________________________