efficient priority queue for a few descrete priority levels

Discussion in 'C++' started by Marcel Müller, Apr 26, 2009.

  1. Hi,

    I seek for a standard solution for a priority queue with the following
    properties:

    - a limited and small number of priorities
    (constructor argument or template parameter)
    - multiple writers
    - multiple readers
    - insert O(1)
    - remove O(1)
    - support for dedicated high priority readers that only handle requests
    up to a certain priority level
    - support for rollback (for readers only)

    std::priority_queue has O(log n) and therefore does not fit.


    Marcel
    Marcel Müller, Apr 26, 2009
    #1
    1. Advertising

  2. Marcel Müller

    red floyd Guest

    Marcel Müller wrote:
    > Hi,
    >
    > I seek for a standard solution for a priority queue with the following
    > properties:
    >
    > - a limited and small number of priorities
    > (constructor argument or template parameter)
    > - multiple writers
    > - multiple readers
    > - insert O(1)
    > - remove O(1)
    > - support for dedicated high priority readers that only handle requests
    > up to a certain priority level
    > - support for rollback (for readers only)
    >
    > std::priority_queue has O(log n) and therefore does not fit.
    >


    comp.algorithms?
    red floyd, Apr 26, 2009
    #2
    1. Advertising

  3. Hi,

    Sam wrote:
    > Given that your number of priorities is limited, all you need is a
    > std::list for each individual priority.
    >
    > An object's priority selects its std::list. A push and a pop on a
    > std::list is O(1).


    oops, I think was too fixed on a single list with uncommitted items
    still in the list and did not see the obvious solution.
    All I have to do is to adjust the reader interface in the way, that it
    starts looking at the highest priority, and the writer in a way that it
    also signals readers with a lower priority limit. I think even a single
    linked list should be fine, since push_back, pop_front and push_front
    (for rollback) are O(1) for simple Head/Next/Tail lists too. And if I
    join the lists the reader does no longer need to search all higher
    priority lists each time. It only has to check for the individual tail
    pointer corresponding to it's priority level.
    Thanks for pushing me back to the right way.


    Marcel
    Marcel Müller, Apr 27, 2009
    #3
  4. red floyd wrote:
    > comp.algorithms?


    You are right, I did not know of this group so far. However, Sam already
    put me in the right direction this time.


    Marcel
    Marcel Müller, Apr 27, 2009
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Navhpf

    priority queue

    Navhpf, Feb 23, 2004, in forum: Java
    Replies:
    3
    Views:
    991
    Navhpf
    Feb 23, 2004
  2. Tobias Merler
    Replies:
    0
    Views:
    816
    Tobias Merler
    Oct 7, 2004
  3. Aaron W. LaFramboise

    Stable priority queue

    Aaron W. LaFramboise, Apr 5, 2004, in forum: C++
    Replies:
    19
    Views:
    1,540
    Claudio Puviani
    Apr 7, 2004
  4. Russell Warren

    Is Queue.Queue.queue.clear() thread-safe?

    Russell Warren, Jun 22, 2006, in forum: Python
    Replies:
    4
    Views:
    678
    Russell Warren
    Jun 27, 2006
  5. Kris
    Replies:
    0
    Views:
    478
Loading...

Share This Page