How to make STL's priority_queue fixed-size

问题:

I am creating a simple game and I use std::priority_queue for giving commands to squads (every squad has a priority_queue<command>).

Every 20 seconds a bot analyses the situation and sends commands to the priority_queue.

How can I make the priority_queue fixed-size, for example, set the size to 10? The desired effect is that when the maximum is reached, if I add 2 new commands to the queue, 2 existing commands with the lowest priority are automatically removed.

回答1:

Wrap it in another class that will perform this operation for you. The Standard provides no such functionality on it's own.

回答2:

It's sneaky, but you should be able to override functionality of std::priority_queue to do what you need. This seems to work in some of the tests I've done:

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*);
};

What's happening here?

• Extend the std::priority_queue class
• Override the priority_queue::push() method, exchanging lowest item with new item
• Default constructor is private, no construction without size
• Restrict allocation on the heap, as STL containers have no virtual destructors.

To use:

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();
}

What's bad here?

• Well you can't safely create these queues on the heap, so big queues might be out of the question. 20 or so, as you mentioned should be fine on the stack anyway (depending on the object). I would probably avoid large queues because...
• I'm not sure of the performance hits here. priority_queue calls make_heap on the underlying container (std::vector by default). I'm not sure how often it's usually called, but we call it often if the queue is full. I think it may be called within priority_queue::push() aswell?
• Probably a heap of other things, so I welcome all constructive feedback and edits from readers :)

Hope this is useful, if not at least interesting.

回答3:

Aryabhatta's answer of another question applies to this question.

You use a max-heap.

Say you have an N element heap (implemented as an array) which contains the N smallest elements seen so far.

When an element comes in you check against the max (O(1) time), and reject if it is greater.

Iteration mentioned by several earlier comments is unnecessary.

回答4:

One idea is to create a min priority queue and use the size() method to only fill the priority queue to the required level. Something like this:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Compare {
    // priority queue is max heap by default, use compare
    // to make it minheap
    bool operator() (const int& a, const int& b) {
        return a>b;
    }
};

typedef priority_queue<int, vector<int>, Compare> pqSize;

void priorityQueueFixedSize(pqSize& pq, int size, vector<int>& vec) {
    for (int i=0;i<vec.size();i++) {
        if (pq.size() < size) {
            pq.push(vec[i]);
        } else {
            if (vec[i] > pq.top()) {
                pq.pop();
                pq.push(vec[i]);
            }
        }
    }
}

void printPQ(pqSize& pq) {
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
}

int main() {
    vector<int> vec(20,0);
    for (int i=0;i<vec.size();i++) {
        vec[i] = i;
    }
    pqSize pq;
    priorityQueueFixedSize(pq,10, vec);
    printPQ(pq);
}

This way only the maximum 10 elements will be held in the priority queue.