15

std::priority_queue::top定数値を返します。ただし、優先キューから最上位の要素を削除し、別の場所で変更できるようにしたいと考えています。

priority_queue<SomeClass, vector<SomeClass>, SomeClassCompare > pQueue;
...
SomeClass *toBeModified = &(pQueue.top());
pQueue.pop();
toBeModified->setMember(3); // I would like to do this

優先度キューから一番上の要素を取得して (そしてキューから削除して)、必要に応じて変更する方法はありますか?

4

2 に答える 2

17

標準コンテナとコンテナ アダプタには、値のセマンティクスがあります。要素をキューにプッシュすると、コピーが作成されます。キューからオブジェクトを削除すると、そのオブジェクトは破棄されます。

top()が non- への参照を返したとしてもconst、キューから要素を削除するとすぐにその参照がぶら下がり、逆参照すると未定義の動作が発生します。

これは、std::priority_queueへの参照を返し、内部の順序付けを (意図的にまたは意図せずに) 混乱させないようにします。これは、やconstなどの連想コンテナーのキーが である理由とほとんど同じです。std::mapstd::setconst

代わりにできることは、によって返された値のコピーtop()を作成し、そのコピーを変更し、元の値を削除して、コピーをキューにプッシュすることです。

SomeClass obj = pQueue.top();
pQueue.pop();
obj.setMember(42);
pQueue.push(std::move(obj)); // You can move obj into the queue if you no more need it

一方、参照セマンティクスが必要な場合は、ポインターをキューにプッシュし (ユース ケースによってはスマート ポインターの可能性があります)、オブジェクトのプロパティに基づいてポインターを並べ替える適切なカスタム順序付け基準を提供する必要があります。彼らは指しています。

この場合、実行時にこれらのプロパティを変更して順序が異なるようにしないように注意してください。これは「コンテナの内部順序をいじる」と見なされ、未定義の動作が発生します。

于 2013-05-25T23:20:57.997 に答える
1

ここでは、値のセマンティクスが少なくとも役割を果たしているとは思いません。他のすべてのコンテナーは同じ値のセマンティクスを持ち、それらのほとんどすべてがfront()可変参照を提供します。

priority_queueが要素の変更を許可しない正確な理由が 1 つありtop()ます。これは、特定の要素がその現在の値に従って適切に修飾されているため、最上位にあるためです。プライオリティ キュー内の要素は、キューに設定された比較基準 (既定では演算子 <) に従って常に並べ替えられます。要素を変更すると、この条件が破棄され、ソートされた前提条件を使用するすべての操作で未定義の動作が発生する可能性があります。

つまり、 が含まれる要素の変更を許可しない理由は、 のおよび キーのpriority_queue場合とまったく同じです。setmap

専用の比較メソッドがあり、比較する値を含むフィールドを使用し、このフィールド以外のオブジェクトのコンテンツを変更することを理解しています。このようにして、ソート順の要件に違反しません。できることは 2 つあります。

  1. として変更する必要があるクラスのパーツを作成しますmutable。このようにして、これが const であっても、要素を取得しtop()て可変コンテンツを変更できます。

  2. を派生させて、独自のプライオリティ キュー クラスを作成しますstd::priority_queue。基礎となるコンテナへの参照を含む名前付きのフィールドがありますc（ただし、保護されたfront()セクションにあります）。基礎となるコンテナにはtop()、priority_queue. ただし、自分自身の安全constのために、リスクを最小限に抑えるために、キー フィールドを作成して、作成中に設定され、決して変更されないようにする必要があります。

ああ、この問題はポインターを使用しても解決できません。ポイントされたオブジェクトはまったく同じ定数になります。専用の比較メソッドが必要な場合は、オブジェクトの内容を調べる必要があり、この方法ではまったく同じ問題が発生するため、これらの「参照セマンティクス」もまったく役に立ちません。単純にポインター値を比較することに頼っている場合、これは役に立ちますが、これが 99% のケースの解決策になるとは思えません。

于 2015-10-01T10:28:22.827 に答える