我正在做很多很多std :: pair< int,int>的插入进入std :: set,它比我想要的时间更长.当我编写代码时,我认为如果事实证明它是一个瓶颈,我将在稍后使用插入的提示迭代器形式;好吧,现在它的形象,它是一个瓶颈.所以我想使用迭代器提示.
但是,我并不总是知道插入我的对的好位置.我通常批量插入它们(在这种情况下批量大约占总输入大小的0.01％,包括重复)增加的设置顺序,但是当插入批次时,我不知道下一个应该在哪里开始.如何使用提示？插入是否从建议的位置执行二分搜索？通常情况下,使用不良提示有多糟糕？
解决方法
我建议只阅读编译器读取的内容：#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); }
带走：
>糟糕的提示不会导致效率上升
>插入是O(log n)
>您可以阅读更多关于insertion hints in the GNU libstdc++ manual的内容.
