What's the benefit of std::back_inserter over std::inserter?

Question

As far as I can tell, anywhere std::back_inserter works in an STL algorithm, you could pass an std::inserter constructed with .end() instead:

std::copy(l.begin(), l.end(), std::back_inserter(dest_list));
std::copy(l.begin(), l.end(), std::inserter(dest_list, dest_list.end()));

AND, unlike back_inserter, as far as I can tell inserter works for ANY STL container!! I tried it successfully for std::vector, std::list, std::map, std::unordered_map before coming here surprised.

I thought that maybe it's because push_back could be faster for some structures than insert(.end()), but I'm not sure...

That doesn't seem to be the case for std::list (makes sense):

// Copying 10,000,000 element-list with std::copy. Did it twice w/ switched order just in case that matters.
Profiling complete (884.666 millis total run-time): inserter(.end())
Profiling complete (643.798 millis total run-time): back_inserter
Profiling complete (644.060 millis total run-time): back_inserter
Profiling complete (623.151 millis total run-time): inserter(.end())

But it does slightly for std::vector, though I'm not really sure why?:

// Copying 10,000,000 element-vector with std::copy.
Profiling complete (985.754 millis total run-time): inserter(.end())
Profiling complete (746.819 millis total run-time): back_inserter
Profiling complete (745.476 millis total run-time): back_inserter
Profiling complete (739.774 millis total run-time): inserter(.end())

I guess in a vector there is slightly more overhead figuring out where the iterator is and then putting an element there vs just arr[count++]. Maybe it's that?

But still, is that the main reason?

My followup question, I guess, is "Is it okay to write std::inserter(container, container.end()) for a templated function and expect it to work for (almost) any STL container?"

---

I updated the numbers after moving to a standard compiler. Here is my compiler's details:
gcc version 4.8.2 (Ubuntu 4.8.2-19ubuntu1)
Target: x86_64-linux-gnu

My build command:

g++ -O0 -std=c++11 algo_test.cc

---

I think this question asks the second half of my question, namely, "Can I write a templated function that uses std::inserter(container, container.end()) and expect it to work for almost every container?"

The answer there was "Yes, for every container except for std::forward_list." But based on the discussion in the comments below and in user2746253's answer, it sounds like I should be aware that this would be slower for std::vector than using std::back_inserter...

Therefore, I might want to specialize my template for containers using RandomAccessIterators to use back_inserter instead. Does that make sense? Thanks.

Answer 1

Iterator types

• std::back_inserter returns std::back_insert_iterator that uses Container::push_back().
• std::inserter returns std::insert_iterator that uses Container::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)
  }