9

楽しみのために、想像できる最も単純な並べ替えアルゴリズムを実装しました。

template<typename Iterator>
void treesort(Iterator begin, Iterator end)
{
    typedef typename std::iterator_traits<Iterator>::value_type element_type;

    // copy data into the tree
    std::multiset<element_type> tree(begin, end);

    // copy data out of the tree
    std::copy(tree.begin(), tree.end(), begin);
}

std::sort私のテストデータよりも約20倍遅いだけです:)

次に、移動セマンティクスを使用してパフォーマンスを改善したいと考えました。

template<typename Iterator>
void treesort(Iterator begin, Iterator end)
{
    typedef typename std::iterator_traits<Iterator>::value_type element_type;

    // move data into the tree
    std::multiset<element_type> tree(std::make_move_iterator(begin),
                                     std::make_move_iterator(end));
    // move data out of the tree
    std::move(tree.begin(), tree.end(), begin);
}

しかし、私が s をソートしているにもかかわらず、これはパフォーマンスに大きな影響を与えませんでしたstd::string。

次に、連想コンテナは外部から一定であることを思い出しました。つまり、ここでも同じことをstd::move行いstd::copyます:(データをツリーから移動する他の方法はありますか?

4

3 に答える 3

8

std::setそれらの要素へのアクセスのみstd::multisetを提供します。constつまり、セットから何かを移動することはできません。アイテムを移動する (またはまったく変更する) ことができれば、アイテムの並べ替え順序を変更することでセットを壊すことができます。したがって、C++11 では禁止されています。

したがって、アルゴリズムを使用しようとするとstd::move、コピー コンストラクターが呼び出されるだけです。

于 2013-01-20T21:11:09.287 に答える
4

multisetメソッド内の要素を実際にdestroyユーザーのコンテナーに戻すカスタム アロケーター (3 番目のテンプレート引数) を使用できると思います。次に、セット内の各要素を消去し、その破壊中に文字列を元のコンテナーに戻します。カスタムアロケータには2フェーズの構築が必要だと思います（メンバーとして保持するために関数に渡されたbeginイテレータを渡しますがtreesort、デフォルトで構築可能でなければならないため、構築中は渡しません）。

明らかにこれは奇妙でありpop、set/multiset にメソッドがない場合のばかげた回避策です。しかし、それは可能なはずです。

于 2013-01-20T21:35:59.993 に答える
0

私は Dave の気紛れなアロケーターのアイデアが好きです。このアロケーターは、それぞれの移動によって構築されたオブジェクトのソースを記憶し、破壊時に自動的に元に戻ります。

しかし、元の試みに近い答えは次のとおりです。

template<typename Iterator>
void treesort_mv(Iterator begin, Iterator end)
{
    typedef typename std::iterator_traits<Iterator>::value_type element_type;

    // move the elements to tmp storage
    std::vector<element_type> tmp(std::make_move_iterator(begin),
                                  std::make_move_iterator(end));
    // fill the tree with sorted references
    typedef std::reference_wrapper<element_type> element_ref;
    std::multiset<element_ref, std::less<element_type>> tree(tmp.begin(), tmp.end());

    // move data out of the vector, in sorted order
    std::move(tree.begin(), tree.end(), begin);
}

これにより参照がソートmultisetされるため、ツリーから移動する必要はありません。

ただし、元の範囲に戻ると、移動の割り当ては必ずしも自己割り当てに対して安全であるとは限らないため、最初にそれらをベクトルに移動して、元の範囲に再割り当てするときに自己割り当てが発生しないようにしました。

私のテストでは、これは元のバージョンよりもわずかに高速です。ベクトルとすべてのツリーノードを割り当てる必要があるため、おそらく効率が低下します。それと、コンパイラが COW 文字列を使用しているため、移動はコピーよりもはるかに高速ではありません。

于 2013-01-21T00:44:14.780 に答える