efficient priority queue for a few descrete priority levels

[Marcel Müller]

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:riority_queue has O(log n) and therefore does not fit.


Marcel

 

[red floyd]

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:riority_queue has O(log n) and therefore does not fit.

comp.algorithms?

 

[Marcel Müller]

Hi,

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]

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