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

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

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).

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

4

Решение

Мне удалось заставить его работать с помощью:

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

Другие решения

Если вы хорошо используете 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 );
} )
{
}

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

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);
}
1
По вопросам рекламы [email protected]