有关比较器的C++模板化问题

Question

可能是一个非常新的C++问题。说我有一个类，顶点，有几个属性和方法。我想将一堆顶点插入队列中，并通过顶点类上的特殊属性对它们进行排序（对于学校是，执行基本的Dijkstra图算法）。

但是我遇到了一些渗透C++语法的问题。这里是我的代码（顶点不显示，但非常简单）。

typedef std::priority_queue<benchmark::vertex*, 
        std::vector<benchmark::vertex*>, 
        std::less<benchmark::vertex*> > q_type; 
q_type* q = new q_type(); 
benchmark::vertex* v1 = new benchmark::vertex(0.1,0.1); 
v1->cost = 4; 
benchmark::vertex* v2 = new benchmark::vertex(0.1,0.1); 
v2->cost = 8; 
benchmark::vertex* v3 = new benchmark::vertex(0.1,0.1); 
v3->cost = 6; 
benchmark::vertex* v4 = new benchmark::vertex(0.1,0.1); 
v4->cost = 10; 
benchmark::vertex* v5 = new benchmark::vertex(0.1,0.1); 
v5->cost = 2; 
q->push(v1); 
q->push(v2); 
q->push(v3); 
q->push(v4); 
q->push(v5); 
while (!q->empty()) { 
    std::cout << (*(q->top())).cost << std::endl; 
    q->pop(); 
} 

这将在本地机器上输出2,10,6,8,4。我正在用GCC（gcc版本4.3.3（Ubuntu 4.3.3-5ubuntu4））在Linux上测试它。很显然，我希望它能够按顺序吐出数字。

如何制作比较器，以便在比较时查看并比较vertex.cost？

Answer 1

将std::less<benchmark::vertex*>替换为以两个顶点指针作为参数的任何函数或函子，并且如果第一个参数属于第二个参数，则返回true。

std::less<benchmark::vertex*>是要比较两个指针，所以你看到的结果显示他们在内存中的顺序。

Answer 2

std::less<benchmark::vertex*>比较地址，而不是顶点

// Functor 
struct VertexLess 
{ 
    bool operator (const benchmark::vertex* left, const benchmark::vertex* right) const { 
     return left->id < right->id; 
    } 
}; 

typedef std::priority_queue<benchmark::vertex*,  
        std::vector<benchmark::vertex*>, 
        VertexLess > q_type; 

Answer 3

奖金额外templatey阿列克谢Malistov的回答版本：

template <class T, class M, const M T::*member> 
struct MemberGenericDereferenceLess 
{ 
    bool operator()(const T* lhs, const T* rhs) const 
    { 
     return ((*lhs).*member < (*rhs).*member); 
    } 
}; 

typedef std::priority_queue<benchmark::vertex*, 
          std::vector<benchmark::vertex*>, 
          MemberGenericDereferenceLess<benchmark::vertex, 
                 int, 
                 &benchmark::vertex::cost> > q_type; 

我曾计算过，你只需要在第一个和第三个模板参数，但我无法通过几分钟的黑客行为推断出class M。 （为读者练习）

这样做的好处是您可以快速更改您排序的成员。假设你vertex看起来像......

namespace benchmark 
{ 
    struct vertex 
    { 
     vertex(double a_, double b_) : a(a_), b(b_) {} 

     double a; 
     double b; 

     int cost; 
    }; 
} 

你可以让你的typedef排序上a或b：

typedef std::priority_queue<benchmark::vertex*, 
          std::vector<benchmark::vertex*>, 
          MemberGenericDereferenceLess<benchmark::vertex, 
                double, 
                &benchmark::vertex::a> > q_type; 

typedef std::priority_queue<benchmark::vertex*, 
          std::vector<benchmark::vertex*>, 
          MemberGenericDereferenceLess<benchmark::vertex, 
                double, 
                &benchmark::vertex::b> > q_type; 

这里是玩一个小驱动程序：

#include <iostream> 
#include <queue> 
#include <vector> 

namespace benchmark 
{ 
    struct vertex 
    { 
     vertex(double a_, double b_) : a(a_), b(b_) {} 

     double a; 
     double b; 

     int cost; 
    }; 
} 

template <class T, class M, const M T::*member> 
struct MemberGenericDereferenceLess 
{ 
    bool operator()(const T* lhs, const T* rhs) const 
    { 
     return ((*lhs).*member < (*rhs).*member); 
    } 
}; 

int main(int argc, char** argv) 
{ 
    typedef std::priority_queue<benchmark::vertex*, 
           std::vector<benchmark::vertex*>, 
           MemberGenericDereferenceLess<benchmark::vertex, 
                 int, 
                 &benchmark::vertex::cost> > q_type; 
    q_type q; 

    benchmark::vertex* v1 = new benchmark::vertex(0.1,0.1); 
    v1->cost = 4; 
    benchmark::vertex* v2 = new benchmark::vertex(0.1,0.1); 
    v2->cost = 8; 
    benchmark::vertex* v3 = new benchmark::vertex(0.1,0.1); 
    v3->cost = 6; 
    benchmark::vertex* v4 = new benchmark::vertex(0.1,0.1); 
    v4->cost = 10; 
    benchmark::vertex* v5 = new benchmark::vertex(0.1,0.1); 
    v5->cost = 2; 
    q.push(v1); 
    q.push(v2); 
    q.push(v3); 
    q.push(v4); 
    q.push(v5); 
    while(q.empty() == false) 
    { 
     std::cout << q.top()->cost << std::endl; 
     q.pop(); 
    } 

    // Clean up all of those new()s 
    delete v1; 
    delete v2; 
    delete v3; 
    delete v4; 
    delete v5; 

    std::cin.get(); 

    return 0; 
}