Random access from index

[jdumas]

Hi,

Thanks for the work you've been doing on the colony/hive container, it's inspiring! Looking at your website, you describe an algorithm for random access in multiple blocks in constant time. But when I look at the current implementation of the hive container, it seems you are using a linked-list of memory blocks, so accessing an element from its index is not really a O(1) operation (you need to find the right block first).

Can you tell me if I miss something in the current hive implementation? Is the trick in the paper above used in another of your container at the moment? What are your thoughts of implementing a similar container to hive but that would support O(1) index-based access to its elements. The reason I am asking is because I am interested in referencing elements in a container that can be serialized/copied around, so storing pointers is not a good solution for me.

[mattreecebentley]

This is not an issue with the source, so it would've been better to email me - to answer your question, no you cannot use that strategy with hive, because that strategy relies on consolidated element space, whereas hive potentially has gaps between elements, if some elements have been erased. Since the hive doesn't know which elements are erased until it iterates (or process the erased-element free list), there is not to the best of my knowledge a way to make hive work with the strategy in question. If you want O(1) indexing, a deque or vector is your best bet. Boost's deque allows you to specify the block capacities yourself, and their 'devector' is also an option. Cheers-

[mattreecebentley]

ps. I have a proof-of-concept container which implements the strategy you're describing, but it's not fit for public display. If the reason you're interested in hive is to retain valid indexes to elements regardless of erasures/insertions into the container, bear in mind that won't work. As soon as you erase an element, you change the indexes for every element after it - unlike with pointers. The std::advance/std::next/std::prev overloads for the container are between O(1) and O(n) time, but they index based on what non-erased elements exist. Thanks for your support of hive btw :)

[jdumas]

Thanks for the answer! I'll reach out via email to continue the conversation then :)