std::set<Key,Compare,Allocator>::emplace_hint

< cpp‎ | container‎ | set
 
C++
 
容器库
 
std::set
 
template <class... Args>
iterator emplace_hint( const_iterator hint, Args&&... args );
 (C++11 起)

插入新元素到容器中尽可能接近于恰在 hint 前的位置。原位构造元素，即不进行复制或移动操作。

以提供给函数的参数准确相同者，以 std::forward<Args>(args)... 转发调用元素的构造函数。

没有迭代器或引用被非法化。

参数

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

返回值

返回指向新插入元素的迭代器。

若因元素已存在而插入失败，则返回指向拥有等价关键的既存元素的迭代器。

异常

若任何操作抛出异常，则此函数无效果（强异常保证）。

复杂度

通常与容器大小成对数，但若新元素正好被插入到 hint 之前则为均摊常数。

示例

运行此代码
#include <set>
#include <chrono>
#include <iostream>
#include <iomanip>
#include <functional>
 
const int nof_operations = 100500;
 
int set_emplace() {
  std::set<int> set;
  for(int i = 0; i < nof_operations; ++i) {
    set.emplace(i);
  }
  return set.size();
}
 
int set_emplace_hint() {
  std::set<int> set;
  auto it = set.begin();
  for(int i = 0; i < nof_operations; ++i) {
    set.emplace_hint(it, i);
    it = set.end();
  }
  return set.size();
}
 
int set_emplace_hint_wrong() {
  std::set<int> set;
  auto it = set.begin();
  for(int i = nof_operations; i > 0; --i) {
    set.emplace_hint(it, i);
    it = set.end();
  }
  return set.size();
}
 
int set_emplace_hint_corrected() {
  std::set<int> set;
  auto it = set.begin();
  for(int i = nof_operations; i > 0; --i) {
    set.emplace_hint(it, i);
    it = set.begin();
  }
  return set.size();
}
 
int set_emplace_hint_closest() {
  std::set<int> set;
  auto it = set.begin();
  for(int i = 0; i < nof_operations; ++i) {
    it = set.emplace_hint(it, i);
  }
  return set.size();
}
 
void timeit(std::function<int()> set_test, std::string what = "") {
  auto start = std::chrono::system_clock::now();
  int setsize = set_test();
  auto stop = std::chrono::system_clock::now();
  std::chrono::duration<double, std::milli> time = stop - start;
  if (what.size() > 0 && setsize > 0) {
    std::cout << std::fixed << std::setprecision(2)
              << time.count() << "  ms for " << what << '\n';
  }
}
 
int main() {
   timeit(set_emplace); // 栈加热
   timeit(set_emplace, "plain emplace");
   timeit(set_emplace_hint, "emplace with correct hint");
   timeit(set_emplace_hint_wrong, "emplace with wrong hint");
   timeit(set_emplace_hint_corrected, "corrected emplace");
   timeit(set_emplace_hint_closest, "emplace using returned iterator");
}

可能的输出： 

18.96  ms for plain emplace
7.95  ms for emplace with correct hint
19.39  ms for emplace with wrong hint
8.39  ms for corrected emplace
7.90  ms for emplace using returned iterator

参阅

(C++11)
 原位构造元素
(公开成员函数)
插入元素或结点 (C++17 起)
(公开成员函数)