Confusion of how to use self define compare functions in std::sort and std::priority_queue

user_11662984 0
Viewed 100

I am trying to figure out the reasons why you define custom compare function differently for std::sort and std::priority_queue.

for example, for std::sort I can do something like this:

bool compare(const vector<int>& a, const vector<int>& b)
{
    return a[0] < b[0];
}
class foo
{
public:
    vector<vector<int>> f(vector<vector<int>> list)
    {
        std::sort(list.begin(), list.end(), compare);
        return list;
    }
};


int main()
{
    vector<vector<int>> t = { {2,1},{1,0},{3,7} };
    foo n;

    auto ans = n.f(t);
    for (vector<int> x : ans)
    {
        printf("x[0]: %d , x[1]: %d \n", x[0], x[1]);
    }
    return 0;
}

after running the code the result is:

x[0]: 1 , x[1]: 0

x[0]: 2 , x[1]: 1

x[0]: 3 , x[1]: 7

However, if i define another function in foo like this:

vector<vector<int>> f1(vector<vector<int>> list)
{
    std::priority_queue<vector<int>, vector<vector<int>>, compare> pq;
}

The compiler will not allow me to do this. The simple way for me to get around this is to make a struct inside the class like this:

struct Compare
{
    bool operator()(const vector<int>& a, const vector<int>& b)
    {
        return a[0] < b[0];
    }
};

Here is what i have so far: From the en.cppreference.com, std::sort pass in a comparison function object, but priority_queue is passing in a Compare type. I assume this might be why I can't use the same compare function for the priority queue.

Another thought is that because std::sort is a function and priority_queue is a container, so we need to make it different?

This is all I have for now.

My most concern for this is why they are behaving so differently? What is the major reason for this to be different? why we need it to be different?

p.s. Anyone have any good book recommendation for explaining the STL deeply and more concentrating on explaining the code of STL and why they made it like this?

templates stl c++
1 Answers

You're specifying compare as the 3rd template argument for std::priority_queue, which is not the correct type name. You need to specify it as an function pointer type, (and pass the function pointer as the function argument). e.g.

std::priority_queue<vector<int>, vector<vector<int>>, decltype(compare)*> pq(compare);

or 

std::priority_queue<vector<int>, vector<vector<int>>, bool (*)(const vector<int>&, const vector<int>&)> pq(compare);

std::sort is a function template, so when you can pass compare as the function argument and the template parameter could be deduced automatically (as the function pointer type); std::priority_queue is a class template, so you have to specify the template argument explicitly, you just need to specify the type correctly (as the function pointer type, just as the type of the template parameter type of std::sort which is deduced automatically).

EDIT

Since C++17 we have class template argument deduction, and then you could use it as

vector<vector<int>> f1(vector<vector<int>> list)
{
    // deduced T=vector<int>, Container=vector<vector<int>>, Compare=bool (*)(const vector<int>&, const vector<int>&)
    std::priority_queue pq(compare, list);
    return ...
}

then we don't need to specify the template arguments.

user_33097900
Related