插入前面的矢量

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

If one of the critical needs of your program is to insert elements at the begining of a container: then you should use a std::deque and not a std::vector. std::vector is only good at inserting elements at the end.

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

Answer 2

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

使用std :: deque,就是它的设计目的.

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向量,以便按顺序排列所有内容.这将具有线性复杂性而不是多项式,就像在前面插入时那样.