理解 std::map::insert 并放置提示

Question

问题> 我试着理解 insert 和 emplace 的用法，并向 std::map 介绍了提示。在下面的测试中，在我看来，老式 insert 是最快的。我是不是做错了什么？

谢谢

static void MapEmplaceWithHint(benchmark::State& state) {
    std::vector<int> v{12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    std::map<int, int> mapInt;
    auto where(std::end(mapInt));
        
  for (auto _ : state) {
   for (const auto &n : v) { // Items in non-incremental order
        where = mapInt.emplace_hint(where, n, n+1);
    }
  }
}
BENCHMARK(MapEmplaceWithHint);

static void MapInsertWithHint(benchmark::State& state) {
    std::vector<int> v{12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    std::map<int, int> mapInt;
    auto where(std::end(mapInt));
        
  for (auto _ : state) {
   for (const auto &n : v) { // Items in non-incremental order
        where = mapInt.insert(where, {n, n+1});
    }
  }
}
BENCHMARK(MapInsertWithHint);

static void MapInsertNoHint(benchmark::State& state) {
    std::vector<int> v{12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    std::map<int, int> mapInt;
        
  for (auto _ : state) {
   for (const auto &n : v) { // Items in non-incremental order
        mapInt.insert({n, n+1});
    }
  }
}
BENCHMARK(MapInsertNoHint);

static void MapReverseInsertNoHint(benchmark::State& state) {
    std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12};
    std::map<int, int> mapInt;
        
  for (auto _ : state) {
   for (const auto &n : v) { // Items in incremental order
        mapInt.insert({n, n+1});
    }
  }
}
BENCHMARK(MapReverseInsertNoHint);

static void MapEmplaceNoHint(benchmark::State& state) {
    std::vector<int> v{12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    std::map<int, int> mapInt;
        
  for (auto _ : state) {
   for (const auto &n : v) { // Items in non-incremental order
        mapInt.emplace(n, n+1);
    }
  }
}
BENCHMARK(MapEmplaceNoHint);

Answer 1

首先，让我们创建一个比 12 个整数更有意义的数据集：

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

所有函数的结果现在更具可比性：https://quick-bench.com/q/HW3eYL1RaFMCJvDdGLBJwEbDLdg

然而，还有更糟糕的事情。请注意，循环遍历 state 会使其多次执行相同的操作以测量平均时间。但是，由于您正在重复使用同一个映射，因此在第一次循环迭代失败后每个 insert 或 emplace，因此您主要测量失败插入的时间，其中 hint 没有帮助。

测试用例应该更像这样：

  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);
    }
  }

有了这个，提示开始闪耀（必须将数据限制为 1000，否则我会超时）：https://quick-bench.com/q/2cR4zU_FZ5HQ6owPj9Ka_y9FtZE

我不确定基准测试是否正确，但快速浏览一下程序集表明插入没有完全优化，所以它有可能足够好。

正如 Ted Lyngmo 所注意到的，try_emplace() 和 hint 的表现往往（稍微）更好：
https://quick-bench.com/q/evwcw4ovP20qJzfsyl6M-_37HzI

理解 std::map::insert 并放置提示

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

c++

stl