c++ - boost::mutable_queueで反復する方法

Question

優先度キーを増減できる優先度キューが必要です。したがって、ドキュメントが不足しているにもかかわらず、boost::mutable_queueは完璧に見えました。

問題は、キュー内のすべての要素に対してある時点で反復する必要があることです。どうやってやるの？

または、（できればブーストで）機能する他のデータ構造はありますか？

Answer 1

キューは反復用ではありません。キューの要点は、キューの先頭にある要素しか見ることができないということです。

繰り返したい場合std::setは、注文された、を使用することをお勧めします。要素を変更する場合は、要素を削除して、新しいキーで再挿入する必要があります。mySet.begin()（イテレータを返す）を使用して、最も優先度の高い要素を取得できます。

理想的には、ヒープを使用することをお勧めします。STLはヒープを作成するための関数を提供し、それがstd::priority_queue用途です。ただし、ヒープ内のキーにはインターフェイスがないため、キーを変更することはできません。

ヒープを自分で管理する場合は、それが可能です。ただし、文書化されていないstd::__adjust_heapからの関数を使用する必要があります。<heap.h>この関数が文書化されていない理由については、Alexander Stepanov （STLの発明者）とのこのインタビューですべて読むことができます。明らかにSTLが大きすぎるため、「削除」する必要がありました。これは、元の標準からのハッシュマップにも発生しました。

Answer 2

問題は、キュー内のすべての要素に対してある時点で反復する必要があることです。どうやってやるの？

これmutable_queueは単なるアダプタです。適切な下にあるコンテナを渡します。さらに、アダプターであると、使用可能なインターフェースが変更されることに注意してください。定義上、キューは通常、反復を許可しません。もしそうなら、このアダプターを持っている必要はありません。この制限については、SGISTLのドキュメントを参照してください。

または、（できればブーストで）機能する他のデータ構造はありますか？

目的に応じて、別のデータ構造を使用する必要がある場合があります。適切な選択は、データの保存方法とアクセス方法によって異なります。std::dequeコンテナを確認することをお勧めします。ただし、含まれているオブジェクトの状態の一部として優先度をエンコードする必要があります。