std::set emplace_hint() 方法

自 C++11 起

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

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

元素的构造函数将使用与提供给函数完全相同的参数调用，并通过 std::forward<Args>(args)... 进行转发。

参数

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

返回值

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

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

复杂度

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

异常

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

示例

Main.cpp

#include <chrono>
#include <functional>
#include <iomanip>
#include <iostream>
#include <set>
 
const int n_operations = 100500;
 
std::size_t set_emplace() {
    std::set<int> set;
    for(int i = 0; i < n_operations; ++i) {
        set.emplace(i);
    }
    return set.size();
}
 
std::size_t set_emplace_hint() {
    std::set<int> set;
    auto it = set.begin();
    for(int i = 0; i < n_operations; ++i) {
        set.emplace_hint(it, i);
        it = set.end();
    }
    return set.size();
}
 
std::size_t set_emplace_hint_wrong() {
    std::set<int> set;
    auto it = set.begin();
    for(int i = n_operations; i > 0; --i) {
        set.emplace_hint(it, i);
        it = set.end();
    }
    return set.size();
}
 
std::size_t set_emplace_hint_corrected() {
    std::set<int> set;
    auto it = set.begin();
    for(int i = n_operations; i > 0; --i) {
        set.emplace_hint(it, i);
        it = set.begin();
    }
    return set.size();
}
 
std::size_t set_emplace_hint_closest() {
    std::set<int> set;
    auto it = set.begin();
    for(int i = 0; i < n_operations; ++i) {
        it = set.emplace_hint(it, i);
    }
    return set.size();
}
 
void timeit(std::function<std::size_t()> set_test, const char* what = nullptr) {
    const auto start = std::chrono::system_clock::now();
    const std::size_t setsize = set_test();
    const auto stop = std::chrono::system_clock::now();
    const std::chrono::duration<double, std::milli> time = stop - start;
    if (what != nullptr && setsize > 0) {
        std::cout << std::setw(6) << time.count() << "  ms for " << what << '\n';
    }
}
 
int main() {
    std::cout << std::fixed << std::setprecision(2);
    timeit(set_emplace); // stack warmup
    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");
}

可能输出

 25.50  ms for plain emplace
  9.79  ms for emplace with correct hint
 28.49  ms for emplace with wrong hint
  8.01  ms for corrected emplace
  8.13  ms for emplace using returned iterator