Priority queue and FIFO

This is a discussion on Priority queue and FIFO within the C++ Programming forums, part of the General Programming Boards category; Hello all, I am looking for a solution on how to order a queue with priority. Simply put, my requirements ...

  1. #1
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,668

    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  3. #3
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,668
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,282
    For any given implementation, you might get it to work directly, but in general, there is nothing you can do to change how the implementation behaves.

    `std:riority_queue' is simply not guaranteed to be a stable priority queue. (They are more expensive and not necessary for a general purpose priority queue.)

    What you can do is change your priority. Use a `std:air' with your current priority type as the major priority and an integer (e.g. time stamp) as the second priority.

    Soma

  5. #5
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,668
    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.)
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,246
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  7. #7
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,668
    At the moment, there are only two. But, if possible, I would like to make it as generic as possible. The code for the current task can also be used the start of a great framework for synchronization problems.

  8. #8
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,282
    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);
    }
    Last edited by phantomotap; 02-28-2012 at 03:29 PM.

  9. #9
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,668
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  10. #10
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,282
    O_o

    I'm not entirely sure I understand the problem...

    *shrug*

    The client was just doing something weird?

    Soma

  11. #11
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,668
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #12
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,282
    Ah. I see.

    Well, I can't speak for how `std:riority_queue' behaves, but you may have been seeing a "heapify" operation or something.

    Soma

  13. #13
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,668
    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!
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with FIFO queue
    By Martin_T in forum C Programming
    Replies: 10
    Last Post: 11-08-2009, 09:30 AM
  2. understanding queue FIFO
    By arastoo.s in forum C Programming
    Replies: 6
    Last Post: 08-18-2009, 10:16 AM
  3. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 08:17 AM
  4. STL min priority queue?
    By *ClownPimp* in forum C++ Programming
    Replies: 7
    Last Post: 04-30-2006, 11:31 AM
  5. Priority Queue
    By Tostado in forum C++ Programming
    Replies: 1
    Last Post: 03-24-2004, 01:01 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21