How to use priority_queue with a non-static compare method of class instance?

Question

Suppose I have a simple class like this:

class Test {
public:
  Test(int reference) { m_reference = reference; }
  void feed(int x) { m_data.push_back(x); }
  int get() { return m_data.front(); }
private:
  int m_reference;
  std::vector<int> m_data;
};

Instead of a std::vector, I would like to feed values into a std::priority_queue. Instead of returning the .front() value, I would like to .get() the .top() value of the priority_queue based on a custom compare function. Let's say this custom comparison is computed as the absolute difference between a value and the instance reference.

I have no idea how to declare the std::priority_queue in my class attributes.

I have tried:

bool compare(int a, int b) {
    return std::abs(a - m_reference) < std::abs(b - m_reference);
}

And then:

std::priority_queue<int, std::vector<int>, decltype(&Test::compare)> m_priority;

I also tried with std::function like this but this raises multiple errors:

std::function<bool(int a, int b)>> pq([this](int a, int b){
   return std::abs(a - m_reference) < std::abs(b - m_reference);
});

But this won't work (see Repl.it).

Any idea how to solve this please?

@MatthieuBrucher If I add `static`, will this still work despite the `reference` attribute being non-static? — Delgan, Dec 13 '18 at 17:21
What about using a lambda and capturing the instance you want to use for the comparison? — πάντα ῥεῖ, Dec 13 '18 at 17:21
@πάνταῥεῖ I tried but was unable to capture `[this]` (as I need it for the `m_reference` attribute). But I haven't much experience with lambda functions, maybe there is a workaround. — Delgan, Dec 13 '18 at 17:22
@Delgan Can you show what you tried with the lambda in your question please? Maybe we could fix your problem then. Generally it should be possible to capture `this.` — πάντα ῥεῖ, Dec 13 '18 at 17:25
@πάνταῥεῖ there is a problem of that `priority_queue` declaration using lambda — Slava, Dec 13 '18 at 17:35
@Slava It looks like the OP writing the answer, did solve it? — πάντα ῥεῖ, Dec 13 '18 at 17:36

Rinat Veliakhmedov · Accepted Answer · 2018-12-13T17:44:12.317

I managed to make it work by using:

std::function<bool(int,int)> comp = [this](int a, int b) { return std::abs(a - m_reference) < std::abs(b - m_reference); };

with

Test(int reference) : m_priority(comp) { m_reference = reference; }

and

std::priority_queue<int, std::vector<int>, decltype(comp)> m_priority;

You also need to #include <functional>

If I understand your question correctly, this is what you wanted?

You can also make your comparator a struct or something and use it instead of std::function if you don't want any performance drawbacks.

Update:

Version with struct would look like this (you can pass a this pointer instead of reference to int or however you prefer it):

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>

class Test {
public:
    Test(int reference) : m_priority(comp(m_reference)) { m_reference = reference; }
    void feed(int x) { m_data.push_back(x); }
    int get() { return m_priority.top(); }

    struct comp {
        int& reference;
        comp(int& ref) : reference(ref) {}
        bool operator()(int a, int b) { return std::abs(a - reference) < std::abs(b - reference); };
    };

private:
    int m_reference;
    std::vector<int> m_data;
    std::priority_queue<int, std::vector<int>, comp> m_priority;
};

Ok, it seems the solution using `struct` is probably the best one. Thanks for the answer! — Delgan, Dec 13 '18 at 17:40

score 5 · Answer 2 · answered Dec 13 '18 at 17:48

If you are fine using std::function (it may have slight overhead) it would work but you tried to submit lambda into type declaration:

std::priority_queue<
        int,
        std::vector<int>,
        std::function<bool(int,int)> comp = [this](int a, int b) { return std::abs(a - m_reference) < std::abs(b - m_reference); }> m_priority;

this would not work. You need to use std::function as a type:

std::priority_queue<
        int,
        std::vector<int>,
        std::function<bool(int,int)>> m_priority;

and then submit lambda into m_priority ctor as parameter:

Test(int reference) :
    m_reference( reference ),
    m_priority( [ref=reference]( int a, int b ) {
        return std::abs( a - ref ) < std::abs( b - ref ); 
    } )
 {
 }

then it would work. Live example

score 2 · Answer 3 · answered Dec 13 '18 at 18:53

If you are ever going to change the m_reference value, you would need to re-sort the std::priority_queue. The below is a (probably) clumsy way of doing it, which will be very costly if done often and/or the queue is big, but it gets the job done. The code is meant to be an add-on to @Slavas answer.

public:
    void set_reference(int x) {
        m_reference = x;
        sort();
    }
private:
    void sort() {
        std::priority_queue<int, std::vector<int>, std::function<bool(int,int)>> tmp(
            [this](int a, int b) { return std::abs(a - m_reference) < std::abs(b - m_reference); }
        );
        while(m_priority.size()) {
            tmp.emplace(std::move(m_priority.top()));
            m_priority.pop();
        }
        std::swap(tmp, m_priority);
    }

How to use priority_queue with a non-static compare method of class instance?

3 Answers3