C++ 使用自定义比较函数初始化 priority_queue

Question

我有一个 Dijkstra class，它使用带有自定义比较功能的 priority_queue。我用 using 语句将队列命名为 DijkstraPriorityQueue。在 class 构造函数中，我初始化队列。为此，我在 lambda 表达式中给出了比较函数。

对于第一个队列 PQ1，比较函数是 { return distTo[u] > distTo[v]; } 并且编译正常，因为 vector<float> distTo 是 class 的成员。

但是对于第二个队列PQ2，函数是{ return distTo2[u] > distTo2[v]; }，其中vector<float> distTo2只是构造函数中的一个临时变量，不会编译。（我认为至少是这个原因）

此外，我随机尝试凭直觉将 vector<float> distTo2 更改为 static vector<float> distTo2 并编译，但我认为这不是我想要做的。我不熟悉函数内部的静态变量，因为它在 Java 或 C# 中不存在。无论如何，什么是使下面的代码按预期编译和工作的干净解决方案？

Dijkstra.h

class Dijkstra
{
public:
    Dijkstra();  
    ~Dijkstra();       

private:    
    vector<float> distTo;
};

Dijkstra.cpp

using DijkstraPriorityQueue = priority_queue<int, vector<int>, function<bool(int, int)>>;

Dijkstra::Dijkstra()
{           
    distTo = vector<float>(V, FLT_MAX);
    // Compiles fine
    DijkstraPriorityQueue PQ1 = DijkstraPriorityQueue([this](int u, int v)
        { return distTo[u] > distTo[v]; });

    vector<float> distTo2 = vector<float>(V, FLT_MAX);
    // Doesn't compile
    DijkstraPriorityQueue PQ2 = DijkstraPriorityQueue([this](int u, int v)
        { return distTo2[u] > distTo2[v]; });
}

编辑：

下面的代码也可以编译。任何线索为什么？有人可以解释 lambda 表达式中的 capture 是什么吗？或者在这种特定情况下我应该如何正确编写代码？

DijkstraPriorityQueue PQ2 = DijkstraPriorityQueue([distTo2](int u, int v)
    { return distTo2[u] > distTo2[v]; });

Answer 1

你的问题主要有两个方面：

这个“捕获”是什么东西，为什么会报错？
如何为优先级队列指定自定义比较函数？

这些方面分开讨论最清楚。

不幸的是，所提供的（不完整的）示例代码不太适合讨论这两个方面，所以我忽略它。

什么是 lambda 捕获。

考虑以下代码：

#include <stdio.h>

struct S
{
    int a_;

    void foo() const
    {
        // Compiles nicely:
        [this]() -> void { printf( "%d\n", a_ ); }();

        // Doesn't compile, oh why!:
        int b = 666;
        [this]() -> void { printf( "%d\n", b ); }();
    }
};

auto main()
    -> int
{ S{ 42 }.foo(); }

MinGW g++ 5.1.0 提供以下诊断（编译错误）：

x1.cpp: In lambda function:
x1.cpp:14:44: error: 'b' is not captured
         [this]() -> void { printf( "%d\n", b ); }();
                                            ^
x1.cpp:14:14: note: the lambda has no capture-default
         [this]() -> void { printf( "%d\n", b ); }();
              ^
x1.cpp:13:13: note: 'int b' declared here
         int b = 666;
             ^

要理解“未捕获”，让我们手动实现 lambdas，只需执行与编译器对其执行的操作等效的代码转换：

    void foo() const
    {
        // Compiles nicely:
        //[this]() -> void { printf( "%d\n", a_ ); }();
        class Functor_a
        {
        private:
            S const* captured_this_;

        public:
            void operator()()
            { printf( "%d\n", captured_this_->a_ ); }

            Functor_a( S const* this_capture )
                : captured_this_( this_capture )
            {}
        };
        Functor_a f_a{ this };
        f_a();

        // Doesn't compile, oh why!:
        int b = 666;
        // [this]() -> void { printf( "%d\n", b ); }();
        class Functor_b
        {
        private:
            S const* captured_this_;

        public:
            void operator()()
            { printf( "%d\n", b ); }

            Functor_b( S const* this_capture )
                : captured_this_( this_capture )
            {}
        };
        Functor_b f_b{ this };
        f_b();
    }
};

诊断现在更清楚了。由于 Functor_b 是一个 class，并且由于 C++ 中的 class 是完全独立的实体，因此其代码与 [=18= 的特定调用中的内容无关或无法访问].所以编译器不接受对某些未指定的 b 的引用，但会注意到，如果你真的指的是包含范围中的 b，那么嘿，那个名称 b 指的是一个不同的foo 的每次调用中的变量，并且不是有效的选择：

x2.cpp: In member function 'void S::foo() const::Functor_b::operator()()':
x2.cpp:37:35: error: use of local variable with automatic storage from containing function
                 { printf( "%d\n", b ); }
                                   ^
x2.cpp:28:17: note: 'int b' declared here
             int b = 666;
                 ^

一个解决方案是捕获值，即将其复制到仿函数 class 实例中，例如如下：

        class Functor_b
        {
        private:
            int const captured_b_;

        public:
            void operator()()
            { printf( "%d\n", captured_b_ ); }

            Functor_b( int const b_capture )
                : captured_b_( b_capture )
            {}
        };
        Functor_b f_b{ b };     // ← The capture.
        f_b();                  // ← Using the captured value.

或者，您可以捕获指向变量的指针，通过引用捕获。在这种情况下，指针仅在变量的生命周期内有效。所以你最好不要在那之后保留一个仿函数实例。

以 lambda 表示法表示，值的捕获可能如下所示：

[b]() -> void { printf( "%d\n", b ); }();

或者像这样，用一般的按值捕获任何需要的东西 =:

[=]() -> void { printf( "%d\n", b ); }();

通过引用捕获，即指针，如下所示：

[&]() -> void { printf( "%d\n", b ); }();

如何为 `std::priority_queue`.

指定比较函数

例如像这样：

#include <iostream>
#include <string>
#include <queue>
#include <vector>
using namespace std;

struct S
{
    string name;
    int birth_year;
};

auto main() -> int
{
    struct Age_sort
    {
        auto operator()( S const& a, S const& b )
            -> bool
        { return (a.birth_year < b.birth_year); }
    };
    using Q = priority_queue< S, vector<S>, Age_sort >;
    Q pq;
    pq.push( S{ "beta", 1980 } );
    pq.push( S{ "alfa", 1992 } );
    pq.push( S{ "charlie", 1971 } );
    while( not pq.empty() )
    {
        cout << pq.top().name << ' ' << pq.top().birth_year << endl;
        pq.pop();
    }
}

C++ 使用自定义比较函数初始化 priority_queue

C++ initialize priority_queue with custom compare function

c++

priority-queue

什么是 lambda 捕获。

如何为 `std::priority_queue`.

C++ 使用自定义比较函数初始化 priority_queue

C++ initialize priority_queue with custom compare function

c++

priority-queue

什么是 lambda 捕获。

如何为 std::priority_queue.

如何为 `std::priority_queue`.