带有自定义比较器的优先级队列

Question

我正在尝试使用优先级队列来保存使用以下成员变量反对的自定义：

class Jobs{
    string id;
    string location;
    int start;
    int end;
};

我将从文件中读取作业 ID 和作业权重的哈希图。我最终会有一个

unordered_map<string, int> jobWeight;

持有此信息。我想最终将作业列表推送到 priority_queue 中，其优先级基于散列图 jobWeight。权重最高的工作应该排在第一位。

参考其他教程，我注意到您应该创建一个单独的 class/struct 并实现 operator()。然后，您会将此比较 class 传递给 priority_queue 参数。但是，似乎 priority_queue 使用默认参数创建了此比较器 class 的新实例？我如何才能从这个比较器 class 中引用我的 jobWeight 哈希图？

class CompareJobs{

    map<string, int> jobWeight;

public:

    CompareJobs(map<string, int> &jobWeight){
        jobWeight = jobWeight;
    }

    bool operator () (const Jobs &a, const Jobs &b){

        return jobWeight.find(a)->second < jobWeight.find(b)->second;

    }

};

Answer 1

std::priority_queue的默认构造函数实际上采用可选参数：

explicit priority_queue(const Compare& x = Compare(), Container&& = Container());

你会注意到第一个参数是比较器的一个实例class。

首先构造你的比较器class，让它以你方便的任何方式引用你的hashmap，然后使用比较器class构造你的优先级队列。

Answer 2

How would I be able to reference my jobWeight hashmap from within this comparator class?

将对地图的引用添加到您的比较 class！当然，您需要确保此引用保持有效。而且您不能使用普通参考（因为它们不可复制，而您的 Compare class 必须是），而是可以使用 std::reference_wrapper.

using IDMap = std::unordered_map<std::string, int>;

struct JobsByWeight {
  std::reference_wrapper<IDMap const> weights_ref;
  bool operator()(Job const & lhs, Job const & rhs) const {
    auto const & weights = weights_ref.get();
    auto lhsmapping = weights.find(lhs.id);
    auto rhsmapping = weights.find(rhs.id);
    if (lhsmapping == weights.end() || rhsmapping == weights.end()) {
      std::cerr << "damn it!" << std::endl;
      std::exit(1);
    }
    return lhsmapping->second < rhsmapping->second;
  }
};

然后只需将您的比较对象 class 传递给您的 priority queue's constructor（在 link 中重载 (1)）：

std::priority_queue<Job, std::vector<Job>, JobsByWeight> queue{std::cref(that_id_map)};

由于没有允许您在队列中移动比较 class 的构造函数，因此您确实需要 JobsByWeight 中的引用。否则会有您的地图的副本（如您所说，它可能很大）。

注意：未经测试的代码。

带有自定义比较器的优先级队列

Priority Queue with custom comparator

c++

priority-queue

c++11