使用指针和比较器C++的优先级队列

Question

我刚刚开始学习C++,有一半时间我不知道自己在做什么,花几个小时在Google上搜索并盲目地将代码放入我的项目中,这可能是一个基本问题,但我似乎无法忍受把它弄好.

这是我的任务要求,我需要这些:

在Edge类中:

public:
bool operator()(Edge*, Edge*)

在Graph类中:

private:
priority_queue<Edge*, vector<Edge*>, Edge> edges

我有问题声明priority_queue.细节:

如果我直接使用这些,边类会给我一个错误"必须有一个类的参数",我明白我不能将两个指针重载到bool运算符中,所以这就是我试过的:

在Edge.cpp中:

#include "Edge.h"
using namespace std;

Edge::Edge(Vertex* s, Vertex* d, double w)
{
    source = s;
    destination = d;
    weight = w;
}

double Edge::getWeight()
{
    return weight;
}

struct CompareWeight : public std::binary_function<Edge*, Edge*, bool>
{
    bool operator()(Edge* e1,Edge* e2)
    {
        double w1 = e1->getWeight();
        double w2 = e2->getWeight();

        if(w1>w2){
            return true;
        }
        else {
            return false;
        }
    }
};

^我甚至不确定将struct放在类中是否正确,另外在这个原因我不知道要放在我的Edge.h文件中.

在Edge.h中:

#include "Vertex.h"
class Edge
{
    public:
        Edge(Vertex*, Vertex*, double);
        double getWeight();
        friend struct CompareWeight; // ??? does not seems right
    private:
        Vertex* source;
        Vertex* destination;
        double weight;
}

至于Graph类是真正的问题所在,我甚至无法通过声明优先级队列而不会出现错误.

在Graph.h中

#include "Vertex.h"
#include "Edge.h"
#include <vector>
#include <queue>

class Graph
{
    public:
        ...

    private:
        priority_queue<Edge*, vector<Edge*>, Edge> edges
        // This give pointer error: no match for call to '(Edge) (Edge*&, Edge*&)'
}

第二次尝试:

// same as above
private:
    priority_queue<Edge*, vector<Edge*>, CompareWeight> edges
    // This give error: 'CompareWeight' not declared in this scope

我不知道为什么第一个错误,但第二个错误我清楚地理解它,但我不知道如何解决它,我应该在CompareWeight面前放一些东西？我尝试过很多东西,没什么用.

任何帮助将不胜感激!否则我可能会失败这个课程.第一次询问stackoverflow,如果我做错了请告诉我.

Answer 1

你实现的需求bool operator()(Edge*, Edge*)作为一个普通成员类Edge是可能的,但很少是它这样做的方式.

标准库算法的比较器有以下惯用语,所有这些都必须在正在处理的序列中提供所包含对象的严格弱排序:

1. 独立的仿函数类
2. 独立operator <超载
3. 对象类成员operator <重载.
4. 独立功能
5. 静态类函数
6. 静态类仿函数类
7. 其他几个......

这个列表中的第五个(5)是看起来像他们的指令试图做的最接近的事情,但它从未被实现为operator().这是可能做到(1)中的一员Edge,但这样做的Edge类型必须支持默认的建设.我会在一分钟内解释如何做到这一点.在上面列出的选项中,对于这种特定情况,性能(内联的可能性)和实现容易度的最佳候选者是(1)和(6).如果你的队列持有实际的Edge 对象而不是Edge 指针(3)将是一个自然的适合,并提供良好的性能.

有序容器和容器适配器(如优先级队列)的比较器的要点是比较两个符合严格弱顺序的项目.如果您不知道那是什么,请参阅此链接.在实现中,它归结为:if,且仅当 x < y返回true时,否则返回false.这意味着必须强制执行以下操作:

• x < x总是返回false
• 如果x < y返回true,则y < x 必须返回false
• 如果两个x < y和y < x返回false,那么x就是等同于y

意外编码一个比较器不遵守这些规则是一个常见的错误.防范这一点.

无论如何,我离题了.根据您的类定义并使用上面列表中的(1),正确执行此操作的一种方法是:

班级边缘

class Edge
{
public:
    Edge(Vertex* src, Vertex* dst, double w)
        : source(src), destination(dst), weight(w)
    {
    };

    // note: const-ness
    double getWeight() const { return weight; }

    Vertex const* getSource() const { return source; }
    Vertex* getSource() { return source; }

    Vertex const* getDestination() const { return destination; }
    Vertex* getDestination() { return destination; }

private:
    Vertex* source;
    Vertex* destination;
    double weight;
};

CmpEdgePtrs类

struct CmpEdgePtrs
{
    bool operator()(const Edge* lhs, const Edge* rhs) const
    {
        return lhs->getWeight() < rhs->getWeight();
    }
};

类图

class Graph
{
    // rest of class stuff

private:
    priority_queue<Edge*, vector<Edge*>, CmpEdgePtrs> edges;
};

老实说,这是使用共享智能指针的尖叫,但我留给你.上面的代码非常强大,可以在实现优先级队列逻辑的标准库算法中的整个使用位置内嵌比较器,因此,鉴于指针容器的约束,性能将很有可能达到最优.

履行指定要求

这可以完全在类中完成Edge,因为它毕竟只是一个类类型.作为优先级队列适配器的模板参数传递的第三种类型是暴露的东西,bool operator()没有什么能阻止你只Edge为你做一个实例.这很奇怪,但通过几次修改,它将会毫不逊色:

首先,移动bool operator()(const Edge*, const Edge*) const到Edge类,声明为public.其次,提供默认构造函数Edge,因为在创建仿函数以执行比较时,优先级队列的内部算法将需要它.

class Edge
{
public:
    // regular parameterized construction
    Edge(Vertex* src, Vertex* dst, double w)
        : source(src), destination(dst), weight(w)
    {
    };

    // ADDED: allows parameterless initialization
    Edge() 
        : source(), designation(), weight() 
    {}

    // note: const-ness
    double getWeight() const { return weight; }

    Vertex const* getSource() const { return source; }
    Vertex* getSource() { return source; }

    Vertex const* getDestination() const { return destination; }
    Vertex* getDestination() { return destination; }

    // ADDED: used when an instance of `Edge` is used as comparator functor
    bool operator ()(const Edge* lhs, const Edge* rhs) const
    {
        return lhs->weight < rhs->weight;
    }

private:
    Vertex* source;
    Vertex* destination;
    double weight;
};


class Graph
{
    // rest of class stuff

private:
    // NOTE: uses Edge-type as the functor type that will
    //  deliver the comparison of Edge pointers.
    priority_queue<Edge*, vector<Edge*>, Edge> edges;
};

这是非常不寻常的,但其好处是允许函子直接访问Edge被比较对象的成员变量,而不是通过公共getter和setter或者不得不与比较器交朋友.但它有一个缺点.除了容器适配器之外,没有什么能阻止构造Edge对象而不指定源,目标和权重.

简而言之,这样做有什么好处,以及不正确使用代码所需的潜在问题,为此,我建议使用第一个选项.

祝你好运