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?

Possible duplicate of [Concatenating two std::vectors](http://stackoverflow.com/questions/201718/concatenating-two-stdvectors) — Tharindu Kumara, Dec 12 '16 at 16:03

score 95 · Accepted Answer · edited Nov 11 '22 at 18:40

95

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

edited Nov 11 '22 at 18:40

A. Guy

500
1
3
10

answered Nov 24 '08 at 04:54

Dmitry Khalatov

4,313
3
33
39

I don't think there's a specialization of vector::insert for random access input iterators, so if performance matters, reserve() first. – Greg Rogers Nov 24 '08 at 05:04
13

Both VC++ 9.0 and GCC 4.3.2 determine iterator category internally, so you don't need to reserve. – Vadim Ferderer Jan 17 '09 at 18:07
25

I know this is 8 years old, but is there any reason why you used `distance()` instead of simply `v_prime.size()`? – Holt Mar 04 '16 at 13:43
1

@Holt 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. – Apollys supports Monica Jan 17 '19 at 23:20

score 27 · Answer 2 · answered Nov 24 '08 at 06:02

27

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

answered Nov 24 '08 at 06:02

CTT

16,901
6
41
37

1

I think space still has to be reserve()-d to improve performance – Dmitry Khalatov Nov 24 '08 at 12:12
4

+1, since the questioner asked for "simplest", not "fastest", so reserving space (while worth mentioning as an option) is unnecessary. – Steve Jessop Nov 24 '08 at 13:23
i think dmitry solution is both simplier and faster. upvote for this guy anway :) – Johannes Schaub - litb Nov 24 '08 at 16:44
1

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. – C. K. Young Nov 25 '08 at 08:38
@Chris, thus defeating the architecture of the STL. – Frank Krueger Mar 24 '09 at 00:43

score 12 · Answer 3 · answered Dec 12 '16 at 15:57

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

score 8 · Answer 4 · answered Sep 28 '20 at 12:37

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.

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). — Samuel Li, Nov 12 '20 at 05:02

TheJJ · Answer 5 · 2016-12-10T19:08:25.663

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

noɥʇʎԀʎzɐɹƆ · Answer 6 · 2017-02-11T16:39:42.500

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>

This is a copy of the most voted answer, https://stackoverflow.com/a/313444/931303, 11 years later. Consider deleting it. — Jorge Leitao, Aug 02 '18 at 20:17
Was going to downvote, but I love the code generator, so +1 for originality instead. — Don Hatch, Nov 05 '21 at 08:26

score 0 · Answer 7 · answered Jul 25 '22 at 05:02

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.

C++ extend a vector with another vector

7 Answers7

Linked

Related