C++ 在前面插入向量

Inserting into a vector at the front

提问by Tryer

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

Is the function declaration of the insert operator of the std::Vectorclass.

是std::Vector类的插入操作符的函数声明。

This function's return type is an iterator pointing to the inserted element. My question is, given this return type, what is the most efficient way (this is part of a larger program I am running where speed is of the essence, so I am looking for the mostcomputationally efficient way) of inserting at the beginning. Is it the following?

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

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

Or,

或者，

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

Essentially, in Code 2, is the parameter,

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

intvector.begin() 

"Costly" to evaluate computationally as compared to using the returned iterator in Code 1 or should both be equally cheap/costly?

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

回答by Stephane Rolland

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::dequeand not a std::vector. std::vectoris only good at inserting elements at the end.

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

Other containers have been introduced in C++11. I should start to find an updated graph with these new containers and insert it here.

C++11 中引入了其他容器。我应该开始寻找包含这些新容器的更新图并将其插入此处。

回答by Mark Ransom

The efficiency of obtaining the insertion point won't matter in the least - it will be dwarfed by the inefficiency of constantly shuffling the existing data up every time you do an insertion.

获取插入点的效率至少无关紧要 - 每次插入时不断将现有数据改组的低效率将使其相形见绌。

Use std::deque for this, that's what it was designed for.

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

回答by Happy Green Kid Naps

An old thread, but it showed up at a coworker's desk as the first search result for a Google query.

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

There is one alternative to using a deque that is worth considering:

有一种使用 deque 的替代方法值得考虑：

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

You still use a vector which is significantly more engineered than deque for performance. Also, swaps (which is what reverse uses) are quite efficient. On the other hand, the complexity, while still linear, is increased by 50%.

你仍然使用一个比双端队列更能提高性能的向量。此外，交换（这是反向使用的）非常有效。另一方面，复杂度虽然仍然是线性的，但增加了 50%。

As always, measure before you decide what to do.

与往常一样，在决定做什么之前先衡量一下。

回答by Mark B

Most likely dequeis the appropriate solution as suggested by others. But just for completeness, suppose that you need to do this front-insertion just once, that elsewhere in the program you don't need to do other operations on the front, and that otherwise vectorprovides the interface you need. If all of those are true, you could add the items with the very efficient push_backand then reversethe vector to get everything in order. That would have linear complexity rather than polynomial as it would when inserting at the front.

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

回答by Tim Rupe

If you're looking for a computationally efficient way of inserting at the front, then you probably want to use a deque instead of a vector.

如果您正在寻找一种在前面插入的计算效率高的方法，那么您可能想要使用双端队列而不是向量。

回答by Diego Sevilla

When you use a vector, you usually know the actual number of elements it is going to have. In this case, reserving the needed number of elements (100000 in the case you show) and filling them by using the []operator is the fastest way. If you really need an efficient insert at the front, you can use dequeor list, depending on your algorithms.

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

You may also consider inverting the logic of your algorithm and inserting at the end, that is usually faster for vectors.

您还可以考虑反转算法的逻辑并在最后插入，这对于向量来说通常更快。

回答by Hongseok Yoon

I think you should change the type of your container if you really want to insert data at the beginning. It's the reason why vector does not have push_front() member function.

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

回答by Marie Hoffmann

Intuitively, I agree with @Happy Green Kid Naps and ran a small test showing that for small sizes (1 << 10 elements of a primitive data type) it doesn't matter. For larger container sizes (1 << 20), however, std::dequeseems to be of higher performance than reversing an std::vector. So, benchmark before you decide. Another factor might be the element type of the container.

直觉上，我同意@Happy Green Kid Naps 并进行了一个小型测试，表明对于小尺寸（原始数据类型的 1 << 10 个元素）这无关紧要。但是，对于较大的容器大小 (1 << 20)，std::deque似乎比反转std::vector. 所以，在你决定之前进行基准测试。另一个因素可能是容器的元素类型。

• Test 1: push_front (a) 1<<10 or (b) 1<<20 uint64_t into std::deque
• Test 2: push_back (a) 1<<10 or (b) 1<<20 uint64_t into std::vectorfollowed by std::reverse

• 测试 1：push_front (a) 1<<10 或 (b) 1<<20 uint64_t 到std::deque
• 测试 2：push_back (a) 1<<10 或 (b) 1<<20 uint64_t 到std::vector后跟std::reverse

Results:

结果：

• Test 1 - deque (a) 19 μs
• Test 2 - vector (a) 19 μs
• Test 1 - deque (b) 6339 μs
• Test 2 - vector (b) 10588 μs

• 测试 1 - deque (a) 19 μs
• 测试 2 - 矢量 (a) 19 μs
• 测试 1 - 双端队列 (b) 6339 μs
• 测试 2 - 矢量 (b) 10588 μs