4 ms·
Based on experience I'm going to form an educated guess (hypothesize) and say that both std::map and author's trie container are primarily bound by pointer chas
by mtanski 9y ago
Based on experience I'm going to form an educated guess (hypothesize) and say that both std::map and author's trie container are primarily bound by pointer chasing. Obviously one should test this.
If that's the case, use a C++ btree_map implementation.
- adzm 9y agoI'm fond of sorted vectors as well such as boost flat_map. The worst case performance can be surprising! But eventually if it gets too big you'll need a btree
- pekk 9y agoCan you share an instance where you actually needed a btree? What made it a true need (business need of some kind maybe_ and not just a measurable difference?
- AstralStorm 9y agoGenerally the requirement for range queries and piercing queries. (Does range x,y contain object o; is object o overlapping range described by object p) Additionally requirement to maximize immutability for reasons of thread safety. Range queries do not really work well on sorted vectors even if you have as many as needed indices. Immutability and race freedom are even more complex. With a tree, copy on write solves many problems. (And can be much cheaper than copying whole structure.) If not, you can atomically replace subtrees in a safe way.