priority_queue在映射构造函数错误中使用自定义比较器作为值

Question

我已经创建了一个带有自定义比较器的priority_queue，它以字典排序的顺序存储字符串，并且可以按预期工作。【参考此】】

现在，我希望它是unordered_map中的值，我得到了error: no matching constructor for initialization ...，我找到的最接近的东西是这个。我意识到我也需要将比较器传递给构造函数，但如何传递呢？

这是我目前的代码：

#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

然后我意识到我也可以将multiset用于此应用程序，但我仍然想知道如何在map中使用带有自定义比较器的priority_queue。

Answer 1

使用lambda是个坏主意。。。只需通过比较模板参数提供比较，则不需要构造函数参数。。。

#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");
}

请注意，我已经将比较更改为通过const引用获取参数，避免了对每次比较所比较的文本进行深度复制(至少在比std::string实现可能具有的任何短字符串优化缓冲区时(。

Answer 2

映射在创建新元素时使用默认构造函数。您可以使用指针，但需要分配每个新条目：

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

Answer 3

问题是使用自定义运行时比较器时，myQuque的默认构造函数不可用。

std::unordered_map::operator[]必须能够为值使用默认构造，以防没有为特定键准备好的值。这是必需的，因为它返回了对可在赋值表达式中使用的值的引用。

要修复它，你必须删除operator[]，你可以使用这个：

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

演示：https://godbolt.org/z/bPnrEe

作为替代方案，您可以提供静态比较器到priority_queue作为Tony Delroys的答案。在这种情况下，myQuque将具有默认构造函数，问题就消失了。