优先级队列:使用对象进行比较而不是类

Question

从priority_queues 开始,我遇到了这样的问题:我需要将元素存储在队列中,但是它们如何排序的标准不包含在元素本身中,而是在某个地方不同,例如在地图中:

std::map<element, value> element_values;
std::priority_queue<element> queue;

我现在需要的是这样的:

struct Comp
{
    std::map<...>& the_map;
    Cpmp(std::map<...> _map) : the_map(_map) {}

    bool operator() (element a, element b)
    {
        return the_map[a] < the_map[b];
    }
 }

 Comp comp(element_values);
 std::priority_queue<element, std::vector<element>, comp> queue; // does not work
 std::priority_queue<element, std::vector<element>, Comp> queue; // does work but I'd not be able to pass values to the constructor

元素本身没有任何内在的顺序.一个解决方法是定义一个包含这个东西的结构,但也许有人知道一个更聪明的方法.我还考虑过提供一个只在我当前范围内有效的比较函数(它本身就是一个函数),但据我所知C++不支持,至少不能像我需要的那样捕获局部变量.

Answer 1

将std::priority_queue<T, Cont, Comp>比较对象类型作为模板参数.要传递引用某些内容的对象,您需要将其作为构造函数参数传递:

std::priority_queue<element, std::vector<element>, Comp> queue(comp);

Answer 2

您可以使用类的比较器模板参数priority_queue.由于您的代码有几个问题,这里是一个整体清理版本:

#include <deque>
#include <queue>
#include <map>
#include <cassert>

typedef std::map<element, value> element_map;

struct Comp
{
    element_map const & m;

    Comp(element_map const & m_) : m(m_) { }

    bool operator()(element a, element b) const
    {
        element_map::const_iterator it1 = m.find(a), it2 = m.find(b);

        assert(it1 != m.end() && it2 != m.end());

        return it1->second < it2->second;
    }
};

typedef std::priority_queue<element, std::deque<element>, Comp> element_pq;

现在使用:

int main()
{
    element_map m;
    element_pq pq((Comp(m))); // ... sigh ...
}