构造向量的优先级队列

Question

我正在寻找向量优先级队列的简单 STL 实现。每个向量正好有 4 个元素。我想根据每个向量的第三个元素对我的优先级队列进行排序。具有最低第三个元素的向量应位于顶部（向量的最小优先级队列）。

如何在 C++ 中实现它？

另外，如果有人有默认优先级队列的实际 STL 实现，请提供链接。就像STL内部的官方实现一样。

Answer 1

您必须创建自己的比较器来比较priority_queue.

像这样的东西：

// How to compare elements
struct my_comparator
{
    // queue elements are vectors so we need to compare those
    bool operator()(std::vector<int> const& a, std::vector<int> const& b) const
    {
        // sanity checks
        assert(a.size() == 4);
        assert(b.size() == 4);

        // reverse sort puts the lowest value at the top    
        return a[2] > b[2];
    }
};

// for usability wrap this up in a type alias:
using my_priority_queue = std::priority_queue<std::vector<int>, std::vector<std::vector<int>>, my_comparator>;

int main()
{
    my_priority_queue mpq;

    mpq.push({1, 2, 1, 4});
    mpq.push({1, 2, 2, 4});
    mpq.push({1, 2, 3, 4});

    // etc ...
}