插入前面的矢量

Question

iterator insert ( iterator position, const T& x );

是std::Vector类的insert运算符的函数声明。

此函数的返回类型是指向插入元素的迭代器。我的问题是，给定这种返回类型，最有效的方法是什么（这是我正在运行的一个更大的程序的一部分，其中速度是最重要的，所以我正在寻找最有效的计算方式）在开头插入。是以下吗？

//Code 1
vector<int> intvector;
vector<int>::iterator it;
it = myvector.begin();
for(int i = 1; i <= 100000; i++){
    it = intvector.insert(it,i);
}

要么，

//Code 2
vector<int> intvector;
for(int i = 1; i <= 100000; i++){
    intvector.insert(intvector.begin(),i);
}

基本上，在代码2中，是参数，

intvector.begin() 

与在代码1中使用返回的迭代器相比，计算评估的“成本”还是应该同样便宜/昂贵？

Answer 1

获得插入点的效率至少无关紧要 - 每次插入时不断改变现有数据的效率会相形见绌。

使用std :: deque，就是它的设计目的。

Answer 2

如果你的程序的一个关键需求是在容器的开头插入元素：那么你应该使用std::deque而不是std::vector。 std::vector只擅长在最后插入元素。

其他容器已在C ++ 11中引入。我应该开始使用这些新容器找到更新的图表并将其插入此处。

Answer 3

一个旧线程，但它出现在同事的桌面上作为Google查询的第一个搜索结果。

有一种方法可以使用值得考虑的双端队列：

std::vector<T> foo;
for (int i = 0; i < 100000; ++i)
  foo.push_back(T());
std::reverse( foo.begin(), foo.end() );

你仍然使用一个比deque更具工程性的矢量来提高性能。此外，交换（反向使用）是非常有效的。另一方面，复杂性虽然仍然是线性的，但却增加了50％。

一如既往，在决定做什么之前先测量一下。

Answer 4

如果你正在寻找一种计算效率高的插入方式，那么你可能想要使用deque而不是vector。

Answer 5

最有可能的deque是其他人建议的合适解决方案。但只是为了完整性，假设你需要只进行一次前插，在程序的其他地方你不需要在前面做其他操作，否则vector提供你需要的接口。如果所有这些都是真的，你可以使用非常有效的push_back添加项目，然后使用reverse向量来添加所有内容。这将具有线性复杂性而不是多项式，就像在前面插入时那样。

Answer 6

使用向量时，通常会知道它将具有的实际元素数。在这种情况下，保留所需数量的元素（在您显示的情况下为100000）并使用[]运算符填充它们是最快的方法。如果你真的需要在前面有效的插入，你可以使用deque或list，具体取决于你的算法。

您也可以考虑反转算法的逻辑并在最后插入，这通常对矢量更快。

Answer 7

如果您真的想在开头插入数据，我认为您应该更改容器的类型。这就是为什么vector没有push_front（）成员函数的原因。