STL containers for event scheduler

0
votes

I'm trying to decide what container to use for an event scheduler. The requirements I'm trying to satisfy are:

  1. Events should be ordered by time, and are evaluated by getting the front of the scheduler, evaluating the event, and then deleting the front.
  2. Events can be inserted for any time (scheduled to be evaluated at any time in the future).
  3. It should be possible to have a pointer to an event that isn't changed if other elements are added to the scheduler. For example, while evaluating the current event, it may be necessary to also delete a future event. Knowledge about this future event should be implemented as a pointer.
  4. It should be possible to reschedule events, e.g. change their time to a future time.

What containers are possible?

  1. STL queue - does not allow events to be inserted anywhere (e.g. by time).
  2. STL vector - inserting new events into the vector can break pointers to existing events.
  3. STL list - events are constant after constructing, so rescheduling is not possible except by deleting an existing event and then creating a new one at a later time. Edit: confused this with STL set.

Are there other options? I have read that it is not generally recommended to create your own containers (e.g. linked lists) for efficiency.

Thanks for your advice!

Edit

From the comments, two further suggestions:

  1. STL set - elements are constant after inserting.
  2. STL priority_queue - depending on the choice of STL container (vector or deque), this can preserve pointers (deque does) after inserting, but only if inserting at either end. However, elements are constant after inserting.
1
c++eventsstl
For requirements 1 and 2, its funny that you did not explore std::set, and std::priority_queue - WhiZTiM
Ah thanks! Didn't put enough effort into it. Do these containers preserve pointers to existing elements after inserting? - smörkex
Edit: since std::priority_queue allows you to specify a container, which can be std::vector or std::deque from STL, then using std::deque would preserve pointers - smörkex
I don't really see the problem with std::list there. How are events constant after creating them? - Galik
@Kurt std::deque only preserves pointers when adding/removing to the front or the back, not in the middle. - Galik

1 Answers

1
votes
  1. Events should be ordered by time, and are evaluated by getting the front of the scheduler, evaluating the event, and then deleting the front.

Use either a std::priority_queue or a std::set.

  1. Events can be inserted for any time (scheduled to be evaluated at any time in the future).

Use either a std::priority_queue or a std::set.

  1. It should be possible to have a pointer to an event that isn't changed if other elements are added to the scheduler. For example, while evaluating the current event, it may be necessary to also delete a future event. Knowledge about this future event should be implemented as a pointer.

Use a std::set and rather than pointer to the stored elements, use iterators. They are not invalidated when an element is deleted from the set (except the iterator to the deleted element).

  1. It should be possible to reschedule events, e.g. change their time to a future time.

Use std::set; With C++17, you can splice (std::list::extract) the element you want, modify it's priority or so, then stick it back in (std::list::merge).