Extending multi_index_container hash tables
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
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_i...) Is this not what you're looking for? Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
participants (2)
-
Joaquin M Lopez Munoz -
Vladimir Voznesensky