std::map emplace_hint() 方法

自 C++11 起

// Non const version only
template <class... Args>
iterator emplace_hint( const_iterator hint, Args&&... args );

在尽可能靠近 hint 之前的位置插入一个新元素到容器中。该元素原地构造，即不执行复制或移动操作。

新元素（即 std::pair<const Key, T>）的构造函数使用与提供给 emplace 的完全相同的参数调用，通过 std::forward<Args>(args)... 进行转发。

不使任何迭代器或引用失效。

参数

• hint - 指向新元素将插入位置之前的迭代器
• args - 转发给元素构造函数的参数

返回值

返回指向新插入元素的迭代器。如果插入失败，因为元素已经存在，则返回指向具有等效键的已存在元素的迭代器。

复杂度

通常情况下，时间复杂度与容器大小呈对数关系 - O(log size())。
如果新元素恰好插入到 hint 之前，则分摊常量时间 - O(1)。

异常

如果任何操作抛出异常，此函数不产生任何影响（强异常保证）。

示例

Main.cpp

#include <chrono>
#include <iostream>
#include <iomanip>
#include <functional>
#include <map>
 
const int nof_operations = 100500;
 
int map_emplace() {
  std::map<int, char> map;
  for(int i = 0; i < nof_operations; ++i) {
    map.emplace(i, 'a');
  }
  return map.size();
}
 
int map_emplace_hint() {
  std::map<int, char> map;
  auto it = map.begin();
  for(int i = 0; i < nof_operations; ++i) {
    map.emplace_hint(it, i, 'b');
    it = map.end();
  }
  return map.size();
}
 
int map_emplace_hint_wrong() {
  std::map<int, char> map;
  auto it = map.begin();
  for(int i = nof_operations; i > 0; --i) {
    map.emplace_hint(it, i, 'c');
    it = map.end();
  }
  return map.size();
}
 
int map_emplace_hint_corrected() {
  std::map<int, char> map;
  auto it = map.begin();
  for(int i = nof_operations; i > 0; --i) {
    map.emplace_hint(it, i, 'd');
    it = map.begin();
  }
  return map.size();
}
 
int map_emplace_hint_closest() {
  std::map<int, char> map;
  auto it = map.begin();
  for(int i = 0; i < nof_operations; ++i) {
    it = map.emplace_hint(it, i, 'e');
  }
  return map.size();
}
 
void timeit(std::function<int()> map_test, std::string what = "") {
  auto start = std::chrono::system_clock::now();
  int mapsize = map_test();
  auto stop = std::chrono::system_clock::now();
  std::chrono::duration<double, std::milli> time = stop - start;
  if (what.size() > 0 && mapsize > 0) {
    std::cout << std::fixed << std::setprecision(2) << std::setw(5)
              << time.count() << "  ms for " << what << '\n';
  }
}
 
int main() {
   timeit(map_emplace); // stack warmup
   timeit(map_emplace, "plain emplace");
   timeit(map_emplace_hint, "emplace with correct hint");
   timeit(map_emplace_hint_wrong, "emplace with wrong hint");
   timeit(map_emplace_hint_corrected, "corrected emplace");
   timeit(map_emplace_hint_closest, "emplace using returned iterator");
}

输出

22.64  ms for plain emplace
 8.81  ms for emplace with correct hint
22.27  ms for emplace with wrong hint
 7.76  ms for corrected emplace
 8.30  ms for emplace using returned iterator