C++ vector's insert & push_back difference

Question

I want to know what are difference(s) between vector's push_back and insert functions.

Is there a structural difference(s)?

Is there a really big performance difference(s)?

Answer 1

The biggest difference is their functionality. push_back always puts a new element at the end of the vector and insert allows you to select new element's position. This impacts the performance. vector elements are moved in the memory only when it's necessary to increase it's length because too little memory was allocated for it. On the other hand insert forces to move all elements after the selected position of a new element. You simply have to make a place for it. This is why insert might often be less efficient than push_back.

Answer 2

The functions have different purposes. vector::insert allows you to insert an object at a specified position in the vector, whereas vector::push_back will just stick the object on the end. See the following example:

using namespace std;
vector<int> v = {1, 3, 4};
v.insert(next(begin(v)), 2);
v.push_back(5);
// v now contains {1, 2, 3, 4, 5}

You can use insert to perform the same job as push_back with v.insert(v.end(), value).

Answer 3

Beside the fact, that push_back(x) does the same as insert(x, end()) (maybe with slightly better performance), there are several important thing to know about these functions:

1. push_back exists only on BackInsertionSequence containers - so, for example, it doesn't exist on set. It couldn't because push_back() grants you that it will always add at the end.
2. Some containers can also satisfy FrontInsertionSequence and they have push_front. This is satisfied by deque, but not by vector.
3. The insert(x, ITERATOR) is from InsertionSequence, which is common for set and vector. This way you can use either set or vector as a target for multiple insertions. However, set has additionally insert(x), which does practically the same thing (this first insert in set means only to speed up searching for appropriate place by starting from a different iterator - a feature not used in this case).

Note about the last case that if you are going to add elements in the loop, then doing container.push_back(x) and container.insert(x, container.end()) will do effectively the same thing. However this won't be true if you get this container.end() first and then use it in the whole loop.

For example, you could risk the following code:

auto pe = v.end();
for (auto& s: a)
    v.insert(s, pe);

This will effectively copy whole a into v vector, in reverse order, and only if you are lucky enough to not get the vector reallocated for extension (you can prevent this by calling reserve() first); if you are not so lucky, you'll get so-called UndefinedBehavior(tm). Theoretically this isn't allowed because vector's iterators are considered invalidated every time a new element is added.

If you do it this way:

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

it will copy a at the end of v in the original order, and this doesn't carry a risk of iterator invalidation.

[EDIT] I made previously this code look this way, and it was a mistake because inserter actually maintains the validity and advancement of the iterator:

copy(a.begin(), a.end(), inserter(v, v.end());

So this code will also add all elements in the original order without any risk.

Answer 4

Since there's no actual performance data, I reluctantly wrote some code to produce it. Keep in mind that I wrote this code because I wondered "Should I push_back multiple single elements, or use insert?".

#include <iostream>
#include <vector>
#include <cassert>
#include <chrono>

using namespace std;

vector<float> pushBackTest()
{
    vector<float> v;
    for(int i =0;i<10000000;i++)
    {
        // Using a for-loop took 200ms more (in the output)
        v.push_back(0);
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);
        v.push_back(6);
        v.push_back(7);
        v.push_back(8);
        v.push_back(9);
    }
    return v;
}

vector<float> insertTest()
{
    vector<float> v;
    for(int i =0;i<10000000;i++)
    {
        v.insert(v.end(), {0,1,2,3,4,5,6,7,8,9});
    }
    return v;
}

int main()
{
    std::chrono::steady_clock::time_point start = chrono::steady_clock::now();
    vector<float> a = pushBackTest();
    cout<<"pushBackTest: "<<chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count()<<"ms"<<endl;
    start = std::chrono::steady_clock::now();
    vector<float> b = insertTest();
    cout<<"insertTest: "<<chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count()<<"ms"<<endl;
    assert(a==b);
    return 0;
}

Output:

pushBackTest: 5544ms
insertTest: 3402ms

Since curiosity killed my time, I run a similar test but adding a single number instead of multiple ones. So, the two new functions are:

vector<float> pushBackTest()
{
    vector<float> v;
    for(int i =0;i<10000000;i++)
    {

        v.push_back(1);

    }
    return v;
}

vector<float> insertTest()
{
    vector<float> v;
    for(int i =0;i<10000000;i++)
    {
        v.insert(v.end(), 1);
    }
    return v;
}

Output:

pushBackTest: 452ms
insertTest: 615ms

So, if you wanna add batch of elements, insert is faster, otherwise push_back it is. Also, keep in mind that push_back can only push... back, yeah.

Answer 5

I didn't see it in any of the comments above but it is important to know:

If we wish to add a new element to a given vector and the new size of the vector (including the new element) surpasses the current vector capacity it will cause an automatic reallocation of the allocated storage space. And Beacuse memory allocation is an action we wish to minimize it will increase the capacity both in push_back and insert in the same way (for a vector with n elemeny will add about n/2).

So in terms of memory efficiency it is safe to say, use what ever you like best. for example:

std::vector<int> test_Insert = { 1,2,3,4,5,6,7 };
std::vector<int> test_Push_Back = { 1,2,3,4,5,6,7 };

std::cout << test_Insert.capacity() << std::endl;
std::cout << test_Push_Back.capacity() << std::endl;

test_Insert.push_back(8);
test_Push_Back.insert(test_Push_Back.end(), 8);

std::cout << test_Insert.capacity() << std::endl;
std::cout << test_Push_Back.capacity() << std::endl;

This code will print:

7

7

10

10