相对于 std: : insert，std: : back_insert 有什么好处？

据我所知，在使用 STL 算法的任何地方，都可以传递一个用 .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)
目标: 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代替。这说得通吗？谢谢。

38046

小开

最佳答案

迭代器类型

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

列表

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

Bit/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);
}

Bit/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看起来有点不同。推回检查是否需要重新分配，如果不只是把价值放在正确的地方。

Bit/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件事情要做，它会影响性能。位/向量

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