C ++ 0x问题：将常量插入std :: set [英] C++0x issue: Constant time insertion into std::set

问题描述

根据此网页，我可以实现常量时间插入，如果我使用

According to this page, I can achieve constant time insertion if I use

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

和位置

现在我关心的情况是，如果我知道我插入的值到底是什么（因为它是最大的），例如：

Now the case I'm concerned with is if I know that the value I'm inserting goes at the end (since it's the largest), e.g.:

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

根据上述标准，我应该传递最后一个元素 foo.end（） - 1 到插入 不 foo.end ）。我的理解是正确的吗？如果我通过 foo.end（）会发生什么？它将是 O（log n）插入或 O（1）一个。所以，选项是：

According to the above criterion I should pass the last element foo.end()-1 to insert not foo.end(). Is my understanding correct? What happens if I pass foo.end()? Will it be a O(log n) insertion or a O(1) one. So, the options are:

// 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有一个不同的行为，如向量：

I ask because I'm writing a function that's templated on the container. I want to insert an element (that I know is the largest) to the end of whatever container is passed in. Using "Option A" above has a different behavior for a container like 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说一般为对数，如果t紧随p之后插入，则使用摊销常数。而C ++ 0x说一般为对数，但如果t在p之前插入t，则是摊销的常数。

As @Bo_Persson suggests, the problem here is that C++03 says "logarithmic in general, but amortized constant if t is inserted right after p." while C++0x says "logarithmic in general, but amortized constant if t is inserted right before p."

PS：我在Ubuntu 11.04上使用GCC 4.5 C ++ 0x支持启用。

PS: I'm using GCC 4.5 on Ubuntu 11.04 with C++0x support enabled.

编辑：我运行经验测试与C + + 0x支持启用和禁用和将结果发布到答案。基本上，结论是，提供 end（）作为插入提示是一样好（并且显然更安全）。然而，这显然只是一个经验观察。

I ran empirical tests with C++0x support enabled and disabled and posted the results in an answer. Basically, the conclusion is that it's just as good (and is obviously safer) to provide end() as the insertion hint. However, that's obviously just an empirical observation. The standard, as stated, is still confusing on this aspect.

推荐答案

运行测试而不是通过库读取操作是作弊的规格？

Is it cheating to run a test instead of reading through library specifications?

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

For g++-4.4 -O2 for the integers 0 <= i < 5000000 my running times for standard insertion are

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

code> end（）作为提示

and my running times for insertion using end() as hint are

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

插入 （） - 1 是尽可能快，我可以告诉，但使用更麻烦，因为 end（） - 1 是一个非法操作（必须使用 operator - （）），如果设置恰好为空，则会崩溃。

Insertion at end() - 1 is just as fast as far as I can tell, but it is more cumbersome to use because end() - 1 is an illegal operation (you have to use operator--()) and it crashes if the set happens to be empty.

#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);
    }
}

这篇关于C ++ 0x问题：将常量插入std :: set的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！