Re: [boost] [MultiIndex] Memory consumption of ordered indices

Subject: Re: [boost] [MultiIndex] Memory consumption of ordered indices
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2015-02-20 09:01:36

Olaf van der Spek <ml <at> vdspek.org> writes:

> 
> Hi,
> 
> What's the memory consumption of ordered indices? Is it implemented as
> a linked list, so two pointers per element?

The overhead (on most platforms) is three pointers per node (and index):

http://stackoverflow.com/a/4208349/213114

Color is usually embedded into one of the pointers:

http://bannalia.blogspot.com/2008/11/optimizing-red-black-tree-color-bits.html

> In that case for a write-only data structure an external ptr vector
> would make more sense wouldn't it?

What's a "write-only" structure supposed to be useful for? Anyway, s
sorted vector is definitely better in terms of memory consumption than
a single-index multi_index_container.

Joaquin M López Muñoz
Telefónica