C++ vector 的 insert & push_back 区别

C++ vector's insert & push_back difference

提问by totten

I want to know what are difference(s) between vector's push_backand insertfunctions.

我想知道vector'spush_back和insert函数之间有什么区别。

Is there a structural difference(s)?

是否存在结构差异？

Is there a really big performance difference(s)?

真的有很大的性能差异吗？

回答by Adam Sznajder

The biggest difference is their functionality. push_backalways puts a new element at the end of the vectorand insertallows you to select new element's position. This impacts the performance. vectorelements are moved in the memory only when it's necessary to increase it's length because too little memory was allocated for it. On the other hand insertforces to move all elements after the selected position of a new element. You simply have to make a place for it. This is why insertmight often be less efficient than push_back.

最大的区别是它们的功能。push_back总是在末尾放置一个新元素，vector并insert允许您选择新元素的位置。这会影响性能。vector元素仅在需要增加其长度时才在内存中移动，因为为其分配的内存太少。另一方面，insert强制在新元素的选定位置之后移动所有元素。你只需要为它腾出一个地方。这就是为什么insert效率通常低于push_back.

回答by Joseph Mansfield

The functions have different purposes. vector::insertallows you to insert an object at a specified position in the vector, whereas vector::push_backwill just stick the object on the end. See the following example:

这些功能有不同的用途。vector::insert允许您在 中的指定位置插入对象vector，而vector::push_back只会将对象粘在末尾。请参阅以下示例：

using namespace std;
vector<int> v = {1, 3, 4};
v.insert(next(begin(v)), 2);
v.push_back(5);
// v now contains {1, 2, 3, 4, 5}

You can use insertto perform the same job as push_backwith v.insert(v.end(), value).

您可以使用insert作为执行相同的任务push_back有v.insert(v.end(), value)。

回答by Ethouris

Beside the fact, that push_back(x)does the same as insert(x, end())(maybe with slightly better performance), there are several important thing to know about these functions:

除了事实之外，这push_back(x)与insert(x, end())（可能性能稍好）相同，关于这些函数还有一些重要的事情需要了解：

1. push_backexists only on BackInsertionSequencecontainers - so, for example, it doesn't exist on set. It couldn't because push_back()grants you that it will always add at the end.
2. Some containers can also satisfy FrontInsertionSequenceand they have push_front. This is satisfied by deque, but not by vector.
3. The insert(x, ITERATOR)is from InsertionSequence, which is common for setand vector. This way you can use either setor vectoras a target for multiple insertions. However, sethas additionally insert(x), which does practically the same thing (this first insert in setmeans only to speed up searching for appropriate place by starting from a different iterator - a feature not used in this case).

1. push_back仅存在于BackInsertionSequence容器上 - 例如，它不存在于set. 它不能，因为push_back()授予您它总是会在最后添加。
2. 一些容器也可以满足，FrontInsertionSequence并且它们具有push_front. 这满足于deque，但不满足于vector。
3. 的insert(x, ITERATOR)是InsertionSequence，这是很常见的set和vector。通过这种方式，您可以使用set或vector作为多个插入的目标。然而，sethas 另外insert(x)，它实际上做了同样的事情（这第一个插入set意味着只是通过从不同的迭代器开始来加速搜索合适的位置 - 在这种情况下未使用的功能）。

Note about the last case that if you are going to add elements in the loop, then doing container.push_back(x)and container.insert(x, container.end())will do effectively the same thing. However this won't be true if you get this container.end()first and then use it in the whole loop.

请注意最后一种情况，如果您要在循环中添加元素，那么执行container.push_back(x)并将container.insert(x, container.end())有效地执行相同的操作。然而，如果你先得到这个container.end()然后在整个循环中使用它，这将不是真的。

For example, you could riskthe following code:

例如，您可能会冒着以下代码的风险：

auto pe = v.end();
for (auto& s: a)
    v.insert(pe, v);

This will effectively copy whole ainto vvector, in reverse order, and only if you are lucky enough to not get the vector reallocated for extension (you can prevent this by calling reserve()first); if you are not so lucky, you'll get so-called UndefinedBehavior(tm). Theoretically this isn't allowed because vector's iterators are considered invalidated every time a new element is added.

这将有效地以相反的顺序将整个复制a到v向量中，并且仅当您足够幸运没有为扩展重新分配向量时（您可以通过reserve()先调用来防止这种情况）；如果你不是那么幸运，你会得到所谓的 UndefinedBehavior(tm)。理论上这是不允许的，因为每次添加新元素时，vector 的迭代器都被视为无效。

If you do it this way:

如果你这样做：

copy(a.begin(), a.end(), back_inserter(v);

it will copy aat the end of vin the original order, and this doesn't carry a risk of iterator invalidation.

它将在原始顺序a的末尾复制v，并且这不会带来迭代器失效的风险。

[EDIT] I made previously this code look this way, and it was a mistake because inserteractually maintains the validity and advancement of the iterator:

[编辑] 我以前让这段代码看起来像这样，这是一个错误，因为inserter实际上保持了迭代器的有效性和进步：

copy(a.begin(), a.end(), inserter(v, v.end());

So this code will also add all elements in the original order without any risk.

所以这段代码也会按照原先的顺序添加所有元素，没有任何风险。