Thread: Priority queue and FIFO

Hello all,

I am looking for a solution on how to order a queue with priority.
Simply put, my requirements are:
- All elements must be FIFO. Whatever is added first must always come out first (unless there is a higher priority item first).
- Order by priority. Higher priority items will always come before lower ones.

std::priority_queue sounds perfectly for the job, but I can't for the life of me get the pop operation to maintain FIFO order among equal priorities. Does anyone have any idea on how to achieve this with priority_queue or some other container in some way or form?

Basically, what I have tried so far is this:

Code:

bool operator > (const XQueueItem& other)
{
	return (m_receipt.GetPriority() > other.m_receipt.GetPriority());
	//if (m_receipt.GetPriority() > other.m_receipt.GetPriority())
	//	return true;
	//else if (m_receipt.GetPriority() < other.m_receipt.GetPriority())
	//	return false;
	//else //if (m_receipt.GetPriority() == other.m_receipt.GetPriority())
	//	return (m_slot > other.m_slot);
}

So far, neither of these approaches led to the queue maintaining FIFO order (perhaps I've implemented the operator wrong?).

Thanks.

Here's an example. It seems you need to implement operator(). I guess that's because the priority could go either way, greater or less.

I have implemented the proper operator for it to compile. I know how to use the queue, but I can't get it to maintain FIFO order. The example doesn't really help; it's too simple.

Hrm. Still can't get it to work:

Code:

auto queue_place = std::make_shared<XQueueItem>(receipt, m_Id++, receipt.GetPriority());

XQueueItem(XStationReceipt& receipt, unsigned long long slot, int priority): m_receipt(receipt), m_slot(std::make_pair(priority, slot)) {}

std::pair<int, unsigned long long> m_slot;

bool operator > (const XQueueItem& other)
{
	return m_slot > other.m_slot;
}

queue.m_Queue.pop();

(Yes, it calls the struct operator >, and not the shared_ptr operators.)

Are the priorities arbitrary or limited to a small set? If there are a limited number of priorities, I'd just make a plurality of simple FIFOs, one for each priority.

Still can't get it to work

Then you've done something wrong, and you didn't post enough for me to guess what that might be.

*shrug*

Pick an order and figure out what you need to do to fix your problem.

[Edit]
Removed a few lines I had added to test the other sort order.
[/Edit]

Soma

Code:

#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>

typedef std::pair<int, std::pair<int, int> > QueueItem;

struct SorterOne
{
    bool operator ()
    (
        const QueueItem & fLHS
      , const QueueItem & fRHS
    )
    {
        return(fLHS.second < fRHS.second);
    }
};

struct SorterTwo
{
    bool operator ()
    (
        const QueueItem & fLHS
      , const QueueItem & fRHS
    )
    {
        if(fLHS.second.first == fRHS.second.first)
        {
            return(fLHS.second.second > fRHS.second.second);
        }
        else
        {
            return(fLHS.second.first < fRHS.second.first);
        }
    }
};

template
<
    typename FQueue
>
void Build
(
    FQueue & fData
)
{
    using namespace std;
    int lStamp(0);
    fData.push(make_pair(0, make_pair(3, ++lStamp)));
    fData.push(make_pair(1, make_pair(1, ++lStamp)));
    fData.push(make_pair(2, make_pair(1, ++lStamp)));
    fData.push(make_pair(3, make_pair(3, ++lStamp)));
    fData.push(make_pair(4, make_pair(3, ++lStamp)));
    fData.push(make_pair(5, make_pair(3, ++lStamp)));
    fData.push(make_pair(6, make_pair(2, ++lStamp)));
    fData.push(make_pair(7, make_pair(2, ++lStamp)));
}

template
<
    typename FQueue
>
void Dump
(
    FQueue & fData
)
{
    using namespace std;
    while(!fData.empty())
    {
        const QueueItem & lTop(fData.top());
        cout << lTop.first << ':' << '(' << lTop.second.first << ',' << lTop.second.second << ')' << '\n';
        fData.pop();
    }
}

int main
(
    int argc
  , char ** argv
)
{
    using namespace std;
    if((2 == argc) && string("one") == argv[1])
    {
        priority_queue<QueueItem, vector<QueueItem>, SorterOne> lData;
        Build(lData);
        Dump(lData);
    }
    else if((2 == argc) && string("two") == argv[1])
    {
        priority_queue<QueueItem, vector<QueueItem>, SorterTwo> lData;
        Build(lData);
        Dump(lData);
    }
    else
    {
        priority_queue<QueueItem> lData;
        Build(lData);
        Dump(lData);
    }
    return(0);
}

Fixed. Borrowing your code and using it as a model, I investigated the problem, seeming as it did not appear in your test code.
It turns out that the queue stores items in some weird order. They can appear in some in-order way (element 0 first, then element 1, and so on), and in some weird-order way which happened after a pop. But printing out the contents of the queue proved that the FIFO order was preserved, thankfully.
So now it works, and I should be finished. Finally...

Thanks for every comment, ideas and help.

The debugger was doing something weird--or the internal representation of the container became weird. The order of the elements, shows from 0 to n, was in order before the pop and became out of order after the pop when peeking in the debugger. But the output was fine before and after when just fetching the first element in the queue and popping, like you did.

Definitely heapify from what I could see from the source. Perhaps it doesn't heapify until you actually try to get something out of the queue or something. Well, it threw me off, so remember all your programmers out there: don't trust the debugger too much!