4 ms·
> [V]ectors outperform other data structures ... even for things that require lookup (i.e. vector outperforming a set) This is something I've heard before (not
by asveikau 4y ago
> [V]ectors outperform other data structures ... even for things that require lookup (i.e. vector outperforming a set)
This is something I've heard before (not often benchmarked) and it makes intuitive sense, and sometimes I've also told it to myself in order to not feel bad for writing O(n) where n is always small.
But somehow, reading this snippet, I'm reminded that the vector does not maintain the semantic reminder that it's used in a key/value use case. So it has me thinking there should be a map/hashtable/dictionary interface that's really just a vector with linear lookup.
Then I think, hmm, maybe the standard containers should just do that. Maybe the authors of those should have some heuristic of "when to get fancy".
- KerrAvon 4y agoI think the cases where lookup is faster for a linearly scanned vector is where the hash computation overhead is greater than a linear scan. Assuming you have a good hash implementation, that should be true only for a small number of entries, where you need to determine "small" by measuring.
- asveikau 4y agoI think it's about locality and quickness of compare. So if you have a small data structure and/or large cache, and the key is not complicated.
- bluGill 4y agoEven if the key is cheap, that it isn't in cache means that vector will be faster just because we avoid the cache miss of loading the value into memory.
- bluGill 4y agoStd::find_if works great if you want to treat a vector like a map. Plus you can have different keys if that is useful for your problem (look up employee by name, id, or address?)
- dabitude 4y agoThese are flat_map, flat_set, flat_hash_map, etc ... See: https://en.cppreference.com/w/cpp/header/flat_map https://en.cppreference.com/w/cpp/header/flat_map