STL container advice

Discussion in 'C++' started by brekehan, Mar 13, 2007.

  1. brekehan

    brekehan Guest

    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?
    brekehan, Mar 13, 2007
    #1
    1. Advertising

  2. brekehan wrote:
    > 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
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Mar 14, 2007
    #2
    1. Advertising

  3. brekehan

    Mark P Guest

    brekehan wrote:
    > 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
    Mark P, Mar 14, 2007
    #3
  4. brekehan

    Sarath Guest

    On Mar 14, 9:10 am, Mark P <>
    wrote:
    > brekehan wrote:
    > > 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


    To know more about dequeue
    http://www.codeproject.com/vcpp/stl/vector_vs_deque.asp
    Sarath, Mar 14, 2007
    #4
  5. brekehan

    coosa Guest

    On Mar 14, 5:28 am, "brekehan" <> wrote:
    > 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.
    coosa, Mar 14, 2007
    #5
    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. Vivi Orunitia
    Replies:
    11
    Views:
    4,466
    Martijn Lievaart
    Feb 4, 2004
  2. Maitre Bart
    Replies:
    2
    Views:
    519
    Maitre Bart
    Feb 11, 2004
  3. Steven T. Hatton
    Replies:
    4
    Views:
    3,890
    Rob Williscroft
    Dec 5, 2004
  4. Replies:
    4
    Views:
    796
    Daniel T.
    Feb 16, 2006
  5. wolverine
    Replies:
    2
    Views:
    446
    Marcus Kwok
    Jul 24, 2006
Loading...

Share This Page