Subject: Re: [boost] Extending multi_index_container hash tables
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2011-05-06 15:03:09
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.
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
> Second, there is no possibility to use internal order of the records in the
> bucket, i.e. operations like popping the last element in the bucket's list.
> Such feature could be useful for, for example, priority queues. It could be
> realized by using such double-linked (or extra pointers in a bucket
Hahsed indices have the following bucket-handling interface:
// bucket interface:
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;
Is this not what you're looking for?
JoaquÃn M LÃ³pez MuÃ±oz
TelefÃ³nica, InvestigaciÃ³n y Desarrollo
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk