Dear Joaquin, Dear all, Please, find the comments below. Joaquin M Lopez Munoz writes:
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.
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 BOOST_MULTI_INDEX_ENABLE_SAFE_MODE 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 introduce 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 http://www.boost.org/libs/multi_index/doc/reference/hash_indices.html#hash_i...) 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.