While it's true that "measure everything" is a good ideal to aim for, I think this article also ends up demonstrating why that's actually hard in practice. One

While it's true that "measure everything" is a good ideal to aim for, I think this article also ends up demonstrating why that's actually hard in practice. One of the reasons it is hard is that "the right datastructure for the job" often depends very much on the details of "the job", including things like the expected distribution of inputs and also on what "right" means for the particular job (e.g. do we prefer to get the best possible average times or to avoid bad worst case times in favour of worse averages). The first example raises as many questions as it answers. In practice I'd consider using a sorted vector with binary search lookup over a hash map in situations where key insertion / deletion either happens entirely up front or is very infrequent relative to lookup. The benchmark here does have all insertions upfront but doesn't test a sorted vector with binary search. The problem description suggests that insertions and deletions will happen for the real use case however, though we don't really know with what relative frequencies. If we were to use a sorted vector, performance in the use case described would be affected by the size of the cached data if the data was stored 'inline' (as a vector<pair<key, value>>) and if it was stored elsewhere would depend on how we accessed it after finding the key. The best choice there would in turn depend on the relative frequencies and distribution of insertions and deletions and the percentage of cache hits. In practice I think simple synthetic benchmarks like this end up being of limited value. Usually you're better off implementing something simple with reasonable theoretical performance based on your expectations of the distribution of data you'll see, then profiling / benchmarking with representative data (ideally captured real world data) once you have something working. Making guesses / approximations up front about the data distribution you'll see in practice can be just as misleading as relying on your intuitions about performance without measuring. Sometimes you have a good understanding of the data you'll have to deal with up front (or even have the data available for testing), in which case you may be able to do a better job of building meaningful benchmarks before starting a full implementation, but in my experience that's relatively rare (though in other domains it may be more common).