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

Here is another possible stable_priority_queue implementation that keeps the same interface provided by priority_queue:

template <class T>
struct stable_element
{
    stable_element(T&& o, std::size_t c)
        : object_(std::move(o))
        , insertion_order_(c)
    {
    }
    stable_element(const T& o, std::size_t c)
        : object_(o)
        , insertion_order_(c)
    {
    }
    operator T() { return object_; }

    T object_;
    std::size_t insertion_order_;
};

template <class T>
bool operator<(const stable_element<T>& lhs, const stable_element<T>& rhs)
{
    return (lhs.object_ < rhs.object_) || (!(rhs.object_ < lhs.object_) && (rhs.insertion_order_ < lhs.insertion_order_));
}

template <class T,
          class Container = std::vector<stable_element<T>>,
          class Compare = std::less<typename Container::value_type>>
class stable_priority_queue : public std::priority_queue<stable_element<T>, Container, Compare>
{
    using stableT = stable_element<T>;
    using std::priority_queue<stableT, Container, Compare>::priority_queue;
public:
    const T& top() { return this->c.front().object_; }
    void push(const T& value) {
        this->c.push_back(stableT(value, counter_++));
        std::push_heap(this->c.begin(), this->c.end(), this->comp);
    }
    void push(T&& value) {
        this->c.push_back(stableT(std::move(value), counter_++));
        std::push_heap(this->c.begin(), this->c.end(), this->comp);
    }
    template<class ... Args>
    void emplace(Args&&... args) {
        this->c.emplace_back(T(std::forward<Args>(args)...), counter_++);
        std::push_heap(this->c.begin(), this->c.end(), this->comp);
    }
    void pop() {
        std::pop_heap(this->c.begin(), this->c.end(), this->comp);
        this->c.pop_back();
        if (this->empty()) counter_ = 0;
    }

protected:
    std::size_t counter_ = 0;
};

In a std::priority_queue, there are protected members c and comp that correspond respectively to the underlying container and the comparison function object. With this approach of inheriting from std::priority_queue, we need to modify the behavior of top, push, emplace and pop. The documentation for std::priority_queue for each of these function provides the implementation of those functions in terms of what it does with the c and comp members. This was quite helpful in rewriting the modified member functions in terms of stable_element<T>.

To use this stable_priority_queue for the OPs use case, we just need to provide a bool operator<(const Lettura& l, const Lettura& r) { return l.priorita < r.priorita; } to sort the priority as desired:

enum Priority
{
    zero, standard, urgent
};

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

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

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

int main()
{
    stable_priority_queue<Lettura> coda;

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

    coda.push(l1);
    coda.push(l2);
    coda.push(l3);
    coda.emplace(100, 'd', standard);
    coda.emplace(l5);
    coda.emplace(l6);

    while (!coda.empty()) {
        std::cout << "top: " << coda.top() << "\n";
        coda.pop();
    }
}

Output:

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 }

Here is a LIVE demonstration of all of this put together

Answer 2

here is a simple implementation of a stable priority queue.

It attempts to resist ordering exhaustion by zeroing the insertion counter whenever the queue is empty:

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

expected results:

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 }

Answer 3

It seems it is a bug of the compiler library and of the C++ Standard. They break the algorithm of selecting of the maximum element in the priority_queue. See the thread opened by me according to heaps.

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

A'm going to prepare the corresponding proposal.

Answer 4

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.