[解決済み] std::setとstd::priority_queueの違いについて

疑問点

どちらも std::priority_queue と std::set (そして std::multiset ) は、要素を保存し、順番にアクセスできるデータコンテナで、同じ挿入の複雑さを持つ O(log n) を使用する利点は何でしょうか？（または、どのような状況でどちらかが必要なのでしょうか？）

基礎となる構造が異なることは知っていますが、私はその実装の違いにはあまり興味がなく、比較のために彼らの

パフォーマンス と 適合性 を、様々な用途で使用することができます。

注意 私はセット内の重複禁止について知っています。そのため、私はまた std::multiset と全く同じ挙動をするので std::set と全く同じ動作をしますが、格納されているデータが等しい要素として比較できる場合に使用することができます。ですから、単一キー/複数キーの問題についてはコメントしないでください。

どのように解決するのですか？

優先キュー のみ にアクセスできるようになります。 1 すなわち、最も優先順位の高い項目を取得し、それを削除すると次に優先順位の高い項目が取得できる、というようになります。優先度キューは要素の重複も許しますので、セットというよりマルチセットに近いですね。[編集：@Tadeusz Kopec が指摘したように、ヒープの構築もヒープ内の項目数に対して線形であり、集合の構築は既に順序付けられたシーケンスから構築されない限り O(N log N) です（この場合も線形です）]。

集合はソートされた順序でのフルアクセスを可能にするので、たとえば、集合の真ん中のどこかで2つの要素を見つけ、それから一方から他方へと順番にたどることができます。