C++ vector's insert & push_back difference
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
.
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)
.
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:
push_back
exists only onBackInsertionSequence
containers - so, for example, it doesn't exist onset
. It couldn't becausepush_back()
grants you that it will always add at the end.- Some containers can also satisfy
FrontInsertionSequence
and they havepush_front
. This is satisfied bydeque
, but not byvector
. - The
insert(x, ITERATOR)
is fromInsertionSequence
, which is common forset
andvector
. This way you can use eitherset
orvector
as a target for multiple insertions. However,set
has additionallyinsert(x)
, which does practically the same thing (this first insert inset
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(pe, v);
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.