C++ приоритетная очередь не соответствует порядку FIFO

Question

Я использую STL priority_queue для сбора объектов собственного класса Lettura.

//---------LETTURA---------- 

enum Priority {zero, standard, urgent}; 

class Lettura{ 
public: 
int valore; 
char sensore; 
Priority priorita; 

Lettura(): valore(0),sensore('\0'),priorita(zero){} 
Lettura(const int val, const char s='\0', const Priority p=zero): valore(val),sensore(s), priorita(p){} 

friend ostream& operator<<(ostream& out, const Lettura & lett); 
}; 

Я хочу, чтобы быть совал в порядке убывающего «priorita», но я также хочу же приоритетные элементы для совали с политикой FIFO, как и в обычной очереди. я же приоритетные элементы в случайном порядке:

top: l5 urgent 
top: l1 standard 
top: l4 standard 
top: l6 standard 
top: l2 standard 
top: l3 standard 

Я хотел бы с тем же приоритетом элементы в порядке FIFO:

top: l5 urgent 
top: l1 standard 
top: l2 standard 
top: l3 standard 
top: l4 standard 
top: l6 standard 

Это мой код:

int main() { 
std::priority_queue<Lettura, std::vector<Lettura>, std::less<Lettura> > coda; 

Lettura l1(50,'a',standard); 
Lettura l2(50,'b',standard); 
Lettura l3(120,'c',standard); 
Lettura l4(100,'d',standard); 
Lettura l5(30,'e',urgent); 
Lettura l6(35,'f',standard); 

coda.push(l1); 
coda.push(l2); 
coda.push(l3); 
coda.push(l4); 
coda.push(l5); 
coda.push(l6); 


cout<<"top: "<<coda.top()<<"\n"; coda.pop(); 
cout<<"top: "<<coda.top()<<"\n"; coda.pop(); 
cout<<"top: "<<coda.top()<<"\n"; coda.pop(); 
cout<<"top: "<<coda.top()<<"\n"; coda.pop(); 
cout<<"top: "<<coda.top()<<"\n"; coda.pop(); 
cout<<"top: "<<coda.top()<<"\n"; coda.pop(); 
} 

Я применил эти методы сравнения:

bool operator<(const Lettura& l1, const Lettura& l2){ 
return l1.priorita < l2.priorita; 
} 

bool operator<=(const Lettura& l1, const Lettura& l2){ 
return l1.priorita <= l2.priorita; 
} 

Я также попытался с различными конструкторами очереди, но безуспешно:

std::priority_queue<Lettura> coda; 
std::priority_queue<Lettura, std::vector<Lettura>, std::less_equal<Lettura> > coda; 

Может кто-нибудь мне помочь?

Answer 1

Ваш код, кажется, работает, поскольку вы сначала получаете неотложные предметы. Нет никакого подзадача по времени вставки в очереди приоритетов с кучей, поэтому вы получите элементы с одинаковым приоритетом в неопределенном порядке, за исключением того, что они будут после элементов с более высоким приоритетом. Вам нужно добавить дополнительное поле, например, время, поставленное в очередь, и использовать его вместе с вашим перечислением Priority в вашем операторе сравнения.

Answer 2

Кажется, это ошибка библиотеки компилятора и стандарта C++. Они нарушают алгоритм выбора максимального элемента в priority_queue. Посмотрите поток, открытый мной в соответствии с кучами.

Why does std::is_heap use random access iterators instead of forward iterators?

А'т собирается подготовить соответствующее предложение.

Answer 3

вот простая реализация стабильной очереди приоритетов.

Он пытается сопротивляться заказе вытяжку с помощью обнуления счетчика вставки всякий раз, когда очередь пуста:

#include <iostream> 
#include <string> 
#include <queue> 
#include <algorithm> 


enum Priority 
{ 
    zero, standard, urgent 
}; 

inline std::ostream& operator <<(std::ostream& os, const Priority& p) 
{ 
    switch (p) { 
     case zero: 
      return os << "zero"; 
     case standard: 
      return os << "standard"; 
     case urgent: 
      return os << "urgent"; 
    } 
} 

class Lettura 
{ 
public: 
    int  valore; 
    char  sensore; 
    Priority priorita; 

    Lettura() 
     : valore(0) 
     , sensore('\0') 
     , priorita(zero) {} 

    Lettura(const int val, const char s = '\0', const Priority p = zero) 
     : valore(val) 
     , sensore(s) 
     , priorita(p) {} 

    friend std::ostream& operator <<(std::ostream& out, const Lettura& lett) 
    { 
     return out << "{ valore: " << lett.valore << ", sensore: " << lett.sensore << ", priorita: " << lett.priorita 
        << " }"; 
    } 
}; 


template<class T, class Comp> 
struct stable_priority_queue 
{ 
    using counter_type = std::size_t; 

    struct Proxy 
    { 
     Proxy(T&& o, counter_type c) 
      : object(std::move(o)) 
      , insertion_order_(c) {} 

     Proxy(const T& o, counter_type c) 
      : object(o) 
      , insertion_order_(c) {} 

     T   object; 
     counter_type insertion_order_; 
    }; 

    struct ProxyComp 
    { 
     bool operator()(Proxy const& l, Proxy const& r) const 
     { 
      if (major_order_(l.object, r.object)) 
       return true; 
      if (major_order_(r.object, l.object)) 
       return false; 
      return minor_order_(l.insertion_order_, r.insertion_order_); 
     } 

     Comp   major_order_; 
     std::greater<> minor_order_; 
    }; 


    decltype(auto) push(T item) 
    { 
     return queue_.emplace(std::move(item), counter_++); 
    } 

    T const& top() const 
    { 
     return queue_.top().object; 
    } 

    void pop() 
    { 
     queue_.pop(); 
     if (queue_.empty()) 
      counter_ = 0; 
    } 

    std::priority_queue<Proxy, std::vector<Proxy>, ProxyComp> queue_; 
    counter_type            counter_ = 0; 
}; 

struct lower_priority 
{ 
    bool operator()(const Lettura& l, const Lettura& r) const 
    { 
     return l.priorita < r.priorita; 
    } 
}; 

int main() 
{ 
    stable_priority_queue<Lettura, lower_priority> coda; 

    Lettura l1(50, 'a', standard); 
    Lettura l2(50, 'b', standard); 
    Lettura l3(120, 'c', standard); 
    Lettura l4(100, 'd', standard); 
    Lettura l5(30, 'e', urgent); 
    Lettura l6(35, 'f', standard); 

    coda.push(l1); 
    coda.push(l2); 
    coda.push(l3); 
    coda.push(l4); 
    coda.push(l5); 
    coda.push(l6); 


    std::cout << "top: " << coda.top() << "\n"; 
    coda.pop(); 
    std::cout << "top: " << coda.top() << "\n"; 
    coda.pop(); 
    std::cout << "top: " << coda.top() << "\n"; 
    coda.pop(); 
    std::cout << "top: " << coda.top() << "\n"; 
    coda.pop(); 
    std::cout << "top: " << coda.top() << "\n"; 
    coda.pop(); 
    std::cout << "top: " << coda.top() << "\n"; 
    coda.pop(); 
} 

Ожидаемые результаты:

top: { valore: 30, sensore: e, priorita: urgent } 
top: { valore: 50, sensore: a, priorita: standard } 
top: { valore: 50, sensore: b, priorita: standard } 
top: { valore: 120, sensore: c, priorita: standard } 
top: { valore: 100, sensore: d, priorita: standard } 
top: { valore: 35, sensore: f, priorita: standard }