Как использовать priority_queue с нестатическим методом сравнения экземпляра класса?

Question

Предположим, у меня есть простой класс, подобный этому:

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

Вместо std::vector, я хотел бы передать значения в std::priority_queue.Вместо того, чтобы возвращать значение .front(), я бы хотел .get() значение .top() priority_queue на основе пользовательской функции сравнения.Допустим, это пользовательское сравнение вычисляется как абсолютная разница между значением и экземпляром reference.

У меня нет понятия , как объявить std::priority_queue в моих атрибутах класса.

Я пытался:

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

А потом:

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

Я также пытался с std::function, как это, но это вызывает несколько ошибок:

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

Но это не сработает (см. Repl.it ).

Есть идеи, как решить эту проблему, пожалуйста?

Answer 1

Если вы хорошо используете std::function (это может иметь небольшие накладные расходы), это будет работать, но вы попытались передать лямбду в объявление типа:

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;

это не будет работать.Вам необходимо использовать std::function в качестве типа:

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

и затем передать лямбду в m_priority ctor в качестве параметра:

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

, тогда это будет работать. Живой пример

Answer 2

Если вы когда-нибудь собираетесь изменить значение m_reference, вам нужно будет повторно отсортировать std::priority_queue.Ниже приведен (вероятно) неуклюжий способ сделать это, который будет очень дорогостоящим, если выполняется часто и / или очередь большая, но он выполняет свою работу.Код предназначен для добавления в ответ @Slavas.

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

Answer 3

Мне удалось заставить его работать, используя:

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

с

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

и

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

Вам также необходимо #include <functional>

Если я правильно понимаю ваш вопрос, это то, что вы хотели?

Вы также можете сделать свой компаратор struct или чем-то другим и использовать его вместо std::function, если вы не хотите ничегонедостатки производительности.

Обновление:

Версия со структурой будет выглядеть следующим образом (вы можете передать указатель this вместо ссылки на int или как вам больше нравится):

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