The most important piece of code in this blog post is right here: for (size_t i = 0; i != NUM_KEYS; ++i) { int key = dis(gen); for (size_t j = 0; j

The most important piece of code in this blog post is right here: for (size_t i = 0; i != NUM_KEYS; ++i) { int key = dis(gen); for (size_t j = 0; j != NUM_2ND_KEYS; ++j) { int key2 = dis(gen); A whole bunch of 2nd keys are generated for each "1st" key. In the parts of the chart where blue beats red, where you've got 2000 "1st" keys, with a MAX_VAL of 100000, each query only has a 2% chance of hitting a "1st" key and experiencing any sort of vector traversal. If you merely generated NUM_KEYS * NUM_2ND_KEYS combinations of 1st and 2nd independent keys, the cost of what once were rare long traversals would be de-amortized into a bunch of tiny traversals that don't benefit from locality. If you only run queries on keys actually present in the data set (which is a far more typical use case than guessing points in a sparse data set), you'll soon regret the use of a vector. Edit: It's also worth pointing out that the implementation with a vector is missing values, which it needs to be functionally equivalent. Changing it to a vector<pair<int, int>> will hurt your vector traversal times. (Replacing the vector with a std::unordered_map<int, int> will improve your performance.)