Как написать класс компаратора для очереди приоритетов STL?

Question

Это два класса у меня есть

class Graph 
    { 
     private: 
      unordered_map<int, Vertex> _vertices; 
    }; 

    class Vertex 
    { 
     private: 
      unordered_map<Vertex *, int> _edges;//key: pointer to a vertex, data: edge weight from this vertex to a certain vertex 
      int _load_factor = 0; 
      int _id = 0; 
    }; 

Если я хочу использовать алгоритм Дейкстры для вычисления кратчайшего пути из определенного прохода, мне нужно использовать очереди с приоритетами. Я понятия не имею, как я могу написать класс компаратор для:

priority_queue<Vertex, vector<Vertex>, PathWeightComparer> dijkstra_queue{};

Это то, что я нашел в Интернете:

class PathWeightComparer 
{ 
public: 
    bool operator()(Vertex lhs, Vertex rhs) 
    { 
     return (lhs.getPathWeight() > rhs.getPathWeight()); 

    } 
}; 

Что левой и правой частях см? Вершины ли они от priority_queue? Если да, чтобы получить вес пути для этого сравнения, мне нужно знать, где от до факторов. Могу ли я просто создать новое имя переменной _path_weight и использовать его только для findShortestPath()? Главное, что я не понимаю, это понятие lhs и rhs, каковы они? Еще одна вещь, мой текущий класс компаратора приведет к максимальной куче или мини-куче?

Спасибо большое

Answer 1

Точка std::priority_queue, чтобы дать вам постоянное время доступа к элементу самого высокого приоритета, который выбирается с помощью функции сравнения (самый большой, самый маленький и т.д.).

Что такое lhs и rhs обратитесь к?

Вот как вы сравниваете. Два элемента передаются функции компаратора для определения того, какой из них «превосходит» по сравнению с другим (или имеет больший приоритет). Сравнение - это то, что мы называем двоичной операцией (два операнда), правильно?

Мой текущий класс компаратора приведет к максимальной куче или мини-куче?

Вы сравниваете с >, тем самым максимальная куча.

Наконец, как я заметил, подпись должна быть:

bool operator()(Vertex const& lhs, Vertex const& rhs);