How to make STL's priority_queue fixed-size

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

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.

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.