0

The comparator function in priority_queue and std::sort in c++ sometimes seems very alike but still have slightly difference between them, sometimes is very confusing to me.

For example if I want to sort characters in a string by the count of characters in hashmap "hash" in descending order:

    unordered_map<char, int> hash;
    for(auto c: S){
        hash[c]++;
    }
    auto cmp = [&hash](char left, char right){
        return hash[left] > hash[right] || hash[left] == hash[right] && left > right;
    };
    sort(S.begin(), S.end(), cmp);

This works, but if another case in priority_queue:

    auto cmp = [](const pair<char, int>& l, const pair<char, int>& r){
        return l.second < r.second;
    };
    priority_queue<pair<char, int>, vector<pair<char, int>>, decltype(cmp)> pq(cmp);

    for(auto p: hash){
        pq.push(p);
    }

Why do we need decltype(cmp) and pq(cmp) in this case?

Also another question for the first case, is it possible to write cmp as a class? How to write it correctly if so? Since "hash" is declared inside orgnizeStr function, I am wondering if it is possible. The following won't work if I use cmp as class:

 class cmp{
 public:
     bool operator()(char l, char r){
         return hash[l] < hash[r];
     }
 };


 string orgnizeStr(....){
    ........
    unordered_map<char, int> hash;
    for(auto c: S){
        hash[c]++;
    }
    //auto cmp = [&hash](char left, char right){
    //    return hash[left] > hash[right] || hash[left] == hash[right] && left > right;
    //};
    sort(S.begin(), S.end(), cmp);
    ........
}

Please let me know if you have any thought! Thank you!

Edit: The difference of my questions is that for my first question is why there will be a difference between std:sort and priority_queue when using lambda expression

tsen0406
  • 119
  • 3
  • 4
  • 15
  • For you second question, `std::sort` takes an object, not a type. You need `sort(S.begin(), S.end(), cmp{})` to get an object of type `cmp` to pass to `sort`. – NathanOliver Mar 26 '19 at 21:23
  • I tried but still seems not working – tsen0406 Mar 26 '19 at 21:31
  • You also need to replicate the capture of hash. You do that in your functor by writing a constructor that takes it and store a reference to it. – NathanOliver Mar 26 '19 at 21:52

0 Answers0