0%

Why priority_queue has different cmp with std::sort

As I mentioned in the title, priority_queue has different type of cmp with std::sort.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool cmp_f(const int& lhs, const int& rhs) {
return lhs < rhs;
}

class Cmp {
public:
bool operator()(const int& lhs, const int& rhs) {
return lhs < rhs;
}
};

int main() {
vector<int> vec;

priority_queue<int, vector<int>, Cmp> pq_1; // work
priority_queue<int, vector<int>, less<int>> pq_2; // work
/* will not compile
priority_queue<int, vector<int>, cmp_f> pq;
priority_queue<int, vector<int>, Cmp()> pq;
*/

sort(vec.begin(), vec.end(), Cmp()); // work
sort(vec.begin(), vec.end(), cmp_f); // work
sort(vec.begin(), vec.end(), less<int>()); // work

return 0;
}

The thing is priority_queue want type while std::sort want object.
To figure out why they work in that way, let us read their definition.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class _Tp, class _Container = vector<_Tp>,
class _Compare = less<typename _Container::value_type> >
class _LIBCPP_TYPE_VIS_ONLY priority_queue
{
...
};

template <class _Tp, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY
void
sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
{
...
}

There is a difference with std::sort. Sort is a function, and you can let the compiler deduce it’s template arguments so you don’t have to specify them explicitly. The queue is a class template, and template arguments of a class template can not be deduced (not in this context at least). (I directly copy this paragraph from the reference which listed at the end :))

Reference

http://stackoverflow.com/questions/34850929/why-function-comparator-doesnt-work-in-priority-queue-like-it-does-in-sort