2

構造体の STL priority_queue があり、優先度が構造体の属性に基づいている場合、新しい順序が異なるように、構造体の 1 つの属性を変更すると、優先度キューは自分自身を再起動することを認識しますか? または、キューから削除して再度プッシュする必要がありますか? push() と pop() が呼び出されたときにソートが行われることをどこかで読みましたが、確認したいと思います。

4

3 に答える 3

1

priority_queue push()メンバー関数とメンバー関数は、範囲として渡された基になるコンテナーの完全な内容を使用して、ライブラリー関数とライブラリー関数pop()の動作に関して定義されます。push_heap()pop_heap()

これらの関数では、範囲 ( のコンテナー内の最後の項目を除いて、push_heap()追加される項目であるため) が「有効なヒープでなければならない」ことが必要です。コンテナーが有効なヒープではなくなるように、含まれている要素を変更すると、未定義の動作が発生します。

したがって、要素をそのように変更する必要がある場合は、要素を削除し、変更してから追加し直す必要があります。または、内容をいじってから呼び出しmake_heap()てヒープを再構築することもできます。

C++11 23.6.4.3 "priority_queue members"、25.4.6.1 "push_heap"、および 25.4.6.2 "pop_heap" を参照してください。

于 2013-05-29T06:14:03.497 に答える
0

正しい方法で並べ替えられていないことは間違いありません。少なくとも、これは保証されていません。priority_queue の push() と pop() は、基になるヒープ構造の std::push_heap() と std::pop_heap() を呼び出すだけです。

の効果

push(const value_type& x)

は

c.push_back(x);
push_heap(c.begin(), c.end(), comp);

C++03 標準 (23.2.3.2.2) に従います。ここで、cはキューの基になるコンテナーであり、順序付け関数はcompです。

push_heapの 1 つの要件は、

範囲 [first, last - 1] は有効なヒープです。

C++03 標準の 25.3.6.1 に従います。

priority_queue の既存の構造を変更すると、ヒープ構造が壊れ、make_heap を使用して再度有効なヒープ構造に再作成する必要があります。

また、priority_queue は、そのメソッドの 1 つへの呼び出しによって通知されないため、外部参照/ポインターを使用して要素を変更したことを知る方法がありません。

目的を達成するには、要素を削除して再度追加する必要があります。std::map のように、どの要素を削除して再度追加するかについてより柔軟な完全に異なるコンテナーを使用することもできます。

于 2013-05-29T06:27:15.857 に答える