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

Question

据我所知,任何地方都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代替使用s的容器专用模板.那有意义吗？谢谢.

Answer 1

迭代器类型

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

的std ::名单

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

比特/ 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 ::矢量

它看起来有点不同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)
  }