Iterator types
std::back_inserter
returnsstd::back_insert_iterator
that usesContainer::push_back()
.std::inserter
returnsstd::insert_iterator
that usesContainer::insert()
.
std::list
For lists std::list::push_back
is almost the same as std::list::insert
. The only difference is that insert returns iterator to inserted element.
bits/stl_list.h
void push_back(const value_type& __x)
{ this->_M_insert(end(), __x); }
void _M_insert(iterator __position, const value_type& __x)
{
_Node* __tmp = _M_create_node(__x);
__tmp->_M_hook(__position._M_node);
}
bits/list.tcc
template<typename _Tp, typename _Alloc> typename list<_Tp, _Alloc>::iterator
list<_Tp, _Alloc>::insert(iterator __position, const value_type& __x)
{
_Node* __tmp = _M_create_node(__x);
__tmp->_M_hook(__position._M_node);
return iterator(__tmp);
}
std::vector
It looks a little different for std::vector
. Push back checks if reallocation is needed, and if not just places value in correct place.
bits/stl_vector.h
void push_back(const value_type& __x)
{
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
{
_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
++this->_M_impl._M_finish;
}
else
_M_insert_aux(end(), __x);
}
But in std::vector::insert
there are 3 additional things done and it impacts performance.
bits/vector.tcc
template<typename _Tp, typename _Alloc> typename vector<_Tp, _Alloc>::iterator
vector<_Tp, _Alloc>::insert(iterator __position, const value_type& __x)
{
const size_type __n = __position - begin(); //(1)
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
&& __position == end()) //(2)
{
_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
++this->_M_impl._M_finish;
}
else
{
_M_insert_aux(__position, __x);
}
return iterator(this->_M_impl._M_start + __n); //(3)
}