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

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 with lambda comparator error 我能够解决我的问题，但只是好奇 struct-comparator 是否允许这种事情。

Answer 1

本质上，您的代码的问题在于 Compare 的实现。从技术上讲，Compare-class 必须满足一些要求：

类型T满足BinaryPredicate ---> CopyConstructible

你的 class cmp 不是 可复制构造的 因为它的一个成员是 std::unique_ptr （它不能被复制）。

所以我想说一个合适的解决方案应该是按照这个原则重构你的设计。我不知道你的问题的全部范围，所以我不能建议什么是正确的设计（而且这可能是个人选择）。

或许，您可以从 class 中删除 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});

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

custom comparator without default constructor as template parameter

c++

priority-queue