如何将 priority_queue 与 class 实例的非静态比较方法一起使用？

Question

假设我有一个像这样的简单 class:

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, I would like to feed values into a std::priority_queue。我不想返回 .front() 值，而是希望根据自定义比较函数 .get() priority_queue 的 .top() 值。假设此自定义比较计算为值与实例之间的绝对差异 reference.

我不知道如何在我的 class 属性中声明 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<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;
};

Answer 2

如果您使用 std::function 没问题（它可能会有轻微的开销）它会起作用，但您尝试将 lambda 提交到类型声明中：

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;

然后将 lambda 作为参数提交到 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 ); 
    } )
 {
 }

那就行了。 Live example

Answer 3

如果您要更改 m_reference 值，则需要重新排序 std::priority_queue。下面是一种（可能）笨拙的方法，如果经常这样做会非常昂贵 and/or 队列很大，但它完成了工作。该代码旨在作为@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);
    }

如何将 priority_queue 与 class 实例的非静态比较方法一起使用？

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

c++

c++11

std

priority-queue

custom-compare