c++c++11stdpriority-queuecustom-compare

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


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?


Solution

  • 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;
    };