Приоритетная очередь с настраиваемым компаратором

Я пытаюсь использовать приоритетную очередь для хранения настраиваемого возражения со следующими переменными-членами:

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

Я буду читать из файла хэш-карту идентификатора работы и веса работы. В конечном итоге у меня будет

unordered_map<string, int> jobWeight;

хранит эту информацию. Я хочу в конечном итоге поместить список заданий в priority_queue с приоритетом, основанным на хэш-карте jobWeight. Работа с наивысшим весом должна быть на первом месте.

Обращаясь к другим руководствам, я заметил, что вы должны создать отдельный класс / структуру и реализовать оператор (). Затем вы должны передать этот класс сравнения в параметры priority_queue. Однако похоже, что priority_queue создает новый экземпляр этого класса компаратора с параметрами по умолчанию? Как я могу ссылаться на свою хэш-карту 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;

    }

};

c++ c++11 priority-queue
person David Yuan    schedule 18.09.2016    source источник
comment
Изначально вы заявили, что jobWeight был unordered_map. Вы хотите преобразовать его в map и передать в качестве аргумента вашему компаратору или как?   -  person WhiZTiM    schedule 19.09.2016
comment
Используется ли эта карта для чего-нибудь еще, кроме этого компаратора? И: Насколько он велик?   -  person Daniel Jour    schedule 19.09.2016
comment
@DanielJour Карту следует использовать только для сравнения, когда я вставляю ее в свою очередь приоритетов. Карта будет такой же большой, как количество заданий ... (каждая работа будет иметь свой вес), поэтому может быть очень большой. В настоящее время конечная цель - выбрать работу для каждого временного интервала (задания не должны сохраняться на протяжении всего периода от начала до конца ... так что жадного подхода к выбору должностей должно быть достаточно. Я просто использую priority_queue, чтобы заполнить весь временной диапазон.   -  person David Yuan    schedule 19.09.2016

Ответы (2)


arrow_upward
2
arrow_downward

Конструктор по умолчанию std::priority_queue фактически принимает необязательные параметры:

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

Вы заметите, что первый параметр - это экземпляр класса компаратора.

Сначала создайте свой класс компаратора, сделав так, чтобы он ссылался на вашу хэш-карту любым удобным для вас способом, а затем используйте класс компаратора для создания своей очереди приоритетов.

person Sam Varshavchik    schedule 18.09.2016
comment
ну никогда не замечал этого. Большое спасибо! - person David Yuan; 19.09.2016

arrow_upward
2
arrow_downward

Как я могу ссылаться на свою хэш-карту jobWeight из этого класса компаратора?

Добавьте ссылку на карту в свой класс сравнения! Конечно, вам нужно убедиться, что эта ссылка остается в силе. И вы не можете использовать простую ссылку (поскольку они не могут быть скопированы, что должно быть у вашего класса Compare), но вместо этого можно использовать _ 1_.

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 в свой конструктор очереди приоритетов ( overload (1) в ссылке):

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

Поскольку нет конструктора, который позволяет перемещать класс Compare в очередь, вам действительно нужна ссылка в JobsByWeight. В противном случае была бы копия вашей карты (которая, как вы сказали, может быть огромной).

Примечание. Непроверенный код.

person Daniel Jour    schedule 18.09.2016
comment
Спасибо за это! Никогда не понимал, что priority_queues принимает параметры. - person David Yuan; 19.09.2016