Почему приоритетная очередь STL неправильно сортирует мои объекты класса

Question

Я перегрузил оператор <, как показано, но каждый раз, когда программа запускается, мои объекты классов сортируются, по-видимому, случайным образом.

class Node
{
int decimal_value
public:
    Node(int decimal) : decimal_value(decimal)
    {}
    friend bool operator<(const Node& p1, const Node& p2);
};

 bool operator<(const Node& p1, const Node& p2)
{
    return p1.decimal_value < p2.decimal_value;
}

int main()
{
    Node* n1= new Node(5);
    Node* n2 = new Node(4);

    priority_queue<Node*> my_q;
    my_q.push(n1);
    my_q.push(n2);
}

Возможно, это связано с использованием указателей на узлы, а неСами узлы? И если так, как я могу это исправить?

Answer 1

priority_queue<Node*> my_q; будет сравнивать элементы типа Node* для сортировки, не разыменовывает эти указатели для вас и вызывает вашего перегруженного оператора. И сравнение несвязанных указателей имеет un определенное поведение, но не даст никакого полезного результата в вашем случае.

Когда вы исправите этот, будет другая ошибка: вы никогда не инициализируете decimal_value, поэтому его значение не определено / случайно.

Одним из решений было бы явное указание компаратора:

struct MyComparator {
    bool operator()(const Node*l, const Node*r) const {
        return l->decimal_value < r->decimal_value;
    }
};

std::priority_queue<Node*, std::vector<Node*>, MyComparator> q;