3 ms·
> vectors, making linear search slower The standard library gives you plenty of tools to maintain and search in a sorted vector. Often enough still faster than
by josefx 4y ago
> vectors, making linear search slower
The standard library gives you plenty of tools to maintain and search in a sorted vector. Often enough still faster than maps.
> Oh and of course that senior engineer will also hopefully be the one monitoring the lengths of all those vectors in production.
Doesn't a std::map have more space overhead than a vector?
- BeetleB 4y agoI believe he was referring to the number of elements in a vector, to know when to swap with a different data structure - not the size in bytes. But to your point - I once needed to do a key/value lookup for a large data set, and so of course I used a map. Then I ran out of RAM (had 80GB of it too!). So I switched to a vector and pre-sorted it and used binary_search for lookups (data set was static - populate once and the rest of the codebase didn't modify it). And of course, the RAM consumption was less than half that of the map.
- sfink 4y agoJust describe your sorted list as "a balanced binary tree with implicit child links" and then you get credit for being fast, space-efficient, and using fancy data structure.