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());

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

原文由 cdleary 发布，翻译遵循 CC BY-SA 4.0 许可协议

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());

原文由 Dmitry Khalatov 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

仅使用以下语法：

 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 编译。

原文由 Ido Kessler 发布，翻译遵循 CC BY-SA 4.0 许可协议