2 
// set::insert (C++98)
#include <iostream>
#include <set>

int main ()
{
  std::set<int> myset;
  std::set<int>::iterator it;
  std::pair<std::set<int>::iterator,bool> ret;

  // set some initial values:
  for (int i=1; i<=5; ++i) myset.insert(i*10);    // set: 10 20 30 40 50

  ret = myset.insert(20);               // no new element inserted

  if (ret.second==false) it=ret.first;  // "it" now points to element 20

  myset.insert (it,25);                 // max efficiency inserting
  myset.insert (it,24);                 // max efficiency inserting
  myset.insert (it,26);                 // no max efficiency inserting

  int myints[]= {5,10,15};              // 10 already in set, not inserted
  myset.insert (myints,myints+3);

  std::cout << "myset contains:";
  for (it=myset.begin(); it!=myset.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

我将此代码视为 cplusplus 参考站点上的示例。它说

myset.insert (it,25);                 // max efficiency inserting
myset.insert (it,24);                 // max efficiency inserting

这是插入的最大效率，但我不明白。谁能告诉我为什么？

4

3 回答 3

3

std::set使用平衡的树结构。当您调用 时insert，您可以为实现提供提示 - 它可以用来加速插入。

想想insert常规二叉搜索树的一般方法是如何工作的。您从根节点开始，您必须使用通常的检查向下进行：

void insert(node* current, const T& value)
{
    if(node == nullptr) // Construct our new node here
    else if(value < node->current) insert(current->left, value);
    else if(value > node->current) insert(current->right, value);
}

void insert(const T& value)
{
    insert(root, value);
}

在平衡树中，这必须执行（平均）O(log n)比较以插入给定值。

但是，假设我们不是从根节点开始，而是给实现一个起始节点，这是实际插入发生的地方。例如，在上面，我们知道 24 和 25 将成为包含 的节点的子节点20。因此，如果我们从那个节点开始，我们不需要进行O(log n)比较——我们可以直接插入我们的节点。这就是“最大效率”插入的意思。

于 2013-09-02T07:59:51.210 回答
0

一般来说，std::set必须查找它插入的位置；这个查找是 O(lg n)。如果您在应该进行插入的位置提供“提示”（附加迭代器），则实现将首先检查此提示是否正确（可以在 O(1) 中完成），如果是，则在此处插入，因此跳过 O(lg n) 查找。当然，如果提示不正确，它就会恢复插入，就好像它没有得到提示一样。

有两种情况经常使用提示：第一种是插入已排序的数据序列时。在这种情况下，提示是结束迭代器，因为如果数据已经排序，实际上每个新值都会插入到最后。第二个是使用插入迭代器复制到集合中时。在这种情况下，“提示”（可以是任何东西）不仅用于语法原因：您不能使用 aback_insertion_iterator或 a front_insertion_iterator，因为std::set没有push_backor push_front，并且简单insertion_iterator需要一个迭代器来告诉它在哪里插入; 这个迭代器将被传递给insert.

于 2013-09-02T08:20:58.057 回答
0

你读过通知吗？

position 提示可以插入元素的位置。c++98 如果位置指向将在插入元素之前的元素，则该函数优化其插入时间。

它指向 20 并在 25 之前。

于 2013-09-02T07:58:17.957 回答