9

良い一日！

彼の「効果的なSTL」で、スコット・マイヤーズは書いた

3 つ目は、反復子の順序付けられたコンテナー内の情報を使用して、リストの要素を配置したい位置に反復的に接合することです。ご覧のとおり、多くのオプションがあります。(項目 31、後編)

誰かが私にこのように説明できますか?

追加テキスト (コンテキストを理解するため):

アルゴリズム sort、stable_sort、partial_sort、および nth_element はランダム アクセス反復子を必要とするため、ベクトル、文字列、両端キュー、および配列にのみ適用できます。標準の連想コンテナで要素を並べ替えても意味がありません。そのようなコンテナは比較関数を使用して常に並べ替えられた状態を維持するためです。sort、stable_sort、partial_sort、または nth_element を使用したいが使用できない唯一のコンテナーは list であり、list はその sort メンバー関数を提供することで多少補償します。(興味深いことに、list::sort は安定した並べ替えを実行します。) リストを並べ替えたい場合はできますが、リスト内のオブジェクトに対して partial_sort または nth_element を使用したい場合は、間接的に行う必要があります。間接的なアプローチの 1 つは、ランダム アクセス イテレータを使用して要素をコンテナーにコピーし、目的のアルゴリズムをそれに適用することです。3 つ目は、反復子の順序付けられたコンテナー内の情報を使用して、リストの要素を配置したい位置に反復的に接合することです。ご覧のとおり、多くのオプションがあります。

4

5 に答える 5

3

I'm not sure what the confusion is but I suspect that it is what "splicing" refers to: the std::list<T> has an splice() member function (well, actually several overloads) which transfer nodes between lists. That is, you create a std::vector<std::list<T>::const_iterator> and apply the sorting algorithm (e.g. std::partial_sort()) to this. Then you create a new std::list<T> and use the splice() member with the iterators from the sorted vector to put the nodes into their correct order without moving the objects themselves.

This would look something like this:

std::vector<std::list<T>::const_iterator> tmp;
for (auto it(list.begin()), end(list.end()); it != end; ++it) {
    tmp.push_back(it);
}
some_sort_of(tmp);
std::list<T> result;
for (auto it(tmp.begin()), end(tmp.end()); it != end; ++it) {
    result.splice(result.end(), list, it);
}
于 2012-02-09T23:59:10.690 に答える
2

partial_sortリストをやりたいとしましょう。次のように、イテレータを使用してソートできる比較関数を提供することにより、イテレータをセット内のリストに格納できます。

struct iterator_less
{   
    bool operator() (std::list<int>::iterator lhs,
                 std::list<int>::iterator rhs) const
    {
        return (*lhs < *rhs);
    }
};
typedef std::multiset<
    std::list<int>::iterator, iterator_less
> iterator_set;

set に並べ替えを実行させることもできますが、一覧表示する反復子が含まれているため、 list::splice を使用してそれらを partial_sorted リストにスプライスできます。

std::list<int> unsorted, partialSorted;
unsorted.push_back(11);
unsorted.push_back(2);
unsorted.push_back(2);
unsorted.push_back(99);
unsorted.push_back(2);
unsorted.push_back(4);
unsorted.push_back(5);
unsorted.push_back(7);
unsorted.push_back(34);

    // First copy the iterators into the set
iterator_set itSet;
for( auto it = unsorted.begin(); it!=unsorted.end();++it)
{
    itSet.insert(it);
}
    // now if you want a partial_sort with the first 3 elements, iterate through the
    // set grabbing the first item in the set and then removing it.
int count = 3;
while(count--)
{
    iterator_set::iterator setTop = itSet.begin();
    partialSorted.splice(
        partialSorted.begin(),
        unsorted,
        *setTop);
    itSet.erase(setTop);
}

partialSorted.splice(
        partialSorted.end(),
        unsorted,
        unsorted.begin(),
        unsorted.end());
于 2012-02-10T00:53:14.170 に答える
1

注文されたコンテナはまたはのいずれstd::setかになりますstd::map。イテレータを使用するコンパレータを作成する場合は、を使用します。std::set<std::list<mydata>::iterator,comparator>それ以外の場合は、を使用できますstd::map<mydata,std::list<mydata>::iterator>。リストをからbegin()までend()調べて、イテレータをセットまたはマップに挿入します。これを使用すると、セットまたはマップを反復処理することにより、リスト内のアイテムにソートされた順序でアクセスできます。これは、自動的にソートされるためです。

于 2012-02-09T23:57:23.733 に答える
1

注文されたコンテナはstd::setとstd::multisetです。std::setBST を実装します。つまり、をクレートしてstd::set<std::list::iterators>から、固有の BST 構造を使用してソートを行う必要があるということです。開始するためのBSTのリンクを次に示します。

于 2012-02-10T02:22:09.053 に答える
0

編集ああ。「イテレータの順序付きコンテナ」に気付きました。これは、別のコンテナーにインデックスを作成することを意味します。

Boost Multi Index には、そのような例が多数あります (単一のコレクションがいくつかの異なる順序付け述語によってインデックス付けされ、インデックスはベース コンテナーへの「ポインター」(通常はイテレーター) のコレクションにすぎません)。

「3つ目は、イテレータの順序付けられたコンテナ内の情報を使用して、リストの要素を配置したい位置に繰り返しスプライスすることです」

その説明と一致すると私が思うことの 1 つは、 / /操作を行っstd::sort_heapたリスト/ベクトルを実行する場合です。std::make_heappush_heappop_heap

  • make_heap: シーケンスをヒープに変換します
  • sort_heap: ヒープをソートする
  • push_heap: 要素をヒープに挿入します
  • pop_heap : ヒープから最上位の要素を削除します

ヒープは、シーケンス内の要素の編成であり、挿入/削除の下でコレクションを既知の順序で維持することを (比較的) 効率的にします。順序は暗黙的 (連続した配列に格納された再帰的に定義されたバイナリ ツリーのように) であり、(非常に効率的な)アルゴリズムを実行することで、対応する適切に並べ替えられたシーケンスに変換できます。sort_heap

于 2012-02-09T23:50:04.447 に答える