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?

A'm去准备了相应的建议。

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 }