Какая польза от std:: back_inserter над std:: inserter?

Насколько я могу судить, где-нибудь std::back_inserter работает в алгоритме STL, вы можете передать std::inserter, построенный с помощью .end(), вместо этого:

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

И, в отличие от back_inserter, насколько я могу судить, inserter работает для ЛЮБОГО контейнера STL!! Я успешно пробовал его для std::vector, std::list, std::map, std::unordered_map, прежде чем приходить сюда удивленно.

Я думал, что возможно, потому что push_back может быть быстрее для некоторых структур, чем insert(.end()), но я не уверен...

Это не похоже на std::list (имеет смысл):

// 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())

Но это немного для std::vector, хотя я не совсем уверен, почему?:

// 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())

Я предполагаю, что в векторе есть немного больше накладных расходов, вычисляющих, где итератор, а затем помещаем туда элемент vs только arr [count ++]. Может быть, это так?

Но все-таки основная причина?

Мой вопрос о последующих действиях, я думаю, гласит: "Можно ли написать std::inserter(container, container.end()) для шаблонной функции и ожидать, что она будет работать (почти) в любом контейнере STL?"

Я обновил номера после перехода на стандартный компилятор. Вот мои данные компилятора:
gcc версия 4.8.2 (Ubuntu 4.8.2-19ubuntu1)
Цель: x86_64-linux-gnu

Моя команда сборки:

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

Я думаю, этот вопрос задает вторую половину моего вопроса, а именно: "Могу ли я написать шаблонную функцию, которая использует std::inserter(container, container.end()), и ожидать, что она будет работать почти каждый контейнер?"

Ответ был "Да, для каждого контейнера, кроме std::forward_list". Но на основе обсуждения в комментариях ниже и в user2746253 ответ звучит так, как будто я должен знать, что это будет медленнее для std::vector, чем при использовании std::back_inserter...

Поэтому я мог бы специализировать мой шаблон для контейнеров, используя RandomAccessIterator вместо back_inserter. Имеет ли это смысл? Спасибо.

Ответ 1

Типы итераторов

std::back_inserter возвращает std::back_insert_iterator, который использует Container::push_back().
std::inserter возвращает std::insert_iterator, который использует Container::insert().

станд:: Список

Для списков std::list::push_back почти то же самое, что и std::list::insert. Единственное отличие заключается в том, что insert возвращает итератор в вставленный элемент.

бит/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);
  }

бит/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

Это выглядит немного иначе для std::vector. Нажмите "Назад", проверьте, требуется ли перераспределение, и если не просто помещает значение в правильное место.

бит/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);
  }

Но в std::vector::insert есть 3 дополнительные вещи, и это влияет на производительность. бит /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)
  }