How does this code work? Specifically, the WorkerCompare struct

Question

(Sorry if this question sounds vague. I'll add more information if needed.)

The task of the program is to simulate parallel processing. One solution I found on the internet contains this code which works but I don't know how. Specifically, why and how WorkerCompare was used:

class Worker {
    public:
        int id;
        long long nextFreeTime;
        Worker (int id) {
            this->id = id;
            nextFreeTime = 0;
        }
};

struct WorkerCompare {
    bool operator()(const Worker &w1, const Worker &w2) const {
        if(w1.nextFreeTime == w2.nextFreeTime)
            return w1.id > w2.id;
        else
            return w1.nextFreeTime > w2.nextFreeTime;
    }
};

This code was mainly used in this function:

void AssignJobs() {
    assigned_workers_.resize(jobs_.size());
    start_times_.resize(jobs_.size());
    priority_queue<Worker, vector<Worker>, WorkerCompare> pq;
    for(int i = 0; i < num_workers_; i++) {
        pq.push(Worker(i));
    }
    for (int i = 0; i < jobs_.size(); i++) {
        Worker freeThread = pq.top();
        pq.pop();
        assigned_workers_[i] = freeThread.id;
        start_times_[i] = freeThread.nextFreeTime;
        freeThread.nextFreeTime += jobs_[i];
        pq.push(freeThread);
    }
  }

It adds elements to the vectors assigned_workers_ and start_times_ which lists the thread used to do a process as well as at what time the process started.

The full source code can be seen here.

You should read the documentation before using a class: https://en.cppreference.com/w/cpp/container/priority_queue. This is very basic knowledge that every C++ programmer should know. I highly recommend you reading a few C++ books. — Phil1970, Jun 21 '21 at 00:24

score 1 · Accepted Answer · answered Jun 20 '21 at 23:27

1

priority_queue<Worker, vector<Worker>, WorkerCompare> pq;

I assume that this is the std::priority_queue from the standard library.

Priority queues work by comparing elements. That is what WorkerCompare is used for. It compares objects of type Worker.

answered Jun 20 '21 at 23:27

eerorika

232,697
12
197
326

So, if I understand this correctly, `pq` has a type `Worker` as indicated by the first parameter, and the `pq.push(Worker(i));` adds an element to the `vector` indicated by the second parameter, and the `WorkerCompare` keeps the queue organized. Is that correct? – Carl Eric Doromal Jun 20 '21 at 23:41
@CarlEricDoromal `vector` is the type of container that the queue uses for internal storage. But yeah, that's pretty much it. See also this: https://stackoverflow.com/q/388242/2079303 – eerorika Jun 20 '21 at 23:48

How does this code work? Specifically, the WorkerCompare struct

1 Answers1