10

vector::insert()andstd::copy()コマンドには追加の割り当てが必要だと考えていました。ただし、push_back()新しく作成された要素の場合swap()、含まれている型がデフォルトのコンストラクターで割り当てられていない限り、これにより割り当てが削減されると思います。

私の質問は、実際にstd::vectorは type の sに特化しstd::stringていますが、ここに記載されているように、含まれている他のタイプでも機能するはずです。

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

私は正しいですか？他に何か不足していますか？たぶん、これを行うためのより良い方法がありますか？

4

1 に答える 1

13

パフォーマンスに関する免責事項: プロファイリングを使用してください。

パフォーマンスに関する考慮事項:

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

私が考えることができる最も効率的な方法は、必要な容量を確保してから、容量チェックなしで要素を (push_backまたは 経由で) 挿入することです。insert

reserveスマートな標準ライブラリの実装は、内部への呼び出しを行い、insert挿入中に容量をチェックしない可能性があります。ただし、これがStandard に準拠するかどうかは完全にはわかりません。

ライブラリが十分にスマートな場合、Andy Prowlのバージョン (コメントを参照) で十分です。

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

reserveそれ以外の場合は、を呼び出す前に への呼び出しを手動で記述できinsertますが、(AFAIK) 内部容量チェックなしで要素を挿入/追加することはできません。

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

ループ内の容量チェックが原因でパフォーマンスの問題が発生した場合は、最初に必要な追加要素のデフォルト構築を試みることができます。それらが存在する場合 (つまり、構築されている場合)、非チェックoperator[]または単純なイテレーターを使用して、src オブジェクトを目的地に移動できます。

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 );
}
于 2013-05-16T23:43:35.483 に答える