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

From: Kevin Sopp (baraclese_at_[hidden])
Date: 2006-09-17 18:50:42

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)
- 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. For
example
one can have a sequenced<> index with a unary predicate to test the value to
be inserted for
some condition.
- I have to manage the MPHFs for all used index combinations.
That means super_node needs a pointer to the index_combination it belongs
to.

sequenced_index derives from a base class with some pure virtual functions
that provide the bare necessities
for a container. Mainly insert(super_node*) and erase(super_node*).
Then insertion becomes:
dynamic_multi_index::insert(value_type& v)
{
  for each index
    index->insert(v.get_super_node());
}
and
sequenced_index::insert(value_type& v)
{
  combination = v.get_super_node()->get_index_combination();
  for each index in combination
    index->insert(v.get_super_node());
}

I have decided against the use of a predicate template parameter in
sequenced_index because it is not sufficient enough for more complex
uses. For example:
if (predicate(value))
  insert into sequenced_index A
else
  insert into sequenced_index B

I was thinking about using some kind of inserter object that the user can
compose
for this purpose.
I am interested in putting this up on sourceforge as soon as I feel that the
code has
advanced sufficiently.

Kevin