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.