Order of elements with the same priority in std::priority_queue

Question

I have following code:

#include <iostream>
#include <map>
#include <list>
#include <queue>
#include <memory>

enum class CommandType : uint8_t {
  Comm1,
  Comm2, 
  Comm3, 
  Comm4, 
  Comm5 
};

enum class Priority {
  HIGH,
  MEDIUM, 
  LOW
};

std::map<CommandType, Priority> priorities = {
    { CommandType::Comm1, Priority::LOW }, 
    { CommandType::Comm2, Priority::LOW }, 
    { CommandType::Comm3, Priority::LOW }, 
    { CommandType::Comm4, Priority::LOW }, 
    { CommandType::Comm5, Priority::LOW }
};

class QueueEntry 
{
 public:
    QueueEntry(CommandType type)
        : type_(type) {}
    CommandType getType() { return type_; }

private:
  CommandType type_;
};

struct QueueEntryPriorityComparator  {
    bool operator()(std::unique_ptr<QueueEntry>& entry1, std::unique_ptr<QueueEntry>& entry2) const
    {
        auto p1 = priorities.at(entry1->getType());
        auto p2 = priorities.at(entry2->getType());

        return p1 < p2;
    }
};

std::priority_queue<std::unique_ptr<QueueEntry>, std::deque<std::unique_ptr<QueueEntry>>, QueueEntryPriorityComparator> q;

void print()
{
    decltype(q) queueCopy;
    queueCopy.swap(q);

    while (!queueCopy.empty()) {
        auto& top = queueCopy.top();

        std::cout << "Command type: " << static_cast<uint32_t>(top->getType()) << std::endl;;

        q.emplace(std::make_unique<QueueEntry>(top->getType()));

        queueCopy.pop();
    }
}

int main()
{


    q.emplace(std::make_unique<QueueEntry>(CommandType::Comm1));
    q.emplace(std::make_unique<QueueEntry>(CommandType::Comm2));
    q.emplace(std::make_unique<QueueEntry>(CommandType::Comm3));
    q.emplace(std::make_unique<QueueEntry>(CommandType::Comm4));
    q.emplace(std::make_unique<QueueEntry>(CommandType::Comm5));

    print();

    std::cout << std::endl;

    print();

    std::cout << std::endl;

    print();



    return 0;
}

Each element has the same priority which is Priority::LOW;

The question is, how those elements are placed in priority_queue?

Whenever I print the queue, elements are in different positions. It is important to me that, if any new element comes to priority_queue should be placed after the last element with the same priority.

Can it be achieved by using std::priority_queue or I must wrap it on my own?

Answer 1

The question is, how those elements are placed in priority_queue?

In an order that satisfies the heap property. Which for equal elements is any order.

It is importatnt to me that, if any new element comes to priority_queue should be placed after the last element with the same priority.

You can achieve that by making the order part of the priority. But to make it part of the priorty, you need to first make the order part of the element. You can use a running counter:

struct OrderedQueueEntry {
    QueueEntry entry;
    int index;
};

struct OrderedQueueEntryPriorityComparator  {
    bool operator()(std::unique_ptr<OrderedQueueEntry>& left, std::unique_ptr<OrderedQueueEntry>& right) const
    {
        auto pl = priorities.at(left->entry.getType());
        auto pr = priorities.at(right->entry.getType());

        return pl == pr
            ? left->index < right->index;
            : pl < pr;
    }
};

int i = 0;
q.emplace(std::make_unique<OrderedQueueEntry>({CommandType::Comm1, i++}));
q.emplace(std::make_unique<OrderedQueueEntry>({CommandType::Comm2, i++}));
q.emplace(std::make_unique<OrderedQueueEntry>({CommandType::Comm3, i++}));
q.emplace(std::make_unique<OrderedQueueEntry>({CommandType::Comm4, i++}));
q.emplace(std::make_unique<OrderedQueueEntry>({CommandType::Comm5, i++}));