std::back_inserter相对于std::inserter的好处是什么？

Question

据我所知，在STL算法适用std::back_inserter的任何地方，您都可以传递一个使用.end()构造的std::inserter：

就我所知，在STL算法中任何使用std::back_inserter的地方，您都可以使用使用.end()构造的std::inserter代替：

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 version 4.8.2 (Ubuntu 4.8.2-19ubuntu1)
Target: x86_64-linux-gnu

我的构建命令：

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

我认为这个问题问的是我的问题的后半部分，即“我能否编写一个使用std::inserter(container, container.end())并期望它适用于几乎每个容器的模板函数？”

那里的答案是“Yes, for every container except for std::forward_list.”。但根据下面评论中和user2746253的回答中的讨论，听起来我应该知道这对于std::vector来说会比使用std::back_inserter慢...

因此，我可能希望为使用RandomAccessIterator的容器专门特化我的模板，以使用back_inserter代替。这有意义吗？谢谢。

- NHDaly

---

back_inserter_iterator 调用 push_back，所以它当然不能适用于所有容器。另一方面，insert_iterator 调用 insert。这些操作的速度取决于你想要做什么。“适用于任何 STL 容器！”是错误的。也许C++ vector's insert & push_back difference会很有帮助。 - user3920237

例如，std::queue。 - Ben Voigt

这两个功能有不同的要求和保证。例如，std::vector<T> 的 inserter 需要 T 是可移动赋值的，而 back_inserter 则不需要。[Live example] (http://coliru.stacked-crooked.com/a/1b18eeb23c18b0e0) - dyp

如果你正在测量性能，请不要使用“-O0”。 - T.C.

@BenVoigt："std :: queue"不是容器，而是容器适配器; 例如，它甚至没有“begin（）”和“end（）”。 - musiphil

Answer 1

迭代器类型

• std::back_inserter 返回使用 Container::push_back() 的 std::back_insert_iterator。
• std::inserter 返回使用 Container::insert() 的 std::insert_iterator。

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个额外的操作，这会影响性能。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)
  }

- user2746253

---

我喜欢这个高水平/简明的解释，它归结为 push_back() 和 insert() 的区别--> 这个回答不会变得复杂难懂，同时还足够技术性（即不含模糊掉手的描述）。 - Trevor Boyd Smith

我认为这三个附加命令不会对性能造成很大影响。但是，真正会有影响的是 _M_insert_aux 在 push_back 时插入到末尾（即只是追加），而在 insert 时则在中间插入，导致后续所有数据都要被推回去。 - Romeo Valentin

Answer 2

简单来说，std::insert_iterator 允许你在容器的任何位置进行插入操作：

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

为了实现这一点，在上面的示例中，std::vector 必须将索引2之后的现有元素向下移动一个位置。除非您在末尾插入，否则这是一个 O(n) 操作，因为必须进行相关检查，这会导致 O(1) 的性能惩罚。对于链表，您可以在 O(1) 时间内在任何位置插入，因此没有惩罚。back_inserter 总是在末尾插入，因此也没有惩罚。

- Shital Shah