c++ - 使用自定义值比较器 boost 最小队列

Question

我想在稀疏图上实现最短路径搜索(它不是 boost 图，可能无法有效地转换成 boost 图)，所以我很自然地坚持使用优先级队列实现 Dijkstras 算法。由于我的图表是自定义图表，因此我需要将距离比较实现为一个函数对象并将其交给队列:

#include <boost/heap/fibonacci_heap.hpp>
#include <iostream>
#include <climits>

#define BIG (INT_MAX / 2)

struct node_compare {
  std::vector<int> dist;

  void set(int node, int d) {
    dist[node] = d;
  }

  node_compare(int dim) : dist(dim, BIG) {};

  /* this is a 'greater than' because boost implements max-heaps */
  bool operator()(const int& n1, const int& n2) const { 
    std::cout << "Comparing " << n1 << " < " << n2 << " = " << dist[n1] << " > " << dist[n2] << std::endl;
    return dist[n1] > dist[n2];
  }

};

typedef boost::heap::fibonacci_heap<int,  boost::heap::compare<node_compare>> priority_queue;

int main(int argc, char** argv) {
  /* comparator implementation, based on distances */
  node_compare cmp(5);

  priority_queue pq(cmp);

  cmp.set(3, 10);

  for (int i = 0; i < 5; i++)
    pq.push(i);

  while(!pq.empty()) {
    std::cout << pq.top() << std::endl;
    pq.pop();
  }
}

让我印象深刻的是，尽管我在构造函数中提供了一个实例，但优先级队列似乎以某种方式构造了它自己的 node_compare 实例。这应该是不可能的，因为 node_compare 没有默认构造函数...

我知道这看起来有点像“请帮我找出那个 bug”之类的问题，但我真的不知道我是否错过了一些重要的 C++ 语义或 boost 逻辑。

Answer 1

堆确实存储了它自己的 node_compare 实例，但不会默认构造它，而是从您在构造函数中传递的对象复制构造它。

因此在 priority_queue pq(cmp); 行中，队列使用 node_compare 类的自动生成的复制构造函数复制 cmp 对象.

如果您在创建 priority_queue 之前调用 cmp.set(3, 10);，它也应该设置在队列的比较器中。

恐怕一旦创建堆就无法更改比较器。堆对象有一个 value_comp() 成员函数，它返回对比较器的 const 引用，因此您不能更改返回的比较器。我认为您不能更改比较器，因为这会使堆中的数据结构无效。

但是您可以在比较器中存储对距离 vector 的引用:

struct node_compare {
    const std::vector<int> &dist_;

    node_compare(const std::vector<int> &dist) : dist(dist) {};

    bool operator()(const int& n1, const int& n2) const { 
        return dist_[n1] > dist_[n2];
    }
};

您只需要小心，不要在向堆中添加元素后更改传递的距离 vector 。