3 ms·
I'd love to see also comparison with B-trees (https://code.google.com/archive/p/cpp-btree/ https://code.google.com/archive/p/cpp-btree/). In my tests done a few
by wmu 8y ago
I'd love to see also comparison with B-trees (https://code.google.com/archive/p/cpp-btree/ https://code.google.com/archive/p/cpp-btree/). In my tests done a few years ago this implementation was faster than std::map. And my guess is the reason of it is better use of cache.
- s3cur3 8y agoHm, I'll look into it... :)
- jstimpfle 8y agostd::map is usually implemented as a Red-black tree. Which is basically a B-tree with branching factor 2. This is less cache friendly than higher branching factors, so it's entirely expected to be slower than B-trees. On the upside, it offers stable pointers which higher branching factors cannot offer.