时间戳

首页 > 解决方案 > std::set::emplace_hint() 实际上如何加速插入过程？

c++ - std::set::emplace_hint() 实际上如何加速插入过程？

问题描述

我不明白（尽管有评论）emplace_hint() 函数是如何工作的，emplace_hint() 实际上如何加快插入过程？有人可以解释一下代码吗？

// CPP program to demonstrate the 
// set::emplace_hint() function 
#include <iostream>
#include <set> 
using namespace std; 
int main() 
{ 

  set<int> s; 
  auto it = s.emplace_hint(s.begin(), 1); 

    /* stores the position of 2's insertion*/ 
    it = s.emplace_hint(it, 2); 

    /* fast step as it directly 
    starts the search step from 
    position where 3 was last inserted */
    s.emplace_hint(it, 3); 

    /* this is a slower step as 
    it starts checking from the 
    position where 3 was inserted 
    but 0 is to be inserted before 1 */
    s.emplace_hint(it, 0); 

    /* prints the set elements*/ 
    for (auto it = s.begin(); it != s.end(); it++) 
        cout << *it << " "; 

    return 0; 
}

标签： c++stl

解决方案

std::set通常实现为平衡二叉搜索树。通常，set::insert需要搜索树来为新元素找到合适的插入点，这需要O(log N)时间。但是如果调用者可以提供一个正确的插入点——即，一个与新元素相邻的现有元素的迭代器——那么可以避免这种搜索，并且可以在 O(1) 时间内完成插入。

emplace_hint让调用者有机会提供该迭代​​器。

推荐阅读