C++ 0x问题:将时间插入到std :: set中

Question

根据这个页面,如果我使用,我可以实现恒定时间插入

iterator std::set::insert ( iterator position, const value_type& x );

position我提供的迭代器直接"在"正确(有序)插入点之前.

现在我关心的情况是,如果我知道我插入的值最后(因为它是最大的),例如:

set<int> foo = {1, 2, 3};
foo.insert(4); // this is an inefficient insert

根据上述标准,我应该将最后一个元素传递foo.end()-1给insert 不 foo.end().我的理解是否正确？如果我通过foo.end()会怎么样？它会是O(log n)插入还是插入O(1).所以,选项是:

// Option A
foo.insert(foo.end()-1, 4);

// Option B
foo.insert(foo.end(), 4);

// Safer version of Option A
if(foo.empty())
    foo.insert(4);
else
    foo.insert(foo.end()-1, 4);

我问,因为我正在编写一个在容器上模板化的函数.我想在传入任何容器的末尾插入一个元素(我知道是最大的).使用上面的"选项A"对容器有不同的行为,如vector:

foo.insert(foo.end()-1, 4);
// result is {1, 2, 3, 4} if foo is an std::set
// result is {1, 2, 4, 3} if foo is an std::vector

正如@Bo_Persson所暗示的,这里的问题是C++ 03说"一般是对数,但如果在p之后插入t,则摊销常数." 而C++ 0x表示"一般为对数,但如果在p之前插入t,则摊销常数."

PS:我在Ubuntu 11.04上使用GCC 4.5并启用了C++ 0x支持.

编辑:我运行经验测试,启用和禁用C++ 0x支持,并将结果发布到答案中.基本上,结论是提供end()插入提示同样好(并且显然更安全).然而,这显然只是一个经验观察.如上所述,标准在这方面仍然令人困惑.

Answer 1

运行测试而不阅读库规范是作弊吗？

对于g++-4.4 -O2整数，0 <= i < 5000000我的标准插入运行时间是

real    0m14.952s
user    0m14.665s
sys 0m0.268s

我使用end()提示插入的运行时间是

real    0m4.373s
user    0m4.148s
sys 0m0.224s

据我所知，插入 at 的end() - 1速度最快，但使用起来比较麻烦，因为它是end() - 1非法操作（您必须使用operator--()），并且如果集合碰巧为空，它就会崩溃。

#include <set>

typedef std::set<int> Set;

void insert_standard(Set& xs, int x)
{
    xs.insert(x);
}

void insert_hint_end(Set& xs, int x)
{
    xs.insert(xs.end(), x);
}

int main()
{
    const int cnt = 5000000;
    Set xs;
    for (int i = 0; i < cnt; i++) {
        // insert_hint_end(xs, i);
        insert_standard(xs, i);
    }
}