C++ std::back_inserter 比 std::inserter 有什么好处？

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

提问by NHDaly

As far as I can tell, anywhere std::back_inserterworks in an STL algorithm, you could pass an std::inserterconstructed with .end()instead:

据我所知，任何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()));

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

而且，不像back_inserter，据我所知inserter适用于任何 STL 容器！！我在std::vector, std::list, std::map,std::unordered_map之前尝试成功了，然后惊讶地来到这里。

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

我想可能是因为push_back某些结构可能比 更快insert(.end())，但我不确定......

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

情况似乎并非如此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())

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

但它对 略有影响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())

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?

我猜在一个向量中，找出迭代器在哪里然后在那里放置一个元素而不是 arr[count++] 会有更多的开销。也许是这样？

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?"

我猜我的后续问题是“可以std::inserter(container, container.end())为模板化函数编写代码并期望它适用于（几乎）任何 STL 容器吗？”

---

---

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

转移到标准编译器后，我更新了数字。这是我的编译器的详细信息：
gcc version 4.8.2 (Ubuntu 4.8.2-19ubuntu1)
目标：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?"

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

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::vectorthan using std::back_inserter...

答案是“是的，对于每个容器，除了std::forward_list.”。但是根据下面评论中的讨论和user2746253的回答，听起来我应该知道这std::vector比使用std::back_inserter...

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

因此，我可能想将我的模板专门用于使用RandomAccessIterators 的容器back_inserter。那有意义吗？谢谢。

回答by user2746253

Iterator types

迭代器类型

• std::back_inserterreturns std::back_insert_iteratorthat uses Container::push_back().
• std::inserterreturns std::insert_iteratorthat uses Container::insert().

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

std::list

标准::列表

For lists std::list::push_backis almost the same as std::list::insert. The only difference is that insert returns iterator to inserted element.

For 列表std::list::push_back几乎与std::list::insert. 唯一的区别是 insert 将迭代器返回到插入的元素。

bits/stl_list.h

位/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

位/列表.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.

看起来有点不同std::vector。推回检查是否需要重新分配，如果不只是将值放在正确的位置。

bits/stl_vector.h

位/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::insertthere are 3 additional things done and it impacts performance. bits/vector.tcc

但是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)
  }

回答by Shital Shah

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

简短的回答是std::insert_iterator允许您在容器中的任何位置插入：

//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_inserteralways inserts at the end so no penalty there either.

为此，std::vector 必须将上面示例中索引 2 之后的现有元素向下移动一位。这是O(n)操作，除非您在最后插入，因为没有其他东西可以向下移动。但仍然需要进行相关检查，这会导致性能O(1)下降。对于链表，您可以在任何O(1)时间插入，因此不会受到任何惩罚。在back_inserter总是在末尾插入所以没有处罚有两种。