Очередь приоритетов C ++ в порядке возрастания с помощью специального метода для уникальных указателей на объекты - PullRequest
Новая
       9

Очередь приоритетов C ++ в порядке возрастания с помощью специального метода для уникальных указателей на объекты

0 голосов
/ 04 ноября 2018

У меня есть класс с именем Foo, и у каждого Foo объекта есть метод с именем yVal. То, что я хотел, было приоритетной очередью Foo объектов в порядке возрастания Foo.yVal()

Я перегружен оператор> и оператор <в <code>Foo к этому: 

   bool operator> (const Foo &f){
        return yVal() > f.yVal();
   }

   bool operator< (const Foo &f){
        return yVal() < f.yVal();
   }

И вот у меня есть следующий код: 

priority_queue<unique_ptr<Foo>, vector<unique_ptr<Foo>>, greater<unique_ptr<Foo>> > Queue;

Но это не сортировка очереди с приоритетами в порядке возрастания Foo.yVal(). Вместо этого они просто сортировали их в каком-то неизвестном случайном порядке. Я поместил оператор cout в operator> и operator <, и они даже не были вызваны. Поэтому я попытался сделать это с помощью лямбды: </p> 

auto cmp = [](Foo left, Foo right) {return left.xVal() > right.xVal();};
priority_queue<unique_ptr<Foo>, vector<unique_ptr<Foo>>, decltype(cmp) > Queue(cmp);

Но это дало мне ошибку "нестатический элемент данных, объявленный автоматически".

В идеале я бы хотел, чтобы это работало с большей <> и перегрузкой операторов. Если нет, кто-нибудь, пожалуйста, скажите мне, что я делаю не так с лямбдой (не слишком знаком с лямбдами и хотел бы избежать их, если это возможно).

Я также пытался использовать функтор, но, опять же, auto на функторе выдает мне ту же ошибку "объявлен не статический элемент данных, объявленный auto".

1 Ответ

0 голосов
/ 04 ноября 2018

Вы получили неизвестный случайный порядок , потому что, когда у вас есть greater<T> выполняется следующее действие 

// pseudocode
cmp(T lhs, T rhs) {
  return lhs > rhs;
}

что такое T в вашем коде? T равно unique_ptr<Foo>, есть ли operator>(unique_ptr<>,unique_ptr<>) в библиотеке C ++? да, это см. здесь , и этот оператор использует метод unique_ptr::get при сравнении: 

// Psuedocode when greater used:
cmp (unique_ptr<Foo>& lhs, unique_ptr<Foo>& rhs)
{
  lhs.get () > rhs.get()
}

Что возвращает unique_ptr::get? Возвращает указатель на Foo, так что вы сравниваете указатели с Foo экземплярами. Результат непредсказуем. Код компилируется и выполняется, но не выполняет то, что вы ожидали.

Как починить лямбду:

Какие объекты хранятся в вашей очереди? Foo или unique_ptr<Foo>? Вы храните unique_ptr<Foo>, поэтому параметры вашей лямбды должны быть объявлены с использованием этого типа. 

auto cmp = [](const unique_ptr<Foo>& left, const unique_ptr<Foo>& right) 
{                   ^^^^^^^^^^^^^^^^
    return left->yVal() > right->yVal();
};             ^^
priority_queue<unique_ptr<Foo>, vector<unique_ptr<Foo>>, decltype(cmp) > Queue(cmp);

Поскольку экземпляры unique_ptr не могут быть скопированы, вы должны передать их по ссылке. Также используйте оператор -> для доступа к методу yVal.

EDIT: версия с функциональным объектом. 

 // comparator as function object with overloaded operator()
 struct Cmp {
   bool operator()(const std::unique_ptr<Foo>& left, const std::unique_ptr<Foo>& right) const {
     return left->xVal() > right->xVal();
   }
 };

class YourClass {
public:
   std::priority_queue<std::unique_ptr<Foo>, std::vector<std::unique_ptr<Foo>>, Cmp> Queue;
...