C ++优先级队列不遵守FIFO顺序 [英] C++ priority queue does not respect FIFO order

问题描述

我正在使用STL priority_queue来收集我自己的Lettura类的对象.

I'm using the STL priority_queue to collect objects of my own class 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策略弹出相同优先级的元素，就像在普通队列中一样. 我会以随机顺序获得相同优先级的元素:

I want them to be popped in order of decrescent "priorita", but I also want same-priority elements to be popped with FIFO policy like in a normal queue. I get same-priority elements in a random order:

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

我想要按FIFO顺序排列相同优先级的元素:

I would like same-priority elements in a FIFO order:

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();
}

我已经实现了以下比较方法:

I have implemented these comparison methods:

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;
}

我也尝试过使用不同的队列构造函数，但未成功:

I have also tried with different queue constructors but unsuccessfully:

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

有人可以帮我吗?

推荐答案

您的代码似乎可以正常工作，因为您可以先将紧急物品取出.在基于堆的优先级队列中，没有按插入时间进行子排序，因此，您将以未定义的顺序获得具有相同优先级的项目，只是它们将排在优先级较高的项目之后.您需要添加一个额外的字段，例如放入队列的时间，并将其与比较运算符中的Priority枚举一起使用.

Your code appears to be working, in that you get the urgent items out first. There is no sub-ordering by insertion time in a heap based priority queue, so you will get the items with the same priority out in an undefined order, except that they will be after items with a higher priority. You need to add an extra field, such as time put into queue, and use that along with your Priority enum in your comparison operator.

这篇关于C ++优先级队列不遵守FIFO顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！