STL priority_queue parameters

Question

When creating a STL priority_queue, the third argument (the one that decides how to compare elements in the queue to decide which is largest)must be a class in which the function operator is defined. It would be much more convenient if a lambda expression could be supplied. Why is that not allowed? A lambda expression should be considered to be compile time constant if it is not capturing any variables, right?

struct compare{
  bool operator()(int p, int q){return p > q;}
};

priority_queue< int, vector<int>, compare> intpq;

priority_queue< int, vector<int>,
                [](int p, int q){return p > q;}
 > intpq2;

The second definition, i.e. of intpq2, gives an error: template argument 3 is invalid. Is there a fundamental problem in accepting the second definition, or is it just that the designers of priority_queue chose not to allow it?

juanchopanza · Accepted Answer · 2015-04-01T07:51:08.003

2

The third parameter of std::priority_queue is a type. A lambda expression is not a type, but rather, an expression (you can think of it as an instance or object of something). On top of that, lambdas do not have an type that can be known a priori, but stateless lambdas do convert to pointer to function .

There are some work-arounds you can use in order to instantiate priority_queues with lambdas:

Make the 3rd parameter a pointer to function and pass a stateless lambda to the constructor. You can also pass plain function pointers. For example,
Make the 3rd parameter an std::function<bool(int, int)> and pass any kind of lambda that matches the correct signature to the constructor. You can pass anything that can be used to construct an std::function<bool(int)>.

For example,

// no capture. Pointer to function is OK
std::priority_queue<int, std::vector<int>, bool (*)(int, int)>
    q2([](int a, int b){return a < b;});

or

// capture. Can't use pointer to function.
std::priority_queue<int, std::vector<int>, std::function<bool(int, int)>>
    q2([some_var](int a, int b){return a < b;});

edited Apr 01 '15 at 07:51

answered Apr 01 '15 at 07:12

juanchopanza

223,364
34
402
480

Well, lambdas, like all expressions, have a type. It's just an unspeakable one. – T.C. Apr 01 '15 at 07:15
@T.C. Rephrased (and added examples.) – juanchopanza Apr 01 '15 at 07:20
The answer is helpful. However, it does not answer my question: is there a fundamental problem in defining priority_queue template class so that the comparison function could be accepted as a function rather than as a class. I guess for that the template parameter would have to be a function type, with arguments of type = the type of the object stored in the priority_queue. This is perhaps not allowed -- at least it did not work in an example I tried compiling. In any case, thanks. – Ekalavya Apr 01 '15 at 10:15
@Ekalavya Obviously not. My first example accepts a function. The class limitation does not exist. – juanchopanza Apr 01 '15 at 10:17
It accepts a function in the constructor -- but not as a template argument. – Ekalavya Apr 01 '15 at 10:18
@Ekalavya It accepts the type of a function as template parameter. It cannot accept an instance of a function as one. Just like it can't accept an instance of a functor as a template parameter. – juanchopanza Apr 01 '15 at 10:19
When you say "cannot accept an instance of a function", do you mean specifically priority_queue cannot (which I agree with), or do you mean that priority_queue cannot be rewritten to accept an instance of a function as a template argument? – Ekalavya Apr 01 '15 at 10:22
@Ekalavya I don't think it can be re-written without breaking backwards compatibility. Even if it could, it isn't going to happen so the question is moot. – juanchopanza Apr 01 '15 at 10:23
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/74251/discussion-between-ekalavya-and-juanchopanza). – Ekalavya Apr 01 '15 at 10:24
@Ekalavya Template non-type arguments are only allowed to be certain specific types because they need to be mangled. And though there are talks about extending the range of allowed types, `std::function` with its complex type-erasure machinery, which often requires dynamic allocation, is almost certainly never going to be allowed. – T.C. Apr 06 '15 at 11:28

score 1 · Answer 2 · answered Apr 01 '15 at 07:24

The third template parameter of priority_queue is a type. Lambda expressions are, well, expressions, not types. An expression has a type. Each lambda expression has a distinct, "unspeakable", type. Pretty much the only way you can refer to it is via auto and decltype:

auto cmp = [](int a, int b){return a < b;};
std::priority_queue<int, std::vector<int>, decltype(cmp)> q1(cmp);

Which is OK if you are just using q1 locally. If you need to pass it around, it can be rather difficult for the users of your function to spell the priority_queue's type, and you may need to resort to one of the ways shown in @juanchopanza's answer.

STL priority_queue parameters

2 Answers2