STL container advice

[brekehan]

I am implementing a event messaging system. Basically I do:

---update cycle---

processing/check for new events
allocate a new event
put it in a std::queue

Dispatch events
make an event equal to std::queue.front()
pop an event from the std::queue
get its type
send it off to registered handlers

Now problem is that the handler may or may not process it. The handler
will return me a 0 if it was taken care of and a 1 if not. If the
event was not handled I want to leave it to be dispatched again next
update cycle. A std::queue only has a front() function, but no
iterator. So I cannot get the event, decide if I still want it or not,
then go to the next event without getting rid of the first. I cannot
iterate through and choose to erase handled events.

First I considered making another queue and putting unhandled events
into it then copying that queue to the original, but I think that
would be darn expensive, no?

I also considered using a vector instead of a queue, so I can iterate
through and erase as I need to, but isn't a vector more expensive,
especially since I am looking at the front and erasing in random
places?

Any other ideas for a more efficient event queue?

 

[Victor Bazarov]

I am implementing a event messaging system. Basically I do:

---update cycle---

processing/check for new events
allocate a new event
put it in a std::queue

Dispatch events
make an event equal to std::queue.front()
pop an event from the std::queue
get its type
send it off to registered handlers

Here you indicate that there are multiple handlers. Or have I
misunderstood and there is only one handler per event? That's not
clear.

Now problem is that the handler may or may not process it. The handler
will return me a 0 if it was taken care of and a 1 if not.

So, each handler can return 0 or 1, right? So, do you keep the event
if at least one handler returned 1 or throw it out if at least one
hanlder returned 0? That's not clear as well.

If the
event was not handled I want to leave it to be dispatched again next
update cycle.

Dispatched to whom? What happens to those handlers that have already
indicated that they "took care" of the event?

Now, if we presume that there is a single handler for each event, you
could simply delay popping the event from the queue until the handler
returns 0 ("taken care of"). Of course, it would stall processing of
all events following the one that needs to be delayed.

A std::queue only has a front() function, but no
iterator. So I cannot get the event, decide if I still want it or not,
then go to the next event without getting rid of the first. I cannot
iterate through and choose to erase handled events.

Why do you need a queue then? Just use a heap or a deque.

First I considered making another queue and putting unhandled events
into it then copying that queue to the original, but I think that
would be darn expensive, no?

It's unclear what that would serve. If you want to iterate over the
events in your container and pull out those you want, then how is that
a queue? The whole point of a queue is that the order of arrival is
of the utmost importance.

I also considered using a vector instead of a queue, so I can iterate
through and erase as I need to, but isn't a vector more expensive,
especially since I am looking at the front and erasing in random
places?

Yes, it is more expensive. Besides, std::queue is not a contaner.
It's a container _adapter_.

Any other ideas for a more efficient event queue?

Here you go again. Yours is not a queue, apparently. Otherwise you
wouldn't be asking those questions. Determine what you want and
only then try to pick the right container. Perhaps 'priority_queue'
is what you can use? Perhaps you need to write your own. Use
std::list, for example. Iterating is straightforward, removal is
swift, so are insertions. A bit more expensive in terms of memory,
but should still be fine.

V

 

[Mark P]

I am implementing a event messaging system. Basically I do:

---update cycle---

processing/check for new events
allocate a new event
put it in a std::queue

Dispatch events
make an event equal to std::queue.front()
pop an event from the std::queue
get its type
send it off to registered handlers

Now problem is that the handler may or may not process it. The handler
will return me a 0 if it was taken care of and a 1 if not. If the
event was not handled I want to leave it to be dispatched again next
update cycle. A std::queue only has a front() function, but no
iterator. So I cannot get the event, decide if I still want it or not,
then go to the next event without getting rid of the first. I cannot
iterate through and choose to erase handled events.

First I considered making another queue and putting unhandled events
into it then copying that queue to the original, but I think that
would be darn expensive, no?

I also considered using a vector instead of a queue, so I can iterate
through and erase as I need to, but isn't a vector more expensive,
especially since I am looking at the front and erasing in random
places?

Any other ideas for a more efficient event queue?

Your description is somewhat vague. Why can't you delay popping the
queue until after you've determined that the event was successfully
handled? Are you handling multiple events concurrently? If you really
need to put things back into the queue, have you looked at std::deque?

-Mark

 

[Sarath]

Your description is somewhat vague. Why can't you delay popping the
queue until after you've determined that the event was successfully
handled? Are you handling multiple events concurrently? If you really
need to put things back into the queue, have you looked at std::deque?

-Mark

To know more about dequeue
http://www.codeproject.com/vcpp/stl/vector_vs_deque.asp

 

[coosa]

I am implementing a event messaging system. Basically I do:

---update cycle---

processing/check for new events
allocate a new event
put it in a std::queue

Dispatch events
make an event equal to std::queue.front()
pop an event from the std::queue
get its type
send it off to registered handlers

Now problem is that the handler may or may not process it. The handler
will return me a 0 if it was taken care of and a 1 if not. If the
event was not handled I want to leave it to be dispatched again next
update cycle. A std::queue only has a front() function, but no
iterator. So I cannot get the event, decide if I still want it or not,
then go to the next event without getting rid of the first. I cannot
iterate through and choose to erase handled events.

First I considered making another queue and putting unhandled events
into it then copying that queue to the original, but I think that
would be darn expensive, no?

I also considered using a vector instead of a queue, so I can iterate
through and erase as I need to, but isn't a vector more expensive,
especially since I am looking at the front and erasing in random
places?

Any other ideas for a more efficient event queue?

Well I believe you would be needing operation where deletion could
occur in the middle of your queue; to such I believe a list is more
appropriate; lists supports forward and backward iteration; popping
form the front and the end of the list as well as deleting from the
middle of the list, but it's still confusing how your application is
performing.