Also note that all <algorithm>s have built-in fully automatic parallelism via <execution>, a massively underused feature. In typical CPP fashion though, their newer views:: counterparts lack those overloads for the moment.
(Not std::map, at the time it must have been something like tsl:: hopscotch_map).
Note also that nowadays for instance boost comes with state-of-the-art flat_map and flat_unordered_map which gives both the cache coherency for small sizes and the algorithmic characteristics of various kinds of maps
For an unsuccessful search, the vector version would do 100 key comparisons, and the hashtag would do a single hash, lookup the bucket, and almost certainly find it empty.
So, if you make the comparison function relatively expensive, I can see the hash map being faster at search.
Even relatively short string keys might be sufficient here, if the string data isn’t stored inline. Then, the key comparisons are likely to cause more cache misses than accessing a single the bucket.
Of course, the moment you start iterating over all items often, the picture will change.
Given the predictable access nature of vectors and their contiguous layout in the memory, the CPU backend will be able to take advantage of those facts and will be able to hide the memory latency (even within the L1+L2+L3 cache) by pre-fetching the data on consecutive cache-lines just as you go through the loop. Accessing the data that resides in L1 cache is ~4 cycles.
The "non-branchiness" of such code will make it predictable and as such will make it a good use of BTB buffers. Predictability will prevent the CPU from having to flush the ROB and hence flushing the whole pipeline and starting all over again. The cost of this is one of the largest there are within the CPU and it is ~15 cycles.
OTOH searching the open-addressing hashmap is the super-set of that - e.g. almost as if you're searching over an array of vectors. So, only the search code is: (1) By several factors larger, (2) Much more branchy, (3) Less predictable and (4) Less cache-friendly.
Algorithmically speaking, yes, what you're saying makes sense, but I think the whole picture can only be made once the hardware details are also taken into account. Vector approach will literally be only bound by the number of cycles it takes to fetch the data from L1 cache and I don't see that happening for a hash-map.
This is a very poor way to choose a data structure. How many items you want to store is not what someone should be thinking about.
How you are going to access it is what is important. Looping through it - vector. Random access - hash map. These two data structures are what people need 90% of the time.
If you are putting data on the heap it is already because you don't know how many items you want to store.
(But I'm about to move it to GPU)
…but in order for this to really matter, communication is required, since even the best developers don’t scale.
This is never a scenario that should happen, because if you are going to retrieve an arbitrary element it should be in a hash map or sorted map.