无法将派生比较传递给 std::priority_queue

Question

我需要将派生比较器传递给 std::priority_queue，但由于某些原因，正在调用基础 class' operator()。

这是显示此行为的最小代码：

class Base {
    public:
    virtual bool operator() (int l, int r) const {
        cout << "Should not be called" << std::endl;
        return 0;
    }
    virtual ~Base() {}
};
class A : public Base { 
    public:
    bool operator() (int l, int r) const override {
        cout << "Should be called!!!!";
        return l < r;
    }
};
int main() {
    priority_queue<int, vector<int>, Base> pq((A()));
    pq.push(1);
    pq.push(2);
    pq.push(3);
    pq.push(0);
    cout << pq.top();
    return 0;
}

The code is available on ideone as well

请注意，我不能使用 priority_queue<int, vector<int>, A>，因为我还有 Base 的其他子 class，这将导致大量代码重复¹.

我做错了什么？如何将比较器传递给将在其生命周期内使用的 priority_queue？

(1) 我知道我可以通过使用接受 priority_queue<int,vector<int>, T> 的模板函数来绕过代码重复问题 - 但我真的不想这样做。

Answer 1

构造函数采用 const Compare&，在将对象传递给函数时不会导致任何切片，但我们在 documentation

Copy-constructs the underlying container c with the contents of cont. Copy-constructs the comparison functor comp with the contents of compare.

由于正在进行复制且模板类型为 Base，因此您只需复制并存储 A 对象的 Base 部分。

您必须将比较对象包装在某种包装器中，并公开一个非虚拟 operator ()，它将调用传递给 priority_queue 构造函数的类型的虚拟 operator() .

Answer 2

该标准将 Compare comp 指定为 23.6.4.1 中 class 模板的值成员。据说构造函数：

Initializes comp with x and c with y (copy constructing or move constructing as appropriate);

因此你有切片，即使参数类型实际上是 const Compare&.

要解决这个问题，您可以为比较器实现一个 pimpl-wrapper。这个包装器将在内部保留一个 Base& 到实际的比较器，并且在它的非虚拟 operator() 中只需调用 Base / A 比较器的 virtual operator() 。

请仔细考虑您的 A 对象的生命周期。根据比较器所需的状态，您可以在 Base 中实现 virtual clone-method。并在您的 PimplCompare 中将 Base 作为 std::unique_ptr<Base> - 您将其克隆到它的复制者中。或者您将其保留为 std::shared_ptr<Base>.

无法将派生比较传递给 std::priority_queue

Unable to pass derived Compare to std::priority_queue

c++

std

priority-queue

c++11