Re:In Defense of Linked Lists
by zelphirkalt on Saturday November 05, 2022 @04:50AM
(#33479350)
I hope that senior engineer is also the one person, who will refactor things, if ever there are more elements in any of those vectors, making linear search slower than an actual set or other data structure. Oh and of course that senior engineer will also hopefully be the one monitoring the lengths of all those vectors in production.
[ Parent
| on HN ]
> 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?
I 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.