std::set::emplace_hint() 实际上如何加速插入过程? [英] How std::set::emplace_hint() actually speeds up the insertion process?

问题描述

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

//CPP 程序演示//set::emplace_hint() 函数#include #include <set>使用命名空间标准；int main(){设置s;auto it = s.emplace_hint(s.begin(), 1);/* 存储2的插入位置*/it = s.emplace_hint(it, 2);/* 快步，因为它直接从开始搜索步骤最后插入 3 的位置 */s.emplace_hint(it, 3);/* 这是一个较慢的步骤它从插入 3 的位置但是0要在1之前插入*/s.emplace_hint(it, 0);/* 打印集合元素*/for (auto it = s.begin(); it != s.end(); it++)cout<<*它<<"";返回0；}

解决方案

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

emplace_hint 给调用者提供迭代器的机会.

I don't understand(despite having comments)how the emplace_hint() function works,How an emplace_hint() actually speeds up the insertion process?Could someone explain me the code?

// 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; 
}

解决方案

std::set is usually implemented as a balanced binary search tree. Normally, set::insert would need to search the tree to find an appropriate insertion point for the new element, which takes O(log N) time. But if the caller can provide a correct spot for insertion - namely, an iterator to an existing element that would be adjacent to the new one - then this search can be avoided, and insertion can be done in O(1) time.

emplace_hint gives the caller the opportunity to provide that iterator.

这篇关于std::set::emplace_hint() 实际上如何加速插入过程?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！