std::priority_queue 中具有相同优先级的元素顺序

Question

我有以下代码：

#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;
}

每个元素具有相同的优先级，即Priority::LOW；

问题是，这些元素是如何放置在priority_queue中的？

每当我打印队列时，元素都在不同的位置。对我来说重要的是，如果有任何新元素出现 priority_queue 应该放在具有相同优先级的最后一个元素之后。

可以使用std::priority_queue实现还是必须自己包装？

Answer 1

std::priority_queue是在底层容器上使用std::make_heap, std::push_heap, and std::pop_heap实现的。这些操作不稳定，因此您无法保证元素会保持输入的顺序。

如果您需要它们保持输入的顺序，那么您可以做的一件事是编写您自己的对象，在向其中添加元素时在底层容器上使用 std::stable_sort。

Answer 2

如果你想要一个保证相等比较元素保持插入顺序的优先级队列，你需要自己写。

当然 std::priority_queue 不能保证这个插入顺序（如果它是作为堆实现的，那也不能保证）。

最简单的写 something 正确的方法可能是 map<key, list<val>>，但如果你需要它很快，这可能并不理想。手动 stable_sort 容器的建议具有更差的算法复杂性，但尽管如此，在大多数实际情况下可能表现更好。

Answer 3

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

满足堆属性的顺序。对于相等的元素，它是 any 顺序。

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.

您可以通过将订单作为优先事项的一部分来实现。但是要使其成为优先级的一部分，您需要首先使顺序成为元素的一部分。您可以使用运行计数器：

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

Answer 4

使用 `std::multiset` 或 `std::multimap`

只需使用 std::multiset 或 std::multimap（根据您的情况，multimap 看起来是正确的选择）。

https://en.cppreference.com/w/cpp/container/multimap

两者都是 staple 并且不会更改插入顺序（因为 c++11）。

std::priority_queue 中具有相同优先级的元素顺序

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

c++

queue

stl

priority-queue

使用 `std::multiset` 或 `std::multimap`

std::priority_queue 中具有相同优先级的元素顺序

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

c++

queue

stl

priority-queue

使用 std::multiset 或 std::multimap

使用 `std::multiset` 或 `std::multimap`