On 09/11/2015 08:00 AM, Andrey Semashev wrote:
Could you provide more details on your container special features and advantages/weaknesses? E.g. how is it better than, for instance, Boost.MultiIndex with random access and binary lookup indices?
My segmented_tree_seq container provides the same interface as std::vector/std::deque (excepting reserve and shrink_to_fit) while Boost.MultiIndex has an interface of its own. Also, given that Boost.MultiIndex provides stable iterators, I'd expect it allocates each element individually. This makes it completely unsuitable for many applications such as storing a buffer of 8bit characters. It probably also means that it's performance would be similar to avl_array which I outperform by as much as 10x in many benchmarks. My container does not provide stable iterators and as a consequence is able to be implemented in a very cache efficient way. Much like you should prefer vector when you are doing insert/erase near the end, and you should prefer deque when you are doing insert/erase near both ends, you should prefer my container when you are doing insert/erase at any index.
O(log n) random access is an unusual trait; random access containers are usually able to provide O(1) complexity for accessing an element by index. It seems there is a key-value lookup instead of a true random access. Am I correct?
As the name suggest, segmented_tree_seq is a tree. It maintains an B+Tree index into chunks of data similar to how deque maintains a vector index into chunks of data.