带指针和比较器C的优先级队列

Question

我刚开始学习C语言，有一半的时间我不知道自己在做什么，花了好几个小时在谷歌上搜索，盲目地在我的项目中输入代码，这可能是一个基本的问题，但我似乎不能正确地理解它。

这是我作业的要求，我需要这些：

在“边”类中：

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

在Graph类中：

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

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

如果我直接使用这些，edge类会给我一个错误“必须有类的参数”，我知道我不能将两个指针重载到bool运算符中，所以我尝试了以下方法：

在边缘。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放在类中是否正确，加上这一点，我不知道将什么放在边缘中。h文件。

在边缘。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类，真正的问题是，我甚至无法在声明优先级队列时获得pass，而不会得到错误。

在图中. h

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

class Graph
{
    public:
        ...

    private:
        prhtml" target="_blank">iority_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

我不知道第一个错误的原因，但第二个错误我理解得很清楚，但我不知道如何修复它，我应该在CompareView前面放一些东西吗？我尝试了很多东西，但都没有成功。

任何帮助都将不胜感激！否则我很可能这门课不及格。第一次问stackoverflow，如果我做错了什么，请告诉我。

Answer 1

你缺少的是一份远期声明。在边缘。h、 只允许编写类顶点 单独在一行上。在这一行之后，C知道有这样一个类，Vertex*因此是指针（而不是乘法的前半部分）。

[edit]此前置声明替换#在Edge. h中包含Vertex. h。

Answer 2

您可以将bool操作符（）（Edge*，Edge*）作为类Edge的常规成员来实现，但很少这样做。

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

1. 独立函子类
2. 独立操作员

这个列表中的第五个（5）是最接近的东西，看起来像他们的指令试图做的事情，但是它从来没有实现为运算符（）。可以将（1）作为Edge的成员执行，但是要执行此操作，Edge类型必须支持默认构造。我稍后会解释如何做到这一点。在上面列出的选项中，对于这种特定情况，性能（内联的可能性）和实现难易度的最佳候选是（1）和（6）。如果您的队列包含实际的Edge对象，而不是Edge指针（3）将是一个自然的匹配，并提供良好的性能。

排序容器和容器适配器（如优先级队列）的比较器的要点是，根据严格的弱排序比较其中保存的两个项。如果您不知道这是什么，请参阅此链接。在实现中，它归结为：如果且仅当x

• x

无论如何，我离题了。根据您的类定义并使用上面列表中的（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;
};

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

满足指定要求

这可以完全在classEdge中完成，因为它毕竟只是一个类类型。作为优先级队列适配器的模板参数传递的第三种类型是公开bool运算符（）的东西，没有什么能阻止您让Edge的实例为您做这件事。这很奇怪，但它仍然可以通过几个修改来工作：

首先，将bool运算符（）（const Edge*， const Edge*）const移动到Edge类，声明为公共。其次，为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对象。

简言之，这样做没有什么好处，而且在不正确地使用实现此功能所需的代码方面存在潜在问题，为此，我建议使用第一种方法。

祝你好运