std :: set :: insert,我有多糟糕提示？

Question

我在做很多很多的插件std::pair<int, int>进入std::set,并且它花费的时间比我想.当我编写代码时,我认为如果事实证明它是一个瓶颈,我将在稍后使用提示迭代器形式的insert; 好吧,现在它被描述了,这是一个瓶颈.所以我想使用迭代器提示.

但是,我并不总是知道插入我的对的好位置.我通常批量插入它们(在这种情况下批量大约占总输入大小的0.01%,包括重复)增加的设置顺序,但是当插入批次时,我不知道下一个应该在哪里开始.如何使用提示？插入是否从建议的位置执行二分搜索？通常情况下,使用不良提示有多糟糕？

Answer 1

我建议只阅读编译器读取的内容：的头文件#include <set>。在我的系统（GNU libstdc ++ 4.5.1）上，我可以阅读以下不言自明的文本：

  /**
   *  @brief Attempts to insert an element into the %set.
   *  @param  position  An iterator that serves as a hint as to where the
   *                    element should be inserted.
   *  @param  x  Element to be inserted.
   *  @return  An iterator that points to the element with key of @a x (may
   *           or may not be the element passed in).
   *
   *  This function is not concerned about whether the insertion took place,
   *  and thus does not return a boolean like the single-argument insert()
   *  does.  Note that the first parameter is only a hint and can
   *  potentially improve the performance of the insertion process.  A bad
   *  hint would cause no gains in efficiency.
   *
   *  For more on @a hinting, see:
   *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
   *  
   *  Insertion requires logarithmic time (if the hint is not taken).
   */
  iterator
  insert(iterator __position, const value_type& __x)
  { return _M_t._M_insert_unique_(__position, __x); }

带走：

1. 不好的提示不会提高效率
2. 插入为 O(log n)
3. 您可以在GNU libstdc ++手册中阅读有关插入提示的更多信息。