3 ms·
> So far all we've done is replaced every STL container with vector. This is something that's easy to do for new code, so I would say it should be a style decis
by amluto 6y ago
> So far all we've done is replaced every STL container with vector. This is something that's easy to do for new code, so I would say it should be a style decision - default to vector and don't pick up sets/maps/lists/whatever unless you have a really, really, really good reason.
There is frequently a really really good reason: when I write set<Foo>, I want a set, not a vector. This frequently has little to do with the underlying data structure or asymptotic complexity or performance at all — it’s a semantic issue. I want a container of distinct elements in which order doesn’t matter. I want to be able to ask whether an element is in the set, I want to be able to insert an element if it doesn’t exist, and I want a guarantee that the same element isn’t there more than once. Similarly, if I type map, I want a map, thank you very much.
This can be reconciled with performance: don’t use red/black trees. An actual high quality set or map will likely be backed by arrays or things much like arrays. B-trees can have very large nodes, aka arrays. Judy arrays are a whole pile of different underlying data structures under the hood. Some hash tables are basically arrays with 70% or so occupancy.
It’s also worth noting that using asymptotically horrible algorithms that are fast on your test case can be a security problem. And it can also cause hilarious slowdowns like the recently reported GTA Online issue. So be careful throwing extra O(n) factors around.