std::set::emplace_hint

来自cppreference.com
< cpp‎ | container‎ | 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 起)
(公开成员函数) [编辑]