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

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

这是要求对于我的任务，我需要这些：

在边缘类中：

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

在图表类中：

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

我在声明优先级队列时遇到问题。细节：

如果我直接使用这些，边缘类会给我一个错误“必须有类的参数”，我知道我不能将两个指针重载到 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;
        }
    }
};

^ 我什至不确定将结构放入类中是否正确，另外，因为我不知道在 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 提问，如果我做错了什么，请告诉我。

您的实施要求bool operator()(Edge*, Edge*)作为常规member班级的Edge这是可能的，但很少这样做。

标准库算法的比较器有以下惯用风格：all其中必须提供正在处理的序列中所包含对象的严格弱排序：

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

此列表中的第五 (5) 个内容与他们的指示最接近trying要做，但它是never实施为operator(). It is possible作为以下成员做 (1)Edge，但要做到这一点Edge类型必须支持默认构造。稍后我将解释如何做到这一点。在上面列出的选项中，对于此特定情况，性能（内联的可能性）和实现简便性的最佳候选者是（1）和（6）。如果您的队列实际持有Edge objects而不是Edge pointers(3) 将是一个自然的选择并且提供不错的性能。

有序容器和容器适配器（如优先级队列）的比较器的要点是比较其中保存的两个项目是否符合严格弱序。如果你不知道那是什么，看到这个链接。在实施中，归结为：如果，并且仅当 x < y return true，否则返回false。这意味着必须执行以下规定：

• x < x总是返回false
• if x < y回报true, then y < x must return false
• if both x < y and y < x返回 false，则x is 相等的 to 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;
};

老实说，这是对共享智能指针的使用的尖叫，但我把它留给你了。上面的代码很有可能在实现优先级队列逻辑的标准库算法中的整个使用位置内联比较器，因此考虑到指针容器的约束，这样的性能将很有可能达到最佳。

完成分配的要求

This can完全在课堂上完成Edge，因为它毕竟只是一个类类型。作为优先级队列适配器的模板参数传递的第三种类型公开了bool operator()，没有什么可以阻止你只是做一个例子Edge为你做那件事。这很奇怪，但它仍然可以通过一些修改来工作：

首先，移动bool operator()(const Edge*, const Edge*) const to the 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;
};

This is 极不寻常，但好处是允许函子直接访问成员变量Edge对象被比较，而不是通过公共 getter 和 setter 或必须与比较器成为好友。但它有一个缺点。没有什么可以阻止某人besides构建容器适配器Edge不指定来源、目的地和重量的对象。

简而言之，这样做没有什么好处，并且不正确使用使这项工作所需的代码可能会出现问题，为此，我会推荐第一个选项。

祝你好运