C++使用另一个向量扩展向量

Question

我是C++领域的C/Python程序员,第一次使用STL.

在Python中,使用另一个列表扩展列表使用以下.extend方法:

>>> v = [1, 2, 3]
>>> v_prime = [4, 5, 6]
>>> v.extend(v_prime)
>>> print(v)
[1, 2, 3, 4, 5, 6]

我目前使用这种算法方法在C++中扩展向量:

v.resize(v.size() + v_prime.size());
copy(v_prime.begin(), v_prime.end(), v.rbegin());

这是扩展向量的规范方法,还是有一种我更缺失的简单方法？

Answer 1

从这里开始

// reserve() is optional - just to improve performance
v.reserve(v.size() + distance(v_prime.begin(),v_prime.end()));
v.insert(v.end(),v_prime.begin(),v_prime.end());

Answer 2

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

Answer 3

仅使用以下语法：

a.insert(a.end(), b.begin(), b.end());

除非您知道自己在做什么，否则不应使用 Reserve\Resize。

预留可能会导致巨大的开销，因为它不一定会分配指数级增长的大小，因此每个预留可能会导致 O(n) 时间。

如果只执行一次，这可能不会非常昂贵，并且在这种情况下实际上可能证明更高的时间\内存效率。另一方面，如果您继续用相对较小的数组以这种方式扩展数组，这将证明效率极低。以下示例显示了导致时间增加 x10,000 的简单误用

例子：

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

int main() {
    std::vector<int> a, b(50);
    auto t1 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 5e4; i++) {
        a.reserve(a.size() + b.size());      // line in question.
        a.insert(a.end(), b.begin(), b.end());
    }
    auto t2 = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>( t2 - t1 ).count();

    std::cout << 1.0 * duration / 1e9;
    return 0;
}

//run              time        complexity      speed up
//with reserve     114.558 s   O(N)            x1
//without reserve    0.012 s   O(N^2)          x10000 (~O(N/50))

在 gcc 17、intel i5 上使用 -O3 编译。

Answer 4

有多种方法可以实现目标。

std :: vector :: insert

可以通过在指定位置的元素之前插入新元素来扩展向量，从而通过插入的元素数量有效地增加容器大小。您可以采用以下方法之一。第二个版本使用C ++ 11，可以将其视为更通用的答案，因为b也可以是数组。

a.insert(a.end(), b.begin(), b.end());
a.insert(std::end(a), std::begin(b), std::end(b));

有时在使用中，最佳实践是在使用std :: vector :: insert之前使用保留功能。std :: vector :: reserve函数将容器的容量增加到一个大于或等于new_cap的值。如果new_cap大于当前的Capacity（），则分配新的存储，否则该方法不执行任何操作。

a.reserve(a.size() + distance(b.begin(), b.end()));

不需要使用保留功能，但建议使用。如果您反复插入知道最终大小且该大小很大的向量，则最好使用reserve。否则，最好让STL根据需要增大向量。

std :: copy

std :: copy是您可以考虑实现目标的第二个选项。此函数将范围（第一，最后）中的元素复制到从结果开始的范围中。

std::copy (b.begin(), b.end(), std::back_inserter(a));

但是，使用std :: copy的速度要比使用std :: vector :: insert（）的速度慢，因为std :: copy（）不能事先预留足够的空间（它无法访问向量本身，仅对具有）的迭代器有效，而std :: vector :: insert（）作为成员函数可以。由于该std :: copy确实比使用std :: vector :: insert慢。大多数人过度使用std :: copy而不了解这种情况。

boost :: push_back

您可以考虑的第三个选项是使用boost的push_back函数。

boost::push_back(a, b);