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.

Solution 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)
  }

Solution 2

Short answer is that std::insert_iterator allows you to insert at any position in the container:

//insert at index 2
auto it = std::inserter(v, v.begin() + 2);
*it = 4;

To accomplish this, std::vector must move existing elements after index 2 one place down in above example. This is O(n) operation unless you are inserting at the end because there is nothing else to move down. But still it needs to make relevant checks which causes O(1) perf penalty. For linked lists, you can insert at any place in O(1) time so no penalty there. The back_inserter always inserts at the end so no penalty there either.

Comments

[Trevor Boyd Smith]

I like the high-level/concise explanation which boils down to push_back() vs insert() --> this answers the question without getting bogged down AND is still sufficiently technical (i.e. non hand wavy).

[Romeo Valentin]

I don't think the three additional commands cause a big performance difference. What does make a difference though is that _M_insert_aux inserts at the end for push_back (i.e. it's just an append), but it inserts somewhere in the middle for insert, which causes all the following data to be pushed back.