CODEWITHSUNDEEP
c++templatescomparison
Peter Lee
Peter Lee

Reputation: 13819

Weird User-defined Comparison struct Error for priority_queue in C++

This is weird that the following code fails compilation:

#include <iostream>
#include <queue>
using namespace std;

struct Node {
    char  data;
    Node* next;
    Node(char c, struct Node* nptr = nullptr)
        : data(c), next(nptr) {}
};

struct NodeCmp {
    bool operator()(const Node*& lhs, const Node*& rhs) const {
        return lhs->data > rhs->data;
    }
};

int main() {
    priority_queue<Node*, vector<Node*>, NodeCmp> PQ;

    return 0;
}

with error:

prog.cpp:13:10: note:   conversion of argument 2 would be ill-formed:
In file included from /usr/include/c++/5/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/5/bits/char_traits.h:39,
                 from /usr/include/c++/5/ios:40,
                 from /usr/include/c++/5/ostream:38,
                 from /usr/include/c++/5/iostream:39,
                 from prog.cpp:1:
/usr/include/c++/5/bits/predefined_ops.h:123:46: error: invalid initialization of non-const reference of type 'const Node*&' from an rvalue of type 'const Node*'
         { return bool(_M_comp(*__it1, *__it2)); }
                                              ^

See this IDE one link: http://ideone.com/T2ST03

However, the following which uses template is fine:

#include <iostream>
#include <queue>
using namespace std;

struct Node {
    char  data;
    Node* next;
    Node(char c, struct Node* nptr = nullptr)
        : data(c), next(nptr) {}
};

template <class T>
struct NodeCmp {
    bool operator()(const T& lhs, const T& rhs) const {
        return lhs->data > rhs->data;
    }
};

int main() {
    priority_queue<Node*, vector<Node*>, NodeCmp<Node*>> PQ;

    return 0;
}

See the IDE one link: http://ideone.com/xPcNFK

I want to understand how could this happen, and why it's like this in C++? Thanks.

Upvotes: 0

Views: 53

Answers (2)

Holt
Holt

Reputation: 37616

const T& with T = Node* is Node* const&, not const Node*&:

  • Node * const& p is a const reference to a pointer to a non-const Node, i.e. you cannot modify it, but you can modify what it points to.

  • const Node*& is a non-const reference to a pointer to a const Node, i.e. you can modify the pointer, but not what it points to.

If you know you are dealing with pointers, just don't use references:

bool operator()(const Node* lhs, const Node* rhs) const

Upvotes: 2

juanchopanza
juanchopanza

Reputation: 227418

This is a (non-const lvalue) reference to a pointer-to-const Node:

const Node*& lhs

A non-const lvalue reference cannot bind to temporaries in standard C++. This is the reason for the compiler error. The simplest fix is to not pass references at all:

bool operator()(const Node* lhs, const Node* rhs) const

The reason it works with the template example is that, for T = Node*, const T& resolves to const reference to Node*.

Upvotes: 2

Related Questions