[解決済み] std::back_inserter が std::inserter よりも優れている点は何ですか？

質問

私の知る限りでは、どこでも std::back_inserter が STL アルゴリズムで機能する場合、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 ." しかし、以下のコメントでの議論に基づき、また ユーザー2746253 の回答では、この方が遅くなることを認識した方が良さそうです。 std::vector を使用するよりも std::back_inserter ...

そのため、コンテナ用にテンプレートを特化して RandomAccessIterator を使用するように back_inserter の代わりに これは意味があるのでしょうか？ありがとうございます。

解決方法は？

イテレータの種類

• 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は挿入された要素へのイテレータを返すことです。

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

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

の場合は少し違って見えます。 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つが追加で行われ、パフォーマンスに影響を与えます。 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)
  }