Limited memory priority queue

I'm trying to implement a highly efficient limited memory priority queue. The interface is the same as a std::priority_queue.

Can anyone suggest any performance improvements on my attempt?

limited_queue.h

#include 
#include 

template
class LimitedPriorityQueue
{
public:
    LimitedPriorityQueue() {}

    void push(T item)
    {
        if (next != items.end()) {
            *next = item;
            ++next;
            std::push_heap(items.begin(), next);
        } else {
            std::sort_heap(items.begin(), items.end());
            if (items.front()  items;
    T* next = items.begin();
};

main.cpp

#include "limited_queue.h"

int main()
{
    LimitedPriorityQueue queue;

    for (int i = 20; i >= 0; --i) {
        queue.push(i);
    }

    while (!queue.empty()) {
        std::cout << queue.top() << std::endl;
        queue.pop();
    }
}

Also, I wasn't quite telling the truth when I said the interface is the same as a std::priority_queue; I'm missing an emplace. I'm not sure if this is possible using an underlying std::array?

Overall, it looks great. The code is clear and easy to follow, you leveraged the standard library well, and performance should be decent decent. There are however, a few things that could be improved.

It might be worth templating the comparison. All that you would have to change is passing an extra argument to make_heap, pop_head and push_heap. There's really not much of a reason to not template the comparator unless I'm missing something.

top() should return a const reference. No reason to make the user copy it unless they want.

You've allowed for move semantics by taking a value rather than const reference in push, but you haven't taken advantage of it the whole way through. Your assignments should be move assignments since you know you're done with the values. That lets you avoid a potentially expensive copy assignment.

Speaking of movement.... You are correct that can't meaningfully implement an emplace with an std::array. Since the elements are default constructed, there's no blank slot to construct in place in to. The best you could do would be a move assignment into an already constructed element which is the same performance as using push with move semantics.

What you could do, however, is use std::aligned_storage and emplace into that. It's basically a tool for getting unitialized memory that's ripe for having something constructed into it. From there, you can implement emplace just like you would in a non-stack allocated situation.

Unfortunately your other logic would get a bit more complicated, but not much. Only construction and destruction (i.e. push and pop) would change, and they would only need placement new and manual-destruction.

There's a pretty good example of what I'm talking about at on cppreference's std::aligned_storage page, though it unfortunately does not have an emplace example.

One last, highly subjective thing: I would probably name it BoundedPriorityQueue instead of LimitedPriorityQueue. Limited sounds like limited functionality to me, whereas bounded sounds like having a maximum size (like bounded buffer).

Also, it might be worth throwing in a bit of documentation. It's pretty obvious from the name and the template params, but someone could wonder what happens when it's full (example thrown, or chucking out the lowest element).

StackExchange Code Review Q#68126, answer score: 8