priority_queue with custom comparator as value in map constructor error

Question

I have created a priority_queue with custom comparator which stores string in lexicographically sorted order, and it works as expected.[ Ref. this] ]

Now, I want it to be value in an unordered_map, and I got error: no matching constructor for initialization ... and closest thing I found is this. I realize I need to pass the comparator to the constructor as well, but how?

Here is my code as of now :

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std; // Used to make code less verbose


int main() {
  auto cmp = [](string s1, string s2){
        return s1.compare(s2) > 0;
      };

  using myQuque = priority_queue<string, vector<string>, decltype(cmp)> ;
  // This code works
  myQuque pq(cmp);
  pq.push("ZZ");
  pq.push("AA");
  pq.push("CC");
  while(!pq.empty()){
    cout << pq.top() << " ";
    pq.pop();
  }

  // This doesn't. How do I pass 'cmp' to constructor?
  unordered_map<string, myQuque> table;
  auto p = table["r"];
  p.push("ZZ");
  p.push("AA");

}

https://godbolt.org/z/cvPfPd

I then realized that I can use multiset as well for this application, but I still would like to know how can I use priority_queue with custom comparator in map.

Answer 1

Using a lambda was a bad idea... just provide comparison through the comparison template argument, then no constructor argument is required...

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std; // Used to make code less verbose

struct Cmp {
    bool operator()(const string& s1, const string& s2) const {
        return s1.compare(s2) > 0;
    }
};

int main() {
  using myQuque = priority_queue<string, vector<string>, Cmp>;
  // This code works
  myQuque pq;
  pq.push("ZZ");
  pq.push("AA");
  pq.push("CC");
  while(!pq.empty()){
    cout << pq.top() << " ";
    pq.pop();
  }

  // This doesn't. How do I pass 'cmp' to constructor?
  unordered_map<string, myQuque> table;
  auto p = table["r"];
  p.push("ZZ");
  p.push("AA");
}

Note too I've changed the comparison to take arguments by const reference, avoiding deep copying the text being compared for each comparison (at least whenever longer than any Short-String-Optimisation buffer your std::string implementation might have).

Answer 2

Maps use the default constructor when creating new elements. You could use pointers, but you’d need to allocate each new entry:

 unordered_map<string, shared_ptr<myQuque>> table;
 auto p = make_shared<myQueue>(cmp);
 table["r"] = p;
 p->push("ZZ");
 p->push("AA");

Answer 3

Problem is that with custom run-time comparator, default constructor of myQuque is not available.

std::unordered_map::operator[] must be able to use default constructs for value in case there is no value ready for specyfic key. This is needed since it returns a reference to value which can be used in assignment expression.

To fix it you have to drop operator[], you can use this:

  unordered_map<string, myQuque> table;
  auto &p = table.emplace("r", cmp).first->second;
  p.push("ZZ");
  p.push("AA");

demo: https://godbolt.org/z/bPnrEe

As an alternative you can provide static comparator to priority_queue as Tony Delroys answer. In such case myQuque will have default constructor and problem vanishes.