为什么std::priority_queue有一个构造函数接受Compare类型对象作为参数？

admin管理员组

文章数量:1623789

在我之前写的一篇博客《使用decltype取函数类型遇到的“invalidly declared function type”问题》中，最近收到一条评论：

X: 想问问，既然模板里面已经传入了comp指针了，为什么构造函数里还要再传一次呢？

我先把情境描述的更清楚一些，std::priority_queue是优先队列的标准库实现，其声明如下：

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

这个类有一堆不同签名的构造函数，不过我们只关心其中三个，前两个都是所谓的委托构造函数，依赖第三个构造函数对对象进行初始化：

priority_queue() : priority_queue(Compare(), Container()) { }

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

explicit priority_queue( const Compare& compare = Compare(),
                         const Container& cont = Container() );

令X疑惑的是下面的代码：

struct Node
{
    int value;
    int ext;
    static bool comp(const Node &a, const Node &b)
    {
        return a.value > b.value;
    }
};

priority_queue<Node, vector<Node>, decltype(Node::comp) *> pq(Node::comp);

为什么在模板参数里面“传过”comp指针了，还要在构造函数再传一次呢？其实只要搞清楚模板参数传入的到底是个什么东西，就不会有这个疑问了。

priority_queue类中含有一个类型为Compare的对象，用来对元素进行比较。第三个模板参数即为Compare的类型，当第三个模板参数为decltype(Node::comp) *时，Compare是什么呢？

答案是bool (*)(const Node &, const Node &)，因此以下这两种写法是等价的：

priority_queue<Node, vector<Node>, decltype(Node::comp) *> pq(Node::comp);
priority_queue<Node, vector<Node>, bool (*)(const Node &, const Node &)> pq(Node::comp);

它是一个函数指针，假如我们调用的是无参版本的构造函数会发生什么呢？答案是会得到一个野指针，它确实能通过编译，但运行时会发生什么情况就完全看天意了。

再来看看其他常见情况，Compare还可以是一个std::less这样的函数对象类型，或者是一个lambda表达式类型，还可以是一个std::function类型。

当Compare是一个函数对象类型时，且含有无参的构造函数，那上面的几个构造函数都是能够正常使用的。但是如果Compare所有构造函数含有参数，无法默认构造时，那上面第一个无参版本的构造函数就无法通过编译了。

struct NodeCompare0
{
    bool operator()(const Node &a, const Node &b)
    {
        return a.value > b.value;
    }
};

struct NodeCompare1
{
    enum Order
    {
        Big,
        Little
    };

    Order m_order;

    NodeCompare1(Order o) : m_order(o) {}
    bool operator()(const Node &a, const Node &b)
    {
        if (m_order == Big)
        {
            return a.value < b.value;
        }
        else
        {
            return a.value > b.value;
        }
    }
};

priority_queue<Node, vector<Node>, NodeCompare0> pq0;   // OK
priority_queue<Node, vector<Node>, NodeCompare1> pq1;   // error
priority_queue<Node, vector<Node>, NodeCompare1> pq2((NodeCompare1(NodeCompare1::Big)));    // OK

当Compare是一个lambda表达式类型时，情况和函数对象类似，不同的地方在于：lambda表达式即使不捕获任何变量（类似无参的函数对象），在C++20之前的版本也是不能默认构造的，但可以拷贝构造：

int main()
{
    enum class Order
    {
        Big,
        Little
    };
    Order order = Order::Big;
    auto lambdaCompare0 = [](const Node &a, const Node &b)
    {
        return a.value > b.value;
    };
    auto lambdaCompare1 = [order](const Node &a, const Node &b)
    {
        if (order == Order::Big)
        {
            return a.value < b.value;
        }
        else
        {
            return a.value > b.value;
        }
    };
    priority_queue<Node, vector<Node>, decltype(lambdaCompare0)> pq0;                   // error when -std=c++11 OK when -std=c++2a
    priority_queue<Node, vector<Node>, decltype(lambdaCompare0)> pq1(lambdaCompare0);   // OK
    priority_queue<Node, vector<Node>, decltype(lambdaCompare1)> pq2;                   // error
    priority_queue<Node, vector<Node>, decltype(lambdaCompare1)> pq3(lambdaCompare1);   // OK
}

std::function类型的情况和函数指针类似，不再赘述。

回到博客标题：为什么std::priority_queue有一个构造函数接受Compare类型对象作为参数？答案是：因为Compare类型无法默认构造或者默认构造的结果不是我们期望的结果。

本文标签： 有一个函数对象参数类型