[boost] Extending multi_index_container hash tables

Subject: [boost] Extending multi_index_container hash tables
From: Vladimir Voznesensky (vvoznesensky_at_[hidden])
Date: 2011-05-06 00:33:21

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.

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

Sure, I could get the current realization and write my own index, but it
seems wiser to extend the current implementation to support custom bucket
container or custom node as a template parameter.

Thanks in advance.
VV