代码之家 › 专栏 › 技术社区 › Svend

关于比较器的C++模板问题

graph templates c++

Svend · 技术社区 · 15 年前

可能是一个非常新的C++问题。假设我有一个类vertex,它有几个属性和方法。我想把一堆顶点填充到一个队列中,并让它们按照顶点类的一个特殊属性排序(为school yes做一个基本的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 version 4.3.3(ubuntu4.3.3-5ubuntu4))的linux机器上测试这个。显然,我希望它把数字按顺序吐出来。

如何制作比较器,以便在进行比较时查看和比较vertex.cost?

3 回复 | 直到 15 年前

Drew Dormann 15 年前

代替 std::less<benchmark::vertex*> 以两个顶点指针作为参数并返回 true 如果第一个参数在第二个参数之前。

STD::少&低;基准::顶点*GT; 将比较这两个指针,所以您看到的结果显示了它们在内存中的顺序。

Alexey Malistov 15 年前

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;

luke 15 年前

额外的模板版亚历克赛·马利斯托夫的回答:

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