82

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?

1

7 Answers 7

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());
4
  • I don't think there's a specialization of vector::insert for random access input iterators, so if performance matters, reserve() first. Nov 24, 2008 at 5:04
  • 13
    Both VC++ 9.0 and GCC 4.3.2 determine iterator category internally, so you don't need to reserve. Jan 17, 2009 at 18:07
  • 27
    I know this is 8 years old, but is there any reason why you used distance() instead of simply v_prime.size()?
    – Holt
    Mar 4, 2016 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. Jan 17, 2019 at 23:20
27
copy(v_prime.begin(), v_prime.end(), back_inserter(v));
5
  • 1
    I think space still has to be reserve()-d to improve performance Nov 24, 2008 at 12:12
  • 4
    +1, since the questioner asked for "simplest", not "fastest", so reserving space (while worth mentioning as an option) is unnecessary. Nov 24, 2008 at 13:23
  • i think dmitry solution is both simplier and faster. upvote for this guy anway :) Nov 24, 2008 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. Nov 25, 2008 at 8:38
  • @Chris, thus defeating the architecture of the STL. Mar 24, 2009 at 0:43
13

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

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.

1
  • 1
    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, 2020 at 5:02
3

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

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>

2
  • 7
    This is a copy of the most voted answer, stackoverflow.com/a/313444/931303, 11 years later. Consider deleting it. Aug 2, 2018 at 20:17
  • Was going to downvote, but I love the code generator, so +1 for originality instead.
    – Don Hatch
    Nov 5, 2021 at 8:26
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.