В чем преимущество std::back inserter над std::inserter?

Question

В чем преимущество 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())

Я предполагаю, что в векторе есть немного больше накладных расходов, выясняя, где находится итератор, а затем помещая туда элемент против просто 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...

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

735 2

c++stl vector containers iterator

2 ответов:

Comments

Ничего не найдено.

user2746253 · Accepted Answer · 2014-10-15 00:49:41

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

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

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

Std:: list

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

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);
  }
Бит/список.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. Push back проверяет, требуется ли перераспределение, и если нет просто помещает ценность в правильное место.

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

ShitalShah · Accepted Answer · 2018-01-26 05:50:43

Короткий ответ заключается в том, что std::insert_iterator позволяет вставить в любую позицию контейнера:
//insert at index 2
auto it = std::inserter(v, v.begin() + 2);
*it = 4;
Для этого std:: vector должен переместить существующие элементы после индекса 2 на одно место вниз в приведенном выше примере. Это операция O(n), Если вы не вставляете в конце, потому что нет ничего другого, чтобы двигаться вниз. Но все же он должен сделать соответствующие проверки, которые вызывают O(1) штраф perf. Для связанных списков, вы можете вставить в любом месте в O(1) времени, так что никакого штрафа нет. back_inserter всегда вставляет в конце, так что никакого штрафа там тоже нет.