== Quote from Andrei Alexandrescu (seewebsiteforem...@erdani.org)'s article
> Joaquin M Lopez Munoz wrote:
> > I'd like to state that Boost.MultiIndex internal implementation is *not*
> > based on iterators, so the whole discussion iterators vs. ranges does
> > not impact Boost.MultiIndex memory usage in any manner.
> >
> > Joaquín M López Muñoz
> > Telefónica, Investigación y Desarrollo
>
> Welcome, Joaquín! Good to see you here. Could you please provide a bit
> more detail? Does Boost.MultiIndex use pointers? Thanks!
The implementation is based on nodes interlinked with pointers,
just as say your favorite std::set implementation. I'll elaborate
a bit on this: A std::set is usually implemented as an rb-tree
where nodes look like
struct node
{
// header
color c;
pointer parent,left,right;
// payload
value_type value;
};
Well, A multi_index_container's node is basically a "multinode"
with as many headers as indices as well as the payload.
For instance, a multi_index_container with two so-called
ordered indices uses an internal node that looks like
struct node
{
// header index #0
color c0;
pointer parent0,left0,right0;
// header index #1
color c1;
pointer parent1,left1,right2;
// payload
value_type value;
};
(The reality is more complicated, these nodes are generated
through some metaprogramming etc. but you get the idea) There
are no iterators involved in the implementation of a
multi_index_container.
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
PS: I'd be delighted if some bold sould took the challenge of
porting Boost.MultiIndex to D. My collected reports show
that the lib is quite popular in C++, so having it in D could
be welcome. I can't program in D, but if someone decides to
go down this path I'd love to assist with discussions on
the design and internals.
J
