Insert or push_back to end of a std::vector?

Question

Is there any difference in performance between the two methods below to insert new elements to the end of a std::vector:

Method 1

std::vector<int> vec = { 1 };
vec.push_back(2);
vec.push_back(3);
vec.push_back(4);
vec.push_back(5);

Method 2

std::vector<int> vec = { 1 };
int arr[] = { 2,3,4,5 };
vec.insert(std::end(vec), std::begin(arr), std::end(arr));

Personally, I like method 2 because it is nice and concise and inserts all the new elements from an array in one go. But

• is there any difference in performance?
• After all, they do the same thing. Don't they?

Update

The reason why I am not initializing the vector with all the elements, to begin with, is that in my program I am adding the remaining elements based on a condition.

Answer 1

After all, they do the same thing. Don't they?

No. They are different. The first method using std::vector::push_back will undergo several reallocations compared to std::vector::insert.

The insert will internally allocate memory, according to the current std::vector::capacity before copying the range. See the following discussion for more:

Does std::vector::insert reserve by definition?

---

But is there any difference in performance?

Due to the reason explained above, the second method would show slight performance improvement. For instance, see the quick benck-mark below, using http://quick-bench.com:

See online bench-mark

Or write a test program to measure the performance(as @Some programmer dude mentioned in the comments). Following is a sample test program:

#include <iostream>
#include <chrono>
#include <algorithm>
#include <vector>
using namespace std::chrono;

class Timer final
{
private:
    time_point<high_resolution_clock> _startTime;

public:
    Timer() noexcept
        : _startTime{ high_resolution_clock::now() }
    {}
    ~Timer() noexcept {  Stop(); }
    void Stop() noexcept
    {
        const auto endTime = high_resolution_clock::now();
        const auto start = time_point_cast<microseconds>(_startTime).time_since_epoch();
        const auto end = time_point_cast<microseconds>(endTime).time_since_epoch();
        const auto durationTaken = end - start;
        const auto duration_ms = durationTaken * 0.001;
        std::cout << durationTaken.count() << "us (" << duration_ms.count() << "ms)\n";
    }
};
// Method 1: push_back
void push_back()
{
    std::cout << "push_backing:    ";
    Timer time{};
    for (auto i{ 0ULL }; i < 1000'000; ++i)
    {
        std::vector<int> vec = { 1 };
        vec.push_back(2);
        vec.push_back(3);
        vec.push_back(4);
        vec.push_back(5);
    }
}
// Method 2: insert_range
void insert_range()
{
    std::cout << "range-inserting: ";
    Timer time{};
    for (auto i{ 0ULL }; i < 1000'000; ++i)
    {
        std::vector<int> vec = { 1 };
        int arr[] = { 2,3,4,5 };
        vec.insert(std::end(vec), std::cbegin(arr), std::cend(arr));
    }
}

int main()
{
    push_back();
    insert_range();
    return 0;
}

release building with my system(MSVS2019:/Ox /std:c++17, AMD Ryzen 7 2700x_{(8-core, 3.70 Ghz)}, x64 Windows 10)

// Build - 1
push_backing:    285199us (285.199ms)
range-inserting: 103388us (103.388ms)

// Build - 2
push_backing:    280378us (280.378ms)
range-inserting: 104032us (104.032ms)

// Build - 3
push_backing:    281818us (281.818ms)
range-inserting: 102803us (102.803ms)

Which shows for the given scenario, std::vector::insert ing is about 2.7 times faster than std::vector::push_back.

See what other compilers(clang 8.0 and gcc 9.2) wants to say, according to their implementations: https://godbolt.org/z/DQrq51

Answer 2

There may be a difference between the two approaches if the vector needs to reallocate.

Your second method, calling the insert() member function once with an iterator range:

vec.insert(std::end(vec), std::begin(arr), std::end(arr));

would be able to provide the optimisation of allocating all the memory needed for the insertion of the elements in one blow since insert() is getting random access iterators, i.e., it takes constant time to know the size of the range, so the whole memory allocation can be done before copying the elements, and no reallocations during the call would follow.

Your first method, individual calls to the push_back() member function, may trigger several reallocations, depending on the number of elements to insert and the memory initially reserved for the vector.

Note that the optimisation explained above may not be available for forward or bidirectional iterators since it would take linear time in the size of the range to know the number of elements to be inserted. However, the time needed for multiple memory allocations likely dwarfs the time needed to calculate the length of the range for these cases, so probably they still implement this optimisation. For input iterators, this optimisation is not even possible since they are single-pass iterators.

Answer 3

The major contributing factor is going to be the re-allocations. vector has to make space for new elements.

Consider these 3 sinppets.

 //pushback
 std::vector<int> vec = {1};
 vec.push_back(2);
 vec.push_back(3);
 vec.push_back(4);
 vec.push_back(5);

 //insert
 std::vector<int> vec = {1};
 int arr[] = {2,3,4,5};
 vec.insert(std::end(vec), std::begin(arr), std::end(arr));


 //cosntruct
 std::vector<int> vec = {1,2,3,4,5};

To confirm the reallocations coming into picture, after adding a vec.reserve(5) in pushback and insert versions, we get the below results.

Answer 4

push_back inserts a single element, hence in the worst case you may encounter multiple reallocations.

For the sake of the example, consider the case where the initial capacity is 2 and increases by a factor of 2 on each reallocation. Then

std::vector<int> vec = { 1 }; 
vec.push_back(2);             
vec.push_back(3);                 // need to reallocate, capacity is 4
vec.push_back(4);                   
vec.push_back(5);                  // need to reallocate, capacity is 8

You can of course prevent unnecessary reallocations by calling

vec.reserve(num_elements_to_push);

Though, if you anyhow insert from an array, the more idomatic way is to use insert.