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".
So if you have a small data structure and/or large cache, and the key is not complicated.
Linear search generally does outperform for small collections though (it’s better for caches and the branch predictor).
I am always uncomfortable using higher algorithmic complexity. Sure, for small data sets, the vector will outperform the set, but it may not stay small forever. I may waste a millisecond now, but at least, I won't waste an hour if the user decides to use 100x the amount of data I initially considered. And using much more data than expected is a very common thing. It is a robustness thing more than optimization.
If you want both, there are staged algorithms, a typical example is a sort algorithm that goes insertion -> quicksort -> mergesort. Insertion sort is O(N^2), but it is great for small arrays, quicksort is O(N log N) on average but may become O(N^2) in some cases, and mergesort is guaranteed O(N log N) and parallelizable, but it is also the slowest for small arrays. For lists, that would be a list of vectors.
Obviously, there is an overhead cost of the staging itself, which hits the use case for small data, and there is the question "From what data size onwards to use what algorithm?".
For example, I just had a look at sort in Clang's STL implementation, which seems to set a boundary at N=1000. Since the number is a multiple of 10, it looks like it might be arbitrarily picked, in any case there is no paper references in the comments to back it up.
Are people aware of formal studies that explore whether it is worth the trouble to inspect data structure and then to dispatch to different algorithms based on the findings?
Other than that, I'd suggest that big O complexity is already telling you that the inspection is worth it. Assuming inspection of an array is constant.
In over 90% of SW applications written in C++, there is little to no uncertainty on the size of the data set. Most applications are written for a very specific purpose, with fairly well known needs.
If my data set is size N, and I can benchmark and show the vector outperforms the theoretical option up to, say, 20N, it's a safe choice to go with vector. Doing these analyses is engineering.
In any case, it's almost trivial to swap out the vector with other options when needed, if you plan for it.
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?
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.
I think your parent's point is that if you're a C++ programmer, recognizing that vectors outperform other data structures for most use cases is what separates a good engineer from a great one. Often even for things that require lookup (i.e. vector outperforming a set).
During code reviews, a senior C++ programmer in my company (formerly sat in the C++ standards committee) would always demand benchmarks from the developer if they used anything else. In most cases, using representative real world data, they discovered that vectors outperformed even when the theoretical complexity of the other data structure was better.
A great engineer knows the limitation of theory.
Of course, my comment is only regarding C++. No guarantees that vectors are great in other languages.