12

私は単純なゲームを作成しており、分隊にコマンドを与えるために使用していstd::priority_queueます (すべての分隊には があります)。priority_queue<command>

20 秒ごとにボットが状況を分析し、コマンドを に送信しますpriority_queue。

priority_queueたとえば、サイズを 10 に設定するなど、固定サイズを作成するにはどうすればよいですか? 望ましい効果は、最大数に達したときに、2 つの新しいコマンドをキューに追加すると、優先度が最も低い 2 つの既存のコマンドが自動的に削除されることです。

4

6 に答える 6

8

この操作を実行する別のクラスでラップします。標準は、それ自体ではそのような機能を提供しません。

于 2012-07-21T08:20:43.080 に答える
5

卑劣ですが、必要なことを行うために の機能をオーバーライドできるはずstd::priority_queueです。これは、私が行ったいくつかのテストでうまくいくようです:

template<typename T>
class fixed_priority_queue : public std::priority_queue<T> 
{
  public:
    fixed_priority_queue(unsigned int size) : fixed_size(size) {}
    void push(const T& x) 
    { 
      // If we've reached capacity, find the FIRST smallest object and replace
      // it if 'x' is larger
      if(this->size() == fixed_size)
      {
        // 'c' is the container used by priority_queue and is a protected member.
        auto beg = c.begin(); auto end = c.end();
        auto min = std::min_element(beg, end);
        if(x > *min)
        {
            *min = x;
            // Re-make the heap, since we may have just invalidated it.
            std::make_heap(beg, end);
        }
      }
      // Otherwise just push the new item.
      else          
      {
        priority_queue::push(x);
      }
    }
  private:
    fixed_priority_queue() {} // Construct with size only.
    const unsigned int fixed_size;
    // Prevent heap allocation
    void * operator new   (size_t);
    void * operator new[] (size_t);
    void   operator delete   (void *);
    void   operator delete[] (void*);
};

ここで何が起こっているのですか？

  • std::priority_queueクラスを拡張する
  • メソッドをオーバーライドし、priority_queue::push()最下位のアイテムを新しいアイテムに交換します
  • デフォルトのコンストラクターはプライベートで、サイズのない構築はありません
  • STL コンテナには仮想デストラクタがないため、ヒープの割り当てを制限します。

使用するには:

const unsigned int LIMIT = 20;
fixed_priority_queue<int> fooQueue(LIMIT);

// Testing.
for(int i=0; i<40; i++)
  fooQueue.push(rand());
for(int i=0; i<LIMIT; i++)
{
  printf("%i\n", fooQueue.top());
  fooQueue.pop();
}

ここで何が悪いのですか？

  • これらのキューをヒープ上に安全に作成することはできないため、大きなキューは問題外になる可能性があります。あなたが言及したように、とにかくスタック上で問題ないはずです（オブジェクトによって異なります）。私はおそらく大きなキューを避けるでしょう...
  • ここでのパフォーマンスのヒットはわかりません。priority_queue基礎となるコンテナーの呼び出しmake_heap(デフォルトでは std::vector)。通常どのくらいの頻度で呼び出されるかはわかりませんが、キューがいっぱいの場合は頻繁に呼び出します。内でも呼ばれると思いますpriority_queue::push()か？
  • おそらく他にもたくさんあるので、読者からの建設的なフィードバックと編集を歓迎します:)

少なくとも興味深いものではないにしても、これが役立つことを願っています。

于 2012-07-21T14:37:29.320 に答える
1

標準では、一連のプリミティブ ヒープ操作が提供されます。

make_heap
sort_heap
push_heap
pop_heap

Command[10]データメンバーとしてorを持つ単純なクラスでラップするかstd::array<Command, 10>、上記の 4 つの関数を低レベルの方法で使用することができます。

プライオリティ キューとしてだけでなく、ECS パターンを採用し、より多くの可能な操作をコマンドに適用したい場合があるため、個人的には関数でラップしないことをお勧めします。ご存知のように、プライオリティ キューを使用すると、不要なコピーや移動が発生する可能性があります。

于 2020-10-18T05:22:39.180 に答える