没有默认构造函数作为模板参数的自定义比较器

Question

让我们看一个玩具示例，从两个排序数组中查找最小的m对数字。 撇开算法效率问题不谈，我想为优先级队列提供一个比较器 在初始化期间需要某些参数：

class Foo {
struct natural_order {
const std::vector<int> &x,&y;
natural_order( const std::vector<int> &x, const std::vector<int> &y ): x(x), y(y) {};
bool operator () ( const std::pair<int,int> &a, const pair<int,int> &b ) const {
return x[a.first]+y[a.second] < x[b.first]+y[b.second];
}
};
struct cmp {
std::unique_ptr<natural_order> o;
cmp( const std::vector<int> &x, const std::vector<int> &y ) {
o= std::make_unique<natural_order>(x,y);
}
bool operator () ( const std::pair<int,int> &a, const pair<int,int> &b ) const {
return (*o)(b,a);
}
};
public:
std::vector<std::vector<int>> m_smalles_pairs( std::vector<int> &x, std::vector<int> &y, int m ) {
std::vector<std::vector<int>> res(m);
std::priority_queue<int,std::vector<int>,cmp(x,y)> pq; //<-- the problem is here. Does not compile
for ( int i= 0; i < m; ++i ) {
auto pr= pq.top(); pq.pop();
res[i]= std::vector<int>{x[pr.first],y[pr.second]};
if ( pr.first+1 < x.size() )
pq.push({pr.first+1,pr.second});
if ( pr.second+1 < y.size() )
pq.push({pr.first,pr.second+1});
}
return res;
}
};

本质上，我希望比较器用参数初始化，但是如何将其作为priority_queue的第三个参数提供？如果不需要x和y参数，我会简单地在上面写cmp。

编辑：它似乎使用 lambda 以类似的行进行，如此处所述 C++ priority_queue lambda 比较器错误 我能够解决我的问题，但只是好奇struct比较器是否允许这种事情。

Answer 1

本质上，代码的问题在于比较的实现。 从技术上讲，比较类必须满足一些要求：

类型 T 满足 BinaryPredicate ---> CopyConstructible

您的类cmp不可复制构造，因为它的一个成员是std::unique_ptr(无法复制(。

所以我想说，一个正确的解决方案应该是根据这个原则重构你的设计。 我不知道您的问题的全部领域，所以我不能建议它的正确设计(此外，这可能是个人选择(。

也许，您可以从类中删除std::unique_ptr，只需将natural_order类型作为成员。当然，这意味着不同的复制构造调用。

此时，您可以使用正确的构造函数初始化std::priority_queue的比较器。

(2) explicit priority_queue(const Compare& compare)
: priority_queue(compare, Container()) { }

您的代码应如下所示：

std::priority_queue<int,std::vector<int>,cmp> pq(cmp{x, y});