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

Question

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

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

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

unordered_map<string, int> jobWeight;

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

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

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

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

将对 map 的引用添加到您的比较类!当然，您需要确保此引用保持有效。而且您不能使用普通引用(因为它们不可复制，而您的 Compare 类必须是)，而是可以使用 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;
  }
};

然后只需将您的 Compare 类的一个对象传递给您的 priority queue's constructor (在链接中重载 (1)):

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

由于没有允许您在队列中移动比较类的构造函数，因此您确实需要 JobsByWeight 中的引用。否则会有您的 map 的拷贝(如您所说，它可能很大)。

注意:未经测试的代码。