2

アルゴリズム設計のブラッシュアップと C++11 の学習を同時に行っているときに、次のようなヒープ ソートの実装を思い付きました。

template <typename It, typename Comp>
void heapSort(It begin, It end, Comp compFunc, std::random_access_iterator_tag)
{
    std::make_heap(begin, end, compFunc);
    std::sort_heap(begin, end, compFunc);
}

template <typename It, typename Comp, typename IterCat>
void heapSort(It begin, It end, Comp compFunc, IterCat)
{
    typedef typename It::value_type value_type;

    std::vector<value_type> randomAccessContainer;
    randomAccessContainer.reserve(std::distance(begin, end));
    std::move(begin, end, std::back_inserter(randomAccessContainer));

    heapSort(std::begin(randomAccessContainer), std::end(randomAccessContainer), compFunc, std::random_access_iterator_tag());
    std::move(std::begin(randomAccessContainer), std::end(randomAccessContainer), begin);
}

[begin, end)最初に から新しいコンテナに移動し、次にそのコンテナから に戻るのは標準的な C++[begin, end)ですか?

4

2 に答える 2

2

最初に [begin, end) から新しいコンテナに移動し、次にそのコンテナから [begin, end) に戻すのは標準的な C++ ですか?

私は当初、あなたの「標準」という言葉の使用に混乱し、質問を編集して、これが「合法」かどうかを尋ねるようにしました。その質問に対する答えは、「はい、完全に合法です」です。元の範囲内の要素が移動された後も、(指定されていなくても) 有効な状態のままです。

したがって、 の 2 番目の呼び出しはstd::move()要素を移動代入するだけであり、これらの要素の型には、事前条件なしで移動代入演算子が必要です。これが事実である限り、それで問題はないと思います。

しかし、あなたの質問を編集した後、これが「標準」、つまり「一般的な慣行」であるかどうかを実際に尋ねたかったのではないかと思い始めたので、元の文言を復元しました.

この質問に対する答えは「一部」です。通常は、以下を呼び出すのではなく、いくつかの移動反復子を使用して一時ベクトルを初期化しますstd::move。

std::vector<value_type> randomAccessContainer(
    std::make_move_iterator(begin),
    std::make_move_iterator(end)
    );

これとは別に、あなたの実装は私には正しいようです。

于 2013-03-09T16:18:17.873 に答える
0

いいえ、そうではありません。

ランダム アクセス コンテナーがまだ必要でない場合、どのようにそれをランダム アクセス コンテナーにする必要があるかがわかります。その場合は、次のことを優先しstd::make_move_iteratorます。

std::vector<value_type> randomAccessContainer(
     std::make_move_iterator(begin), 
     std::make_move_iterator(end));

それ以外の場合は、その場でソートする必要があります。(例外で「影響なし」が必要でない限り、多分)

于 2013-03-09T16:13:29.677 に答える