C++ initialize priority_queue with custom compare function

Question

I have a Dijkstra class which uses a priority_queue with a custom compare function. I named the queue DijkstraPriorityQueue with a using statement. Inside the class constructor, I initialize the queue. To do that, I give the compare function in a lambda expression.

For the first queue, PQ1, the compare function is { return distTo[u] > distTo[v]; } and this compiles fine, because the vector<float> distTo is a member of the class.

But for the second queue, PQ2, the function is { return distTo2[u] > distTo2[v]; } where vector<float> distTo2 is just a temporary variable inside the constructor, and that doesn't compile. (I think that's the reason at least)

Also, I randomly tried to change vector<float> distTo2 to static vector<float> distTo2 by intuition and it compiles, however I don't think this is what I want to be doing. I am not familiar with static variables inside functions, since that doesn't exist in Java or C#. At any case, what is a clean solution to make the code below compile and work as intended ?

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]; });
}

Edit:

The following code compiles too. Any clues why ? Can someone explain what capture is on lambda expressions ? Or how should I write my code properly in this specific case ?

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

Answer 1

There are two main aspects of your question:

• What is this “capture” thing, and why the error?

• How to specify a custom compare function for a priority queue?

These aspects are most cleanly discussed separately.

Unfortunately the presented (incomplete) example code is not well suited for discussing either aspect, so I just disregard it.

What is a lambda capture.

Consider the following code:

#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 provides the following diagnostics (compilation errors):

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;
             ^

To understand the “not captured”, let's implement the lambdas manually, just doing a code transformation equivalent to what the compiler does with it:

    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();
    }
};

The diagnostic is now more clear. Since Functor_b is a class, and since a class in C++ is completely free-standing entity, its code has no relation to or access to things in a particular invocation of foo(). So the compiler doesn't accept the reference to some unspecified b, but notes that if you really meant the b in the containing scope, then hey, that name b refers to a different variable in each call of foo, and isn't a valid choice:

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;
                 ^

One solution is to capture the value, i.e. copy it into the functor class instance, e.g. as follows:

        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.

Alternatively you could capture a pointer to the variable, capture by reference. In that the case the pointer is only valid for the lifetime of the variable. So you'd better not keep a functor instance around after that.

Expressed in lambda notation the capture of the value can look like this:

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

Or like this, with a general capture-whatever's-needed-by-value =:

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

Capturing by reference, i.e. a pointer, looks like this:

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

How to specify a compare function for a std::priority_queue.

E.g. like this:

#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();
    }
}