Returning a priority_queue with custom comparator

Question

I have a function that needs to return a sorted list based on some input parameters. I've selected a std::priority_queue to hold this list.

But the compiler is giving me an error I don't recognize. Here's the code I have:

struct DepthCompare {
    bool operator()
        (const struct inst *&lhs, const struct inst *&rhs) const
    {
        return lhs->depth < rhs->depth;
    }
};

typedef priority_queue<struct inst*> HeuristicList;
HeuristicList getHeuristicList(struct BasicBlock &) {

    HeuristicList ret( DepthCompare );
    return ret;
}

The compiler says that a conversion from 'HeuristicList (*)(DepthCompare)' to non-scalar type 'HeuristicList' requested on the return statement's line.

It doesn't look like I'm trying to return a pointer. What's going wrong?

Answer 1

You have two problems.

To use a custom comparator, you must specify the comparator type as the third template argument:

typedef priority_queue<inst*, vector<inst*>, DepthCompare> HeuristicList;

HeuristicList ret( DepthCompare ); is interpreted as a function declaration, rather than a variable declaration, giving the error that you're seeing. You need to pass an instance of the comparator, and make sure it can't be interpreted as a function declaration:

HeuristicList ret = HeuristicList(DepthCompare());

However, since the constuctor's first argument is optional, and defaults to a default-constructed comparator, you can simply write

HeuristicList ret;

Or, since you're just returning the variable straight away,

return HeuristicList();

Answer 2

Note that the comparator is the third template parameter of priority_queue. You must declare your priority_queue like such:

typedef priority_queue<inst*, vector<inst*>, DepthCompare> HeuristicList;

This assumes you want to use vector as the backing container (default).

Also note that in your comparator functor, you want to declare the parameters as const reference to a pointer. What you have is a reference to a pointer to const. You want this:

bool operator()(inst* const& lhs, inst* const& rhs) const

You also don't need to pass an instance of your comparator object to the priority_queue constructor, as the default comparator constructor will do just fine.