logo标签列表

C++中vector的insert和push_back有什么区别？

c++
88

我想知道vector的push_back和insert函数有哪些区别。

它们之间是否有结构上的差异？

它们之间是否存在非常大的性能差异？

7
insert 可以在任何位置执行，并支持其他功能，如范围操作。而 push_back 更方便用于在末尾添加元素。 - chris
5个回答
107

最大的区别在它们的功能上。push_back总是将新元素放在vector的末尾，而insert允许您选择新元素的位置。这会影响性能。vector元素仅在必须增加其长度时才移动到内存中，因为分配给它的内存太少了。另一方面，insert强制移动新元素选定位置后的所有元素，以为其腾出空间。这就是为什么insert可能比push_back效率低的原因。

11
另一方面，在末尾插入应该与 push_back 一样高效。 - Matthieu M.
21
几乎一样高效——代码需要确定insert实际上是否在end()，因此insert中将会有比push_back更多的分支，除非编译器能够发现它们实际上是不需要的。 - Yakk - Adam Nevraumont
6
人们选择使用C或C++是为了尽可能地压榨机器的每一个时钟周期，提高性能，有时甚至直接用汇编语言编写程序...每一个“if”都很重要，这不是Java。 - Cesar
1
@Cesar，选择编程语言的原因并不是因为它的速度问题... C++ 可能比 C 更快，反之亦然... 甚至在某些情况下，由于其运行时优化，Java 也可能比 C 更快。 - Tomer W
@TomerW 哦，那为什么？请启迪一下我。 - Cesar
显示剩余3条评论
34

这些函数有不同的目的。 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}

您可以使用insert执行与push_back相同的操作，使用v.insert(v.end(), value)。

10

除了 push_back(x) 可能会比 insert(x, end())（可能稍微更快）执行相同的操作之外，还有几个需要了解这些函数的重要事项：

  1. push_back 仅存在于 BackInsertionSequence 容器中 - 例如，它不存在于 set 中。因为 push_back() 保证始终在末尾添加。
  2. 一些容器也可以满足 FrontInsertionSequence，并且它们具有 push_front。这适用于 deque，但不适用于 vector。
  3. insert(x, ITERATOR) 来自于 InsertionSequence，这对于 set 和 vector 是共通的。这样你可以将 set 或 vector 作为多次插入的目标。但是，set 还有另一个 insert(x)，它实际上做了相同的事情（这里的第一个 insert 在 set 中只是从不同的迭代器开始加速搜索适当的位置的特性，在此情况下未使用）。

关于最后一种情况的说明是，如果您要在循环中添加元素，则执行 container.push_back(x) 和 container.insert(x, container.end()) 将实际上执行相同的操作。但是，如果您先获取此 container.end()，然后在整个循环中使用它，则这种情况不成立。

例如，您可能会冒险编写以下代码：

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

这将会把整个a逆序复制到v向量中，但只有在你运气好到没有因为扩展而重新分配向量（你可以通过先调用reserve()来防止这种情况）的时候才能生效；如果你运气不好，你将会遇到所谓的UndefinedBehavior(tm)。理论上，这是不允许的，因为每次添加新元素时，向量的迭代器都被认为无效。

如果你使用以下方式：

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

它将按照原始顺序在末尾复制a到v中，这不会导致迭代器失效的风险。

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

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

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

你对于 std::inserter 在类似 vector 的容器中存在“风险”的评论是不正确的。事实上，它的设计就是为了消除这些风险。没有反向排序，也没有未定义的行为。可以参考以下链接进行详细了解： https://www.fluentcpp.com/2017/10/06/stl-inserter-iterators-work/ - downhillFromHere
你说得对。我只是想让代码变短，而不是将其扩展成一个冗长的手动循环，所以这实际上是不正确的，因为 inserter 会维护迭代器的前进和有效性。我需要编辑帖子 :) - Ethouris
1

由于没有实际的性能数据，我不情愿地编写了一些代码来生成它。请记住，我编写这段代码是因为我想知道“我应该使用push_back多个单元素，还是使用insert？”。

#include <iostream>
#include <vector>
#include <cassert>
#include <chrono>

using namespace std;

vector<float> pushBackTest()
{
    vector<float> v;
    for(int i =0;i<10000000;i++)
    {
        // Using a for-loop took 200ms more (in the output)
        v.push_back(0);
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);
        v.push_back(6);
        v.push_back(7);
        v.push_back(8);
        v.push_back(9);
    }
    return v;
}

vector<float> insertTest()
{
    vector<float> v;
    for(int i =0;i<10000000;i++)
    {
        v.insert(v.end(), {0,1,2,3,4,5,6,7,8,9});
    }
    return v;
}

int main()
{
    std::chrono::steady_clock::time_point start = chrono::steady_clock::now();
    vector<float> a = pushBackTest();
    cout<<"pushBackTest: "<<chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count()<<"ms"<<endl;
    start = std::chrono::steady_clock::now();
    vector<float> b = insertTest();
    cout<<"insertTest: "<<chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count()<<"ms"<<endl;
    assert(a==b);
    return 0;
}

输出：

pushBackTest: 5544ms
insertTest: 3402ms

由于好奇心占据了我的时间，我进行了类似的测试，但是只添加了一个数字而不是多个数字。 因此，这两个新函数是：

vector<float> pushBackTest()
{
    vector<float> v;
    for(int i =0;i<10000000;i++)
    {

        v.push_back(1);

    }
    return v;
}

vector<float> insertTest()
{
    vector<float> v;
    for(int i =0;i<10000000;i++)
    {
        v.insert(v.end(), 1);
    }
    return v;
}

输出：

pushBackTest: 452ms
insertTest: 615ms

所以，如果你想添加一批元素，插入是更快的选择，否则就使用 push_back。同时要记住，push_back 只能将元素放在末尾。

1

我在之前的评论中没有看到，但这很重要：

如果我们想要添加一个新元素到给定的向量中，而新向量的大小（包括新元素）超过当前向量容量，它将导致自动重新分配已分配的存储空间。 由于内存分配是我们希望最小化的操作，因此它会在 push_back 和 insert 中以相同的方式增加容量（对于一个有 n 个元素的向量，将增加大约 n/2）。

因此从内存效率的角度来说，可以放心使用任何你喜欢的方法。 例如：

std::vector<int> test_Insert = { 1,2,3,4,5,6,7 };
std::vector<int> test_Push_Back = { 1,2,3,4,5,6,7 };

std::cout << test_Insert.capacity() << std::endl;
std::cout << test_Push_Back.capacity() << std::endl;

test_Insert.push_back(8);
test_Push_Back.insert(test_Push_Back.end(), 8);

std::cout << test_Insert.capacity() << std::endl;
std::cout << test_Push_Back.capacity() << std::endl;

这段代码将打印出以下内容：

7

7

10

10

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接