C++ extend a vector with another vector

cdleary_3594 0
Viewed 49756

I'm a C/Python programmer in C++ land working with the STL for the first time.

In Python, extending a list with another list uses the .extend method:

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

I currently use this algorithmic approach to extend vectors in C++:

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

Is this the canonical way of extending vectors, or if there is a simpler way that I'm missing?

vector c++
7 Answers

From here

// 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_181740 
copy(v_prime.begin(), v_prime.end(), back_inserter(v));
CTT_401910

Use only the following syntax:

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

Reserve\Resize should not be used unless you know what you are doing.

Reserving can cause massive over head as it doesn't necessarily allocate an exponential increase in size, so each reserve can cause O(n) time.

This might not be extremely expensive if done only once, and might actually prove more time\memory efficient in such cases. On the other hand, if you continue to extend the array this way with relatively smaller arrays, this will prove extremely inefficient. The following example show a simple miss-usage that cause x10,000 increase in time

example:

#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))

Compiled with -O3 on gcc 17, intel i5.

user_71103670

Simple is better IMHO.

for (auto &val: v_prime)
  v.push_back(val);

When you need to extend the vector v multiple times, the simple code above is much faster than repeatedly reserving the space and inserting the other vector. This is because the process of reserving space is done automatically in an optimal way.

user_66567620
Related