これは、C++ 11のstd :: vectorの内容を別のstd :: vectorの内容に移動する最も効率的な方法ですか？

Question

vector::insert()とstd::copy()のコマンドに余分な割り当てが必要と考えていました。しかし、もし私が新たに作成された要素ならば、swap()だと、これは、含まれている型がデフォルトのコンストラクタで割り当てられていない限り、割り当てを減らすと思います。

私の質問はタイプstd::stringのstd::vectorのために特別に実際にあるが、ここで述べたように、他のは、タイプが含まれているために働く必要があります。

template <typename T> 
void appendMove(std::vector<T>& dst, std::vector<T>& src) 
{ 
    dst.reserve(dst.size() + src.size()) 
    for(std::vector<T>::iterator it = src.begin(); it != src.end(); ++it) 
    { 
     dst.push_back(std::vector<T>()); 
     std::swap(dst.end()[-1], *it); 
    } 
} 

は私が修正アム？他に何かが足りないのですか？おそらくこれを行うにはもっと良い方法がありますか？

Answer 1

パフォーマンスに関する免責条項：プロファイリングを使用します。

パフォーマンスの考慮：

• push_backは、ベクターの容量が要素を挿入するのに十分である場合は、各コールをチェックする必要があります。コンパイラがループ内でのチェックを避けるほどスマートではない、つまりチェックする必要のあるすべてのループ反復に対して、それ以上の最適化を禁止する可能性もあります。
• reserveへの呼び出しがない場合、push_backは、移動中のベクトルの容量を調整する必要があります。ループ内で既に格納されている要素の移動につながる可能性があります。
• swapはmove若干異なっている：動きはGManNickGコメントで指摘したように、それは全範囲を取得するように最適化
• は、vector::insertは、挿入する前に必要なメモリを確保できた可能性が移動オブジェクトにあまり厳密な保証を、有します挿入される。これはおそらく、ランダムアクセスイテレータの特殊化を必要とするでしょう。それらのためのstd::differenceはO（1）にあります（すべての双方向イテレータに適用できますが、これは2回のループ反復よりも遅くなる可能性があります）。ではなく予約）。

私が考えることができる最も効率的な方法は、必要な容量を確保した後、容量チェックなし（push_back介し又はinsertを介してのいずれか）の要素を挿入することです。

スマートスタンダードライブラリの実装では、reserveをinsertの中に呼び出して、挿入時の容量をチェックすることはできません。私は完全にこれがcomply to the Standardだろうとは思わない。

あなたのライブラリーは、（コメントを参照）Andy Prowlのバージョン、十分にスマートで十分である場合：他に

dst.insert(dst.end(), 
      std::make_move_iterator(src.begin()), 
      std::make_move_iterator(src.end()) ); 

は、手動でinsertを呼び出す前にreserveへの呼び出しを記述することができますが、できません（私の知る限り）、インサート/要素を追加W/O内部容量チェック：

template < typename T, typename FwdIt > 
void append(FwdIt src_begin, FwdIt src_end, std::vector<T>& dst) 
{ 
    dst.reserve(dst.size() + std::distance(src_begin, src_end)); 
    // capacity checks might slow the loop inside `insert` down 
    dst.insert(dst.end(), src_begin, src_end); 
} 

例：

int main() 
{ 
    std::vector<int> dst = { 0, 1, 2 }; 
    std::vector<int> src = { 3, 42 }; 

    append(std::make_move_iterator(src.begin()), 
      std::make_move_iterator(src.end()), 
      dst); 
} 

別のイテレータ型のためappendを実装した方がよいかもしれません：

template < typename T, typename FwdIt > 
void append(FwdIt src_begin, FwdIt src_end, std::vector<T>& dst, 
      std::forward_iterator_tag) 
{ 
    // let the vector handle resizing 
    dst.insert(dst.end(), src_begin, src_end); 
} 

template < typename T, typename RAIt > 
void append(RAIt src_begin, RAIt src_end, std::vector<T>& dst, 
      std::random_access_iterator_tag) 
{ 
    dst.reserve(dst.size() + (src_end - src_begin)); 
    dst.insert(dst.end(), src_begin, src_end); 
} 

template < typename T, typename FwdIt > 
void append(FwdIt src_begin, FwdIt src_end, std::vector<T>& dst) 
{ 
    append(src_begin, src_end, dst, 
      typename std::iterator_traits<FwdIt>::iterator_category()); 
} 

---

パフォーマンスの問題は、ループ内の容量チェックのために発生した場合、デフォルト・構築するために必要な追加要素を試みることができます最初。

template < typename T, typename RAIt > 
void append(RAIt src_begin, RAIt src_end, std::vector<T>& dst, 
      std::random_access_iterator_tag) 
{ 
    auto src_size = src_end - src_begin; 

    dst.resize(dst.size() + src_size); 

    // copy is not required to invoke capacity checks 
    std::copy(src_begin, src_end, dst.end() - src_size); 
    // ^this^ should move with the example provided above 
} 

---

やすいラッパー：

template < typename T, typename FwdIt > 
void append_move(FwdIt src_begin, FwdIt src_end, std::vector<T>& dst) 
{ 
    append(std::make_move_iterator(src_begin), 
      std::make_move_iterator(src_end), 
      dst); 
}