I 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.
I 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.
Even 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.
Std::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?)
These are flat_map, flat_set, flat_hash_map, etc ...
I believe that flat_map and flat_set at least are sorted, so that binary_search/lower_bound can be used for lookups.
Linear search generally does outperform for small collections though (it’s better for caches and the branch predictor).
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".