C++ extend a vector with another vector

Question

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?

Nickolasnickolaus

Possible duplicate of Concatenating two std::vectors – Benzoin

Answer 1

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

Stanwood

I don't think there's a specialization of vector::insert for random access input iterators, so if performance matters, reserve() first. – Acciaccatura

Both VC++ 9.0 and GCC 4.3.2 determine iterator category internally, so you don't need to reserve. – Elijah

I know this is 8 years old, but is there any reason why you used distance() instead of simply v_prime.size()? – Baiel

@Baiel He was probably thinking about the more general case where you want to extend a vector by some range of elements. If you don't want to use all the elements from v_prime for example, you can just use this code and replace the iterators. – Vigilance

Answer 2

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

Flo

I think space still has to be reserve()-d to improve performance – Stanwood

+1, since the questioner asked for "simplest", not "fastest", so reserving space (while worth mentioning as an option) is unnecessary. – Adjunction

i think dmitry solution is both simplier and faster. upvote for this guy anway :) – Satiable

This answer should be discouraged. See Effective STL, Item 5: Too many STL programmers overuse copy, so the advice I just gave bears repeating: Almost all uses of copy where the destination range is specified using an insert iterator should be replaced with calls to range member functions. – Heliograph

@Chris, thus defeating the architecture of the STL. – Swint

Answer 3

There are multiple ways to achieve your target.

std::vector::insert

The vector can be extended by inserting new elements before the element at the specified position, effectively increasing the container size by the number of elements inserted. You can follow one of below approaches. The second version uses C++11 and it can be considered as a more generic answer, as b could also be an array.

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

Sometimes in usage it is a best practice to use reserve function before using std::vector::insert. std::vector::reserve function increases the capacity of the container to a value that's greater or equal to new_cap. If new_cap is greater than the current capacity(), new storage is allocated, otherwise the method does nothing.

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

Use of reserve function is not required but may be advisable. And it is best practive to use reserve if you are repeatedly inserting into a vector for which you know the final size, and that size is large. Otherwise, it is better to let the STL grow your vector as needed.

std::copy

std::copy is the second option that you can consider to achieve your target. This function copies the elements in the range (first,last) into the range beginning at result.

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

However use of std::copy is slower than use of std::vector::insert(), because std::copy() can't reserve enough space before-hand (it doesn't have access to the vector itself, only to an iterator which has), while std::vector::insert(), being a member function, can. Due to that std::copy is indeed slower than using std::vector::insert. Most of the people, over use std::copy without knowing this scenario.

boost::push_back

The third option that you can consider is the use of boost's push_back function.

boost::push_back(a, b);

Benzoin

Answer 4

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.

Collectivity

This answer could do better in explaining what's happening. Without manually reserving space, i.e., let the vector manage its space, the amortized cost of memory allocation is O(1). That is achieved by allocating memory in an exponential fashion. With manual reserve, the size of memory allocation is linear in this example (50 more elements in each allocation), resulting in an O(n) cost in memory allocation. Of course, O(1) is faster than O(n). – Aggrade

Answer 5

I needed two different variants of the extend function in C++14, where one supported move semantics for each element of the vector to be appended.

vec is your v, and ext is your v_prime.

/**
 * Extend a vector with elements, without destroying source one.
 */
template<typename T>
void vector_extend(std::vector<T> &vec, const std::vector<T> &ext) {
    vec.reserve(vec.size() + ext.size());
    vec.insert(std::end(vec), std::begin(ext), std::end(ext));
}

/**
 * Extend a vector with elements with move semantics.
 */
template<typename T>
void vector_extend(std::vector<T> &vec, std::vector<T> &&ext) {
    if (vec.empty()) {
        vec = std::move(ext);
    }
    else {
        vec.reserve(vec.size() + ext.size());
        std::move(std::begin(ext), std::end(ext), std::back_inserter(vec));
        ext.clear();
    }
}

Plumb

Answer 6

Using std::vector::insert;

A.reserve(A.size() + B.size());
A.insert(A.end(), B.begin(), B.end());

reserve() is optional, but using it helps to improve performance.

---

Convienent code generator to save precious seconds:

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/materialize/0.98.0/css/materialize.min.css"><script src="https://cdnjs.cloudflare.com/ajax/libs/materialize/0.98.0/js/materialize.min.js"></script><script src="https://cdn.jsdelivr.net/clipboard.js/1.6.0/clipboard.min.js"></script><script>function generateCode(){codeTemplate="{0}.reserve({0}.size() + {1}.size()); \n{0}.insert({0}.end(), {1}.begin(), {1}.end());",first=document.getElementById("1").value,second=document.getElementById("2").value,""==first&&(first="A"),""==second&&(second="B"),document.getElementById("c").innerHTML=String.format(codeTemplate,first,second)}String.format||(String.format=function(a){var b=Array.prototype.slice.call(arguments,1);return a.replace(/{(\d+)}/g,function(a,c){return"undefined"!=typeof b[c]?b[c]:a})});</script><div class="A" style="margin:3% 10% 1% 10%;"><label for="1">First vector name:</label><input id="1"/><br/><label for="1">Second vector name:</label><input id="2"/><div class="D"><a class="waves-effect waves-light btn red col" onclick="generateCode();" style="margin:0 0 4% 0;">Generate Code</a></div><textarea id="c" onclick="this.select()" style="border:none;height:auto;overflow: hidden;font-family:Consolas,Monaco;">A.reserve(A.size() + B.size());&#13;&#10;A.insert(A.end(), B.begin(), B.end());</textarea></div>

Chaperone

This is a copy of the most voted answer, https://mcmap.net/q/54354/-c-extend-a-vector-with-another-vector, 11 years later. Consider deleting it. – Transport

Was going to downvote, but I love the code generator, so +1 for originality instead. – Willyt

Answer 7

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.

Waybill