map::emplace不总是比map::insert快

自C++11起,标准库中的许多集合类型提供了emplace函数,可以在集合内直接创建新元素,而不需要将现有元素复制或移动到集合内。在很多情况下,使用emplace函数能够减少复制或移动构造函数的开销,能提供比insertpush等函数更高的性能。但对于std::mapstd::unordered_map而言,在某些情况下insert可能比emplace更快。

调用std::map<TKey, TValue>::insert函数需要传入一个std::pair<TKey, TValue>对象。在实际插入时,这个pair会用于复制构造或移动构造map中实际的存储对象,这样会产生一次复制操作。调用std::map<TKey, TValue>::emplace函数时,则会使用传入的参数直接在实际的存储位置原地构造一个std::pair<TKey, TValue>,这样通常可以减少一次复制操作1

但是,若key原本就已经存在,则insert只需完成键的对比就可以直接返回了,而emplace将必须原地构造一个新的对象才能开始对比,使用emplace将需要额外的构造开销。根据Quick C++ Benchmarks (quick-bench.com)的测试结果,下面的代码中,MapEmplace算例所用时间大约为MapInsertConst算例的3倍。

static void MapEmplace(benchmark::State& state) {
  map<string, int> s;
  string val("SomeVeryLongString");
  s.emplace(val, 1);

  for (auto _ : state) {
    s.emplace(val, 1);
  }
}

BENCHMARK(MapEmplace);

static void MapInsertConst(benchmark::State& state) {
  map<string, int> s;
  string val("SomeVeryLongString");
  const pair<const string, int> p{val, 1};
  s.emplace(val, 1);

  for (auto _ : state) {
    s.insert(p);
  }
}

BENCHMARK(MapInsertConst);

需要注意的是,若使用非const的左值作为insert函数的参数,则会调用template<class P> insert(P&& value)这一重载,而不是insert(value_type&& value)。这实际上等同于直接调用emplace1。下面的测试代码中,MapInsert所用时间约为MapInsertConst的3倍。

static void MapInsert(benchmark::State& state) {
  map<string, int> s;
  string val("SomeVeryLongString");
  pair<const string, int> p{val, 1};
  s.emplace(val, 1);

  for (auto _ : state) {
    s.insert(p);
  }
}

BENCHMARK(MapInsert);

static void MapInsertConst(benchmark::State& state) {
  map<string, int> s;
  string val("SomeVeryLongString");
  const pair<const string, int> p{val, 1};
  s.emplace(val, 1);

  for (auto _ : state) {
    s.insert(p);
  }
}

BENCHMARK(MapInsertConst);

参考文献

  1. std::map<Key,T,Compare,Allocator>::emplace – cppreference.com