Re: [boost] [intrusive] Intrusive containers library strikes back

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2006-09-18 13:06:00

Kevin Sopp ha escrito:

> On 9/17/06, "JOAQUIN LOPEZ MU?Z" <joaquin_at_[hidden]> wrote:
> >
> > Hello Kevin, I am *very* interested in seeing your work.
> > Is that possible? Are you building on Boost.MultiIndex, or
> > is your material written from scratch?
> >
>
> I knew you'd answer ;)

:)

> It is written from scratch. Basically the code isn't anywhere ready
> to be publically consumed. I still have to figure out some tough things.
> But the gist is this:
> - Derive your type from super_node. // can be done as a member too, but is
> not implemented
> - super_node manages access to a vector of sub_nodes.
> - sub_nodes are linked list nodes/red-black tree nodes, etc.
> - super_node holds these as a vector<void*>, it has no type information
> - sub_nodes are looked up via a minimal perfect hash function (MPHF)

As it happens, I did in the past a little sketch of how a dynamic
multi_index_container (no intrusiveness) could be implemented, and basically
all of the above coincides with my stuff, except one thing: what is this MPHF
thing and what do you use it for?

>
> - minimal perfect hash function is generated in linear time! (BMZ algorithm,
> also found in cmph on sourceforge)
> this is a C++ implementation of the BMZ paper
> - default key type is typeid(index_type), user can provide other key type
> though
>
> Complexity is added because we can create subviews on data, unlike your
> multi_index container the number of sub_nodes per super_node does not need
> to be the same.

Very interesting possibility.

[...]

> I am interested in putting this up on sourceforge as soon as I feel that the
> code has advanced sufficiently.

All of this looks sexy. Looking forward to seeing your stuff soon.

> Kevin

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo