Priority Queue with custom comparator

Question

I am trying to use a priority queue to hold a custom objected with the following member variables:

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

I will be reading from file a hashmap of Job ID and the weight of the job. I will ultimately have a

unordered_map<string, int> jobWeight;

holding this information. I want to push a list of Jobs into a priority_queue eventually with the priority based on the hashmap jobWeight. The highest weighted job should come first.

Referring to other tutorials, I noticed that you should create a separate class/struct and implement the operator(). Then you would pass in this comparison class into the priority_queue parameters. However, it appears that the priority_queue creates a new instance of this comparator class with default parameters? How would I be able to reference my jobWeight hashmap from within this comparator class?

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?

Add a reference to the map to your Compare class! Of course you need to make sure that this reference stays valid. And you cannot use a plain reference (as these are not copy-able, which your Compare class must be) but instead can use a 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;
  }
};

Then just pass an object of your Compare class to your priority queue's constructor (overload (1) in the link):

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

Since there's no constructor that allows you to move your Compare class in the queue you really need a reference in JobsByWeight. Otherwise there'd be a copy of your map (which could be huge, as you said).

Note: Untested code.