Why is STL priority queue incorrectly sorrting my class objects

Question

I have overloaded the < operator as shown but every time the program is run my class objects are sorted seemingly randomly.

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);
}

Is it possibly due to my use of pointers to Nodes rather than Nodes themselves? And if so how can I fix this?

When creating a [mcve] to show us, please make sure it replicates the problem you have, and don't contain any other unrelated errors. — Some programmer dude, Oct 25 '19 at 08:54
Your operator overload has *nothing* to do with a priority queue of pointers. They're being compared at face-value using stock pointer value comparison. Make a custom comparator type as the additional argument to the queue. — WhozCraig, Oct 25 '19 at 08:54
And yes, the problem is most likely because you have a queue of *pointers*, so the comparison operator that will be invoked is `bool operator<(Node*, Node*)`. — Some programmer dude, Oct 25 '19 at 08:55
Check this [link](https://stackoverflow.com/questions/16111337/declaring-a-priority-queue-in-c-with-a-custom-comparator) — gimme_danger, Oct 25 '19 at 08:58
What would be wrong with `priority_queue`? And if you really must store pointers, you should store smart pointers (unless someone else is responsible for deallocating them) — chtz, Oct 25 '19 at 09:02

Lukas-T · Accepted Answer · 2019-10-25T09:32:30.967

4

priority_queue<Node*> my_q; will compare elements of type Node* to sort, it will not dereference those pointers for you and call your overloaded operator. And comparison of unrelated pointers has undefined behaviour, but will yield no useful result in your case.

When you fixed this one, there will be another bug: You never initialize decimal_value, so it's value is undefined/random.

One solution would be to explicitly specify an comparator:

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;

edited Oct 25 '19 at 09:32

answered Oct 25 '19 at 08:58

Lukas-T

11,133
3
20
30

Comparison of unrelated pointers has [defined behavior](http://eel.is/c++draft/expr.rel#4) (although it is only a partial ordering). Subtraction [does not](http://eel.is/c++draft/expr.add#5). – Max Langhof Oct 25 '19 at 09:04
I see, so is there no way to use a priority_queue to sort what the pointers are pointing to? – Risen Oct 25 '19 at 09:22
@Risen, I added a small example :) – Lukas-T Oct 25 '19 at 09:34
@MaxLanghof Hm, I remember pointer comparison between unrelated pointers as UB as well. Could that possibly have changed with C++11? Unfortunately, not having access to older standards at the moment... – Aconcagua Oct 25 '19 at 12:12
@Aconcagua In C++11 it was well-defined (although mostly unspecified): https://timsong-cpp.github.io/cppwp/n3337/expr.rel#2. Similar for [n1905 from 2005](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1905.pdf). Let me see if there's an older draft somewhere... – Max Langhof Oct 25 '19 at 12:53
@MaxLanghof Well, C++11 I figured out myself – just that I'm old enough to have learned C++ with 98 standard... – Aconcagua Oct 25 '19 at 12:54
@Aconcagua I was able to dig up a C++03 standard, and it's only unspecified there too: https://cs.nyu.edu/courses/fall11/CSCI-GA.2110-003/documents/c++2003std.pdf – Max Langhof Oct 25 '19 at 13:26
@Aconcagua And here's C++98, also unspecified: http://www.lirmm.fr/~ducour/Doc-objets/ISO+IEC+14882-1998.pdf – Max Langhof Oct 25 '19 at 13:28
@MaxLanghof Thanks! Seems as if I mixed up something myself long ago and retained it until today... – Aconcagua Oct 25 '19 at 14:18

Why is STL priority queue incorrectly sorrting my class objects

1 Answers1