根据 这一页，如果我使用，我可以实现恒定时间插入
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() 作为插入提示。然而，这显然只是一个经验观察。如上所述，标准在这方面仍然令人困惑。
是否因为运行测试而不是阅读库规范而作弊？
对于 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
插入时间 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);
}
}
是否因为运行测试而不是阅读库规范而作弊？
对于 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
插入时间 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);
}
}
目前还不完全清楚 position 应该在插入点之前或之后指向。一些实现可以使用。
另一方面，如果你想为不同的容器使用不同的行为，为什么不为你的函数写两个重载，一个用于带有a的容器 push_back 功能和一个 std::set。
仅提供立即下降的迭代器 后 新的价值是有道理的。
那是因为在N个元素的集合中，有N + 1个可能的插入点。存在一个迭代器 后 高于任何预先存在的元素的值，但是 在所有元素之前的值之前没有迭代器。
跟随@antonakos的脚步，我正在扩展“作弊”解决方案并进行实证测试。我正在使用GCC 4.5进行优化（-02并考虑到C ++ 0x支持未启用以及何时启用时的情况 -std=c++0x。 40,000,000次插入的结果如下（显示系统时间，因为在这种情况下其他值不是特殊的）：
- 没有C ++ 0x支持
- 没有提示：26.6秒
- 提示
end()： 5.71秒
- 提示
--end()：5.84秒
- 启用C ++ 0x支持
- 没有提示：29.2秒
- 提示
end()： 5.34秒
- 提示
--end()：5.54秒
结论：GCC（启用或不启用C ++ 0x）在有效时插入 end() 作为插入提示提供。
我使用的代码基于@ antonakos：
#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);
}
void insert_hint_one_before_end(Set & xs, int x) {
xs.insert(--xs.end(), x);
}
int main() {
const int cnt = 40000000;
Set xs;
xs.insert(0);
for (int i = 1; i < cnt; i++) {
//insert_standard(xs, i);
//insert_hint_one_before_end(xs, i);
insert_hint_end(xs, i);
}
return 0;
}