Re: [boost] Extending multi_index_container hash tables

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

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

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?

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo