c++ - 带有指针和比较器C++的优先级队列

coder 2024-02-02 原文

我刚刚开始学习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前面放些东西吗？我尝试了很多事情，没有任何效果。

任何帮助将不胜感激!否则我可能只会不通过这门类(class)。
第一次在stackoverflow中询问，如果我做错了什么，请告诉我。

最佳答案

您可能需要将bool operator()(Edge*, Edge*)实现为Edge类的常规成员，但是很少这样做。

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

独立仿函数类

独立operator <重载

对象类成员operator <重载。

独立功能

静态类函数

静态类仿函数类

其他一些...

该列表上的第五(5)是最接近他们指令试图执行的操作的东西，但从未实现为operator()。可以将(1)作为Edge的成员来执行，但是这样做Edge类型必须支持默认构造。我将在稍后说明如何做到这一点。在上面列出的选项中，对于此特定情况，性能(内联的可能性)和实现难易程度的最佳候选者是(1)和(6)。如果您的队列中包含实际的Edge对象，而不是Edge指针(3)，那将是很自然的选择，并且可以提供不错的性能。

用于有序容器和容器适配器(如优先级队列)的比较器的作用是比较符合严格弱排序的两个容纳在其中的项目。如果您不知道那是什么，请see this link。在实现中，可以归结为:当且仅当x < y返回 true ，否则，才返回 false 。这意味着必须执行以下操作:

x < x始终返回错误

如果x < y返回 true ，则y < x 必须返回错误

如果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移到声明为public的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对象的成员变量，而不是通过公共(public) getter 和 setter 或与比较器成为 friend 。它有一个缺点。除了容器适配器之外，没有其他任何东西可以阻止在不指定源，目标和权重的情况下构造Edge对象。

简而言之，像这样进行操作几乎没有什么好处，而如果使用不正确的代码来完成这项工作可能会引起问题，为此，我建议您选择第一种方法。

祝你好运

关于c++ - 带有指针和比较器C++的优先级队列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23997104/

amp 43 code Edge strong c++pointers priority-queue comparator

有关c++ - 带有指针和比较器C++的优先级队列的更多相关文章

ruby - Ruby 的 Hash 在比较键时使用哪种相等性测试？ - 2
我有一个围绕一些对象的包装类，我想将这些对象用作散列中的键。包装对象和解包装对象应映射到相同的键。一个简单的例子是这样的:classAattr_reader:xdefinitialize(inner)@inner=innerenddefx;@inner.x;enddef==(other)@inner.x==other.xendenda=A.new(o)#oisjustanyobjectthatallowso.xb=A.new(o)h={a=>5}ph[a]#5ph[b]#nil,shouldbe5ph[o]#nil,shouldbe5我试过==、===、eq?并散列所有无济于事。
ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
ruby - 分布式事务和队列，ruby，erlang，scala - 2
我有一个涉及多台机器、消息队列和事务的问题。因此，例如用户点击网页，点击将消息发送到另一台机器，该机器将付款添加到用户的帐户。每秒可能有数千次点击。事务的所有方面都应该是容错的。我以前从未遇到过这样的事情，但一些阅读表明这是一个众所周知的问题。所以我的问题。我假设安全的方法是使用两阶段提交，但协议(protocol)是阻塞的，所以我不会获得所需的性能，我是否正确？我通常写Ruby，但似乎Redis之类的数据库和Rescue、RabbitMQ等消息队列系统对我的帮助不大——即使我实现某种两阶段提交，如果Redis崩溃，数据也会丢失，因为它本质上只是内存。所有这些让我开始关注erlang和
ruby - 使用 `+=` 和 `send` 方法 - 2
如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:
ruby-on-rails - 带有 Zeus 的 RSpec 3.1，我应该在 spec_helper 中要求 'rspec/rails' 吗？ - 2
使用rspec-rails3.0+，测试设置分为spec_helper和rails_helper我注意到生成的spec_helper不需要'rspec/rails'。这会导致zeus崩溃:spec_helper.rb:5:in`':undefinedmethod`configure'forRSpec:Module(NoMethodError)对thisissue最常见的回应是需要'rspec/rails'。但这是否会破坏仅使用spec_helper拆分rails规范和PORO规范的全部目的？或者这无关紧要，因为Zeus无论如何都会预加载Rails？我应该在我的spec_helper中做
ruby - 如何计算 Liquid 中的变量 +1 - 2
我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。最佳答案因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我
Ruby:如何使用带有散列的 'send' 方法调用方法？ - 2
假设我有一个类A，里面有一些方法。假设stringmethodName是这些方法之一，我已经知道我想给它什么参数。它们在散列中{'param1'=>value1,'param2'=>value2}所以我有:params={'param1'=>value1,'param2'=>value2}a=A.new()a.send(methodName,value1,value2)#callmethodnamewithbothparams我希望能够通过传递我的哈希以某种方式调用该方法。这可能吗？最佳答案确保methodName是一个符号，而
ruby-on-rails - 带有 Pry 的 Rails 控制台 - 2
当我进入Rails控制台时，我已将pry设置为加载代替irb。我找不到该页面或不记得如何将其恢复为默认行为，因为它似乎干扰了我的Rubymine调试器。有什么建议吗？最佳答案我刚发现问题，pry-railsgem。忘记了它的目的是让“railsconsole”打开pry。关于ruby-on-rails-带有Pry的Rails控制台，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/question
带有 attr_accessor 的类上的 Ruby instance_eval - 2
我了解instance_eval和class_eval之间的基本区别。我在玩弄时发现的是一些涉及attr_accessor的奇怪东西。这是一个例子:A=Class.newA.class_eval{attr_accessor:x}a=A.newa.x="x"a.x=>"x"#...expectedA.instance_eval{attr_accessor:y}A.y="y"=>NoMethodError:undefinedmethod`y='forA:Classa.y="y"=>"y"#WHATTT?这是怎么回事:instance_eval没有访问我们的A类(对象)然后它实际上将它添加到
ruby - 是否有用于复杂比较的漂亮语法？ - 2
方法应返回-1,0或1分别表示“小于”、“等于”和“大于”。对于某些类型的可排序对象，通常将排序顺序基于多个属性。以下是可行的，但我认为它看起来很笨拙:classLeagueStatsattr_accessor:points,:goal_diffdefinitializepts,gd@points=pts@goal_diff=gdenddefothercompare_pts=pointsother.pointsreturncompare_ptsunlesscompare_pts==0goal_diffother.goal_diffendend尝试一下:[LeagueStats.new(

c++ - 带有指针和比较器C++的优先级队列

有关c++ - 带有指针和比较器C++的优先级队列的更多相关文章

随机推荐