How to make STL's priority_queue fixed-size

user_486578 0
Viewed 17055

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.

std stl c++
6 Answers

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.

user_59824640

The standard provides a set of primitive heap operations:

make_heap
sort_heap
push_heap
pop_heap

We can wrap it in a simple class which has a Command[10] or std::array<Command, 10> as its data member, or simply use the four functions above, in a lower-level fashion.

I personally recommend against wrapping it in a function, because you may want to adopt the ECS pattern and apply more possible operations on your commands, not only as a priority queue. As we know, if you use a priority queue there may be unnecessary copies or moves.

user_121852260

A bit tricky solution is not use std::priotity_queue, but std::array with size N+1, where only first N elements is a real queue. And instead of replacing element with lowest priority, you overwrite queue.back() with a new command. Than pop_queue(q.begin(), q.end()) adds new command to the queue.

Here is my code, that works:

int main() {
    std::array<int, 10> queue;
    queue.fill(500);
 
    for(int i = 0; i < 1000; i++)
    {
        queue.back() = rand() % 1000;
        pop_heap(queue.begin(), queue.end(), std::greater<int>());
        //print_queue(queue);
        assert(is_heap(queue.begin(), queue.end()-1, std::greater<int>()));
    }
}

The other thing is, whether your specification is what you really want. Do not forgot add an age into priority. If you don't, then after a million iteration you will have 10 element, with greatest priority. Does not matter when they were added to queue.

user_49510960
Related