优先级队列：使用一个对象来比较而不是类

开始于priority_queue s，我有这样的问题：我需要将元素存储在队列中，但是它们的排序方式不包含在元素中本身，而是不同的地方，就像在一个地图：优先级队列：使用一个对象来比较而不是类

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

本身没有intrensic顺序的元素。一个解决方法是定义一个包装这个东西的结构，但也许有人知道一个更聪明的方法。我也想过提供一个只在当前范围内有效的比较函数（它本身就是一个函数），但据我所知C++不支持这个函数，至少不需要像我需要的那样捕获局部变量。

来源

2012-02-08 wal-o-mat

从C++的角度来看，一个仿函数是覆盖（）操作的结构。你所问的代码是解决问题的完全合理的方法。 Dietmar的答案填入空格:) – Bukes 2012-02-08 20:50:44

'Comp'应该将地图作为构造函数中的const引用，存储const引用，并且运算符应该是const。 – 2012-02-08 20:53:21

我注意到cppreference.com没有记录带比较函数的构造函数。我想知道这是否是混淆的根源。 – 2012-02-08 20:54:58

std::priority_queue<T, Cont, Comp>将比较对象类型作为模板参数。传递对象引用的东西，你需要把它作为构造函数的参数：

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

来源

2012-02-08 20:50:44

可以使用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 ... 
}

来源

2012-02-08 20:57:47

感谢您清理我的代码，实际上它看起来不同于我在这里发布的内容，只是为了说明这一点我的函子需要参数通过:) – 2012-02-08 21:29:42

优先级队列：使用一个对象来比较而不是类

回答

相关问题