Re:In Defense of Linked Lists
by BeetleB on Saturday November 05, 2022 @01:51PM
(#33483798)
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.
Re:In Defense of Linked Lists
by sfink on Saturday November 05, 2022 @02:22PM
(#33484150)
Just 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.
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.