priority_queues or not?

[lallous]

Hello

I have a design / C++ question, hope you can help me.

class interface1
{
protected:
int _priority;
public:
virtual ~interface1() { };
interface1(int priority) { _priority = priority; }
virtual void on_event() { }
};

Now users can subclass this interface and override the on_event().

Now I have an std::list<interface *>

However, the std::list does not sort the elements.
Thus I want to use an std::set<> instead that will sort the "interface1 *",
providing it with a comparison function that will sort according to
priority, so that later I can iterate in a sorted manner.

I would have used priority_queue, however I want to be able to register and
unregister arbitrary interfaces.
std::set allows one to remove and insert anywhere.

Please advise.

 

[Bernd Strieder]

Hello,

I have a design / C++ question, hope you can help me.

class interface1
{
protected:
int _priority;
public:
virtual ~interface1() { };
interface1(int priority) { _priority = priority; }
virtual void on_event() { }
};

Now users can subclass this interface and override the on_event().

Now I have an std::list<interface *>

However, the std::list does not sort the elements.
Thus I want to use an std::set<> instead that will sort the
"interface1 *", providing it with a comparison function that will sort
according to priority, so that later I can iterate in a sorted manner.

I would have used priority_queue, however I want to be able to
register and unregister arbitrary interfaces.
std::set allows one to remove and insert anywhere.

Please advise.

priority_queue is meant for a situation, where a set of elements is
moved through the queue, i.e. they are queued and some time later they
are unqueued. priority_queue maintains a certain order only when
removing the elements one by one. I think you intend to use your set of
elements repeatedly, this means you would have to recreate the priority
queue each time you need it. So priority queue seems not to be the
right tool.

My suggestion is map, i.e. removing the priority from interface1, and
using a map from priority to interface1 pointers as sorted structure.

class interface1
{
public:
virtual ~interface1() { };
virtual void on_event() { }
};

std::map<int,interface1*> on_event_listeners;

map supports inserting and erasing everywhere.

Assigning priorities to certain implementations of interface1 has been
left open in the code above, but in the end the OP has left it open as
well.

You have several tasks, the on_event implementations, assigning
priorities to them, and maintaining lists of implementations, which
should be separated from each other.

Bernd Strieder

 

[Daniel T.]

Hello

I have a design / C++ question, hope you can help me.

class interface1
{
protected:
int _priority;
public:
virtual ~interface1() { };
interface1(int priority) { _priority = priority; }
virtual void on_event() { }
};

Now users can subclass this interface and override the on_event().

Now I have an std::list<interface *>

However, the std::list does not sort the elements.
Thus I want to use an std::set<> instead that will sort the "interface1 *",
providing it with a comparison function that will sort according to
priority, so that later I can iterate in a sorted manner.

Are you saying you don't want to remove the items as you are processing
them? If that's the case, then I agree with you.

I would have used priority_queue, however I want to be able to register and
unregister arbitrary interfaces.

What? I don't understand what you mean here...

std::set allows one to remove and insert anywhere.

No it doesn't. It requires items to be sorted. If you provide a pred
that sorts by _priority, then they must be in _priority order. Also, set
doesn't allow two items with the same _priority to exist. Also, set
doesn't allow modification of the contained elements. (However, since
the elements contained are pointers, that's probably not an issue.)

Please advise.

I have to agree with Bernd, although I think you would be better served
by a multimap<int, interface*> so that several things can have the same
priority.

Now, one might ask, "why rip the priority out of the class?" I suspect
that 'priority' is not an intrinsic property of objects of the class,
but instead a relation between two objects of the same class in the
particular environment they are currently being used in. When dealing
with a single object, the priority becomes nonsensical.

 

[lallous]

Hello Bernd,

Hello,


priority_queue is meant for a situation, where a set of elements is
moved through the queue, i.e. they are queued and some time later they
are unqueued. priority_queue maintains a certain order only when
removing the elements one by one. I think you intend to use your set of
elements repeatedly, this means you would have to recreate the priority
queue each time you need it. So priority queue seems not to be the
right tool.

My suggestion is map, i.e. removing the priority from interface1, and
using a map from priority to interface1 pointers as sorted structure.

class interface1
{
public:
virtual ~interface1() { };
virtual void on_event() { }
};

std::map<int,interface1*> on_event_listeners;

map supports inserting and erasing everywhere.

Assigning priorities to certain implementations of interface1 has been
left open in the code above, but in the end the OP has left it open as
well.

You have several tasks, the on_event implementations, assigning
priorities to them, and maintaining lists of implementations, which
should be separated from each other.

How do you suggest I managed priorites with an std::map ?
It is true that map can add/remove items on demand, however, the keys are
not sorted, unlike an std::set.

So the best thing is to use an std::set<interface1_ptr> with custom compare
functor?

 

[Jeff Flinn]

lallous wrote:


....

It is true that map can add/remove items on demand, however, the keys
are not sorted, unlike an std::set.

Are too!

Jeff

 

[lallous]

Hello

Are you saying you don't want to remove the items as you are processing
them? If that's the case, then I agree with you.

Yes, processing is done when a given event is triggered.
Removing is done when a certain client decides to unregister from the list
(by providing the "interface1 *").

What? I don't understand what you mean here...

Doesn't priority_queue require you to extract only the top item?
But I may want to remove a given handler by its pointer value, and don't
think priority_queue would allow me to remove any item but the top one.

No it doesn't. It requires items to be sorted. If you provide a pred
that sorts by _priority, then they must be in _priority order. Also, set
doesn't allow two items with the same _priority to exist. Also, set
doesn't allow modification of the contained elements. (However, since
the elements contained are pointers, that's probably not an issue.)

You mean that std::set will allow you to remove any item from anywhere, and
it will re-sort again?

I have to agree with Bernd, although I think you would be better served
by a multimap<int, interface*> so that several things can have the same
priority.

I didn't understand how I can implement my requirement using a map or
multimap.

Can you elaborate more on this idea please?

Currently, I am relying on std::set<interface1 *> which are sorted based on
their _priority member.
So when I process the 'set', the elements with highest priority will be
processed first.

But do maps maintain a certain sorting that is reliable and when iterated it
will yield items in my desired order? (highest priority elements first and
least at last)

Now, one might ask, "why rip the priority out of the class?" I suspect
that 'priority' is not an intrinsic property of objects of the class,
but instead a relation between two objects of the same class in the
particular environment they are currently being used in. When dealing
with a single object, the priority becomes nonsensical.

You are correct, priority is used only to define a certain order
relationship and is nonesensical when an object is used alone.
But I wanted a self-contained structure that will allow one to insert items
and sort them by order.

 

[Fei Liu]

Hello


Yes, processing is done when a given event is triggered.
Removing is done when a certain client decides to unregister from the list
(by providing the "interface1 *").


Doesn't priority_queue require you to extract only the top item?
But I may want to remove a given handler by its pointer value, and don't
think priority_queue would allow me to remove any item but the top one.


You mean that std::set will allow you to remove any item from anywhere, and
it will re-sort again?

You probably should read some STL document first before you make any design
decision. It seems you are not very familiar with the STL classes.