On 9/17/06, "JOAQUIN LOPEZ MU?Z" <joaquin@tid.es> 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