[boost] [multi_index] Extending multi_index_container hash tables

Subject: [boost] [multi_index] Extending multi_index_container hash tables
From: Vladimir Voznesensky (vvoznesensky_at_[hidden])
Date: 2011-05-16 15:37:48

Dear Joaquin,
Dear all,

Please, find the comments below.

Joaquin M Lopez Munoz writes:

> Vladimir Voznesensky<vvoznesensky<at>  gmail.com>  writes:
>
>    
>> >  
>> >  Hello there.
>> >  
>> >  Current implementation of hashed index has, at least, two issues, preventing
>> >  me from re-using it in some places.
>> >  
>> >  First, the time for unlink operation in
>> >  multi_index/detail/hash_index_node.hpp is O(m) where m is a occupancy of the
>> >  given bucket. I'ts usually ok for unique index, but seems to hit performance
>> >  of removing item in a non-unique index. It's all because of using
>> >  single-linked list instead of double-linked one.
>>      
> The question here is whether non-unique indices will be populated
> with many equivalent elements or not: if the former, a singly-linked
> list implementation such as that of Boost.MultiIndex certainly
> degrades at erasure, but going to a doubly-linked list unncessarily
> imposes a non-negligible penalty (one pointer per element) in the
> latter case. Having to decide I chose to favor the former case.
>    
I think it should be up to a user to choose: the usage pattern could
be very specific (for instance, a LIFO pattern seems to work OK
with the single linked machinery).
> If you can contribute a Boost-quality modification of the implementation
> that lets the user decide between singly-linked and doubly-linked
> implementation (say with an extra template paramater in
> the hashed<...>  index specifier I can certainly add it to the
> library.
>    
I have some questions to discuss here.

1. The 1st obvious step is to realize a double-
linked list near a single-linked one.
I plan not to subclass any stuff from the
current detail/hash_index_node.hpp,
but use it as a near sample.

Should I copy detail/hash_index_node.hpp
to, say, detail/hash_index_dbl_node.hpp
or use the same file for realization?

It seems not to be a problem to add a
concrete NodeImpl second template
argument to a class bucket_array.

2. hashed_index.hpp arise some gentle
problems. I could put another template
argument into detail::hashed_index,
hashed_unique and hashed_non_unique,
but what kind should it be?

It's seems possible to add NodeType
template argument to class hashed_index
without breaking up
BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
stuff, but how should we pass such
sophisticatedly formed type from the
final API? detail::hashed_index_args
looks like a template hell.

So, maybe it would be wiser to just
introduce
struct hashed_dbl_unique and
struct hashed_dbl_non_unique
extra variants?
> Hahsed indices have the following bucket-handling interface:
>
>    // bucket interface:
>
>    size_type bucket_count()const;
>    size_type max_bucket_count()const;
>    size_type bucket_size(size_type n)const;
>    size_type bucket(const key_type&  k)const;
>
>    local_iterator       begin(size_type n);
>    const_local_iterator begin(size_type n)const;
>    local_iterator       end(size_type n);
>    const_local_iterator end(size_type n)const;
>    const_local_iterator cbegin(size_type n)const;
>    const_local_iterator cend(size_type n)const;
>
>    local_iterator       local_iterator_to(const value_type&  x);
>    const_local_iterator local_iterator_to(const value_type&  x)const;
>
> (See
> http://www.boost.org/libs/multi_index/doc/reference/hash_indices.html#hash_indices)
> Is this not what you're looking for?
>    
It's not clear from the docs and the sources, how to, say, insert a new 
element before or after a given one.

Thank you.