Understand std::map::insert & emplace with hint-CodePudding

CodePudding user response：

First, let's create a dataset more meaningful than 12 integers:

  std::vector<int> v(10000);
  std::iota(v.rbegin(), v.rend(), 0);

Results from all functions are now more comparable:

However, there's a worse thing. Notice that looping over state makes it perform the same operations several times to measure the average time. But, since you are reusing the same map, each insert or emplace after the first loop iteration is failing, so you mostly measure time of failed inserts, where hint doesn't help.

Test cases should look more like this:

  std::vector<int> v(1000);
  std::iota(v.rbegin(), v.rend(), 0);

  for (auto _ : state) {
    std::map<int, int> mapInt;
    auto where(std::end(mapInt));
        
   for (const auto &n : v) { // Items in non-incremental order
        where = mapInt.emplace_hint(where, n, n 1);
    }
  }

And with this, hints start to shine (had to limit data to 1000, otherwise I'd get timeouts):

I'm not sure if the benchmarks are correct, but quick glance in the assembly suggests that inserts were not optimized altogether, so there's a chance it's good enough.

As noticed by