C++ priority queue does not respect FIFO order

Question

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

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

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

This is my code:

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;

Can somebody help me?

Answer 1

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.