Boost logo

Boost :

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>> 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
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
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
> 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.

Boost list run by bdawes at, gregod at, cpdaniel at, john at