3 ms·
I'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
by adzm 10y ago
I'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 10y 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 10y 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.