c++ stl 将参数正确设置为 priority_queue

Question

下面是错误的代码片段。

我想用c++的优先级队列stl实现dijkstra。但我想不出将此 priority_queue 与边缘 class 一起使用的正确语法。我想根据权重将优势放在 priority_queue 上。

class edge{
public: 
    int src;
    int dest;
    int wt;
};

class comp {
bool operator() (int a, int b) {
    if(a<=b){
        return true;
    }else{
        return false;
    }
   }
};


priority_queue<int,edge,comp> check;

edge e1,e2,e3;
e1.dest=1;
e2.dest=2;
e3.dest=3;

Answer 1

#include <queue>
#include <iostream>

class edge{
public:
    int src;
    int dest;
    int wt;
};

struct less_weight {
    bool operator() (const edge& a, const edge& b) {
        return a.wt < b.wt;
    }
};

struct greater_weight {
    bool operator() (const edge& a, const edge& b) {
        return a.wt > b.wt;
    }
};

int main()
{
    std::priority_queue<int,std::vector<edge>,less_weight> prioritise_higher_weights;
    prioritise_higher_weights.push(edge{0, 1, 1 });
    prioritise_higher_weights.push(edge{1, 2, 2 });
    prioritise_higher_weights.push(edge{2, 3, 3 });

    std::priority_queue<int,std::vector<edge>,greater_weight> prioritise_lower_weights;
    prioritise_lower_weights.push(edge{0, 1, 1 });
    prioritise_lower_weights.push(edge{1, 2, 2 });
    prioritise_lower_weights.push(edge{2, 3, 3 });

    std::cout << prioritise_higher_weights.top().wt << std::endl;
    std::cout << prioritise_lower_weights.top().wt << std::endl;
}

预期输出：

3
1

请注意优先级队列如何按给定谓词的逆排序。

Answer 2

先阅读spec for priority_queue。说真的，读它。

请注意，第一个模板参数是您要存储的类型，因此如果您要存储 Edges，那么 Edge 应该是您的第一个参数。

第二个模板参数是 priority_queue 将在下面用来存储您提供的值的容器。默认情况下，是 std::vector，我认为对于演示目的来说已经足够了。

第三个模板参数是用于比较您将存储在队列中的值的比较器。由于您正在存储 Edges，因此您需要一个比较器 class 能够比较 Edge 个实例，而不是 ints。

上面说了，试试这个：

#include <vector>
#include <queue>

class Edge{
public:
    int src;
    int dest;
    int wt;
};

struct comp {
  // note the use of references
  bool operator() (const Edge& a, const Edge& b) {
    // comparison by edge weights
    return a.wt < b.wt;
  }
};

int main() {
  std::vector<Edge> storage;
  comp compare;
  std::priority_queue<Edge, std::vector<Edge>, comp> check(compare);

  Edge e1,e2,e3;
  e1.wt=1; e1.src=1; e1.dest=2;
  e2.wt=2; e2.src=1; e2.dest=2;
  e3.wt=3; e3.src=2; e3.dest=3;

  check.push(e1);
  // pushing the maximum in the middle, let's see where it gets
  check.push(e3);
  check.push(e2);

  // let's see what's on top
  const Edge& top=check.top();
  std::cout << "weight: "<< top.wt 
            << " src:" << top.src 
            << " dest:" << top.dest << std::endl; // got the maximum on top
}

c++ stl 将参数正确设置为 priority_queue

c++ stl correct parameters to priority_queue

c++

stl

dijkstra

priority-queue