Boost logo

Boost :

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2022-07-25 14:29:25


Jooseong Lee wrote:
> I recently wrote a general-purpose STL-like ordered associative B-Tree
> based container in C++.
> .
> Its API and usage is very similar to std::set, std::map, std::multiset,
> std::multimap,
> and when the number of elements is relatively large, my benchmark shows
> that it is 2.5~3 times faster than std::set and its friends.
>
> Repo link: https://github.com/frozenca/BTree

I would be interested to see a comparison with Beman Dawes'
B-Tree library from 2010:

https://lists.boost.org/Archives/boost//2010/09/170995.php
https://github.com/Beman/btree

Personally, I often use flat sets/maps. Of course these are best
suited when lookups dominate over modifications. It would be interesting
to know how your library compares for lookups.

I see that you have O(log N) n-th element access, that it is an
interesting feature. Does this mean that every non-leaf node has a
count of its descendants?

I don't see how erase(a,b) can be O(log N), is that a typo?

In the past I have used a lot of memory-mapped, mostly read-only,
binary data structures but these days I'm more likely to use
sqlite. Have you tried to benchmark against that?

I note it is not Boost licensed.

Regards, Phil.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk