13

C++ STL priority_queueコンテナー アダプターを使用して、タイマー キューイング システムを実装したいと考えています。

私の問題は、タイマーを時々キャンセルしたいということですが、最上位のアイテムではないpriority_queue内のアイテムを簡単に削除できるインターフェイスがありません。

助言がありますか？。

ご協力ありがとうございました。

4

6 に答える 6

10

まったく同じシナリオが一度あり、次のことを行いました。

  • 私が保持していた構造には、std::priority_queueソートする時間と a へのインデックスのみが含まれていましたstd::vector<Handler>(私の場合Handlerは でしたがboost::function、インターフェイスまたは関数へのポインターである可能性もあります)
  • タイマーを追加するときは、ハンドラー1のベクターで空きインデックスを見つけ、そのインデックスにハンドラーを格納します。インデックスと時間をpriority_queueに格納します。キャンセルするトークンとしてインデックスをクライアントに返します
  • タイマーをキャンセルするには、追加時に受け取ったインデックスを渡します。そのインデックスのハンドラーをクリアします ( boost::functioncallclear()の場合、ポインターを使用する場合はゼロに設定します)
  • タイマーをコールバックするときは、優先キューからそのハンドラー インデックスを取得し、ハンドラー ベクトルをチェックします。その位置のハンドラーが empty()/NULL の場合、タイマーはキャンセルされています。そのハンドラ インデックスを free 2としてマークします。

1フリー インデックスをすばやく見つけるために、個別std::stackのインデックスを使用しました。タイマーを追加し、そのスタックが空である場合、ベクターの最後に追加します。それ以外の場合は、トップ インデックスをポップして使用します。

2フリーインデックススタックにインデックスをpushするときのポイントはこちら

特にタイマーコールバックでタイマーを追加またはキャンセルする必要がある場合は、全体がややこしく、エラーが発生しやすくなります。上記のキャンセル タイマー クラスへのリンクは次のとおりです。このコードはパブリック ドメインです。

于 2010-06-19T18:29:35.407 に答える
7

残念ながら、 STLpriority_queueはそのような機能を提供していません。独自のヒープ クラスを作成できます (それほど難しくありません)。std::xxx_heap次のような汚いトリックで関数を使用することもできます。

delete_heap(iterator to_delete, iterator heap_begin, iterator heap_end)
{
  to_delete->key = something that would compare less to everything; // make sure it gets to the top in the next step
  std::push_heap(heap_begin, to_delete+1);
  std::pop_heap(heap_begin, heap_end);
}

これでO(log n)削除できます。

于 2010-06-19T16:30:53.460 に答える
4

他のいくつかの回答が述べているにもかかわらずpriority_queue、コンテナは と呼ばれる保護されたメンバーとして公開されているため、 を含む任意の標準コンテナ アダプタの基になるコンテナにアクセスすることができますc。インターフェイスを継承して拡張するか、このpriority_queueようなダーティ トリックを使用して一時的に法線にアクセスすることができます。priority_queue

于 2010-06-19T17:12:06.813 に答える
3

私の問題は、タイマーを時々キャンセルしたいということですが、最上位のアイテムではないpriority_queue内のアイテムを簡単に削除できるインターフェイスがありません。

タイマーのキャンセルが頻繁に発生する場合は、別の構造を使用する必要があります。std::map もそれほど悪くはありませんが、delete_min のコストは高くなります。

タイマーのキャンセルがめったに起こらない場合は、要素を削除済みとしてマークする (および ::pop の間は無視する) とうまくいくかもしれません。

于 2010-06-19T17:08:54.157 に答える
2

STL の priority_queue コンテナーは、最上位のアイテムのみにアクセスできるように特別に設計されているため、最上位以外のアイテムを削除できるようにする必要がある場合は、使用する別のクラスを見つける必要があります。

于 2010-06-19T16:14:37.700 に答える
0

私は同じ要件を持っていました。コンテナーを自由に変更できる場合、この問題を解決できるのはstd::set (重複は許可されません) またはstd::multisetです。

どちらも順序付けられており、コンテナー サイズで要素対数を消去できます (詳細については、ドキュメントを参照してください)。マルチ セットの削除については、こちらを参照してください。

決定する前に、 std::set と std::priority_queueの違いを確認してください。

于 2016-11-12T10:50:52.057 に答える