0

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.
smörkex
  • 336
  • 3
  • 18
  • For requirements 1 and 2, its funny that you did not explore `std::set`, and `std::priority_queue` – WhiZTiM May 07 '17 at 21:40
  • Ah thanks! Didn't put enough effort into it. Do these containers preserve pointers to existing elements after inserting? – smörkex May 07 '17 at 21:43
  • 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 May 07 '17 at 21:45
  • I don't really see the problem with `std::list` there. How are events *constant* after creating them? – Galik May 07 '17 at 21:52
  • @Kurt `std::deque` only preserves pointers when adding/removing to the front or the back, not in the middle. – Galik May 07 '17 at 22:00
  • @Galik you are right on both points - not sure how I managed it but I confused set and list – smörkex May 07 '17 at 22:08
  • @Galik the true cost of a list then is that it does not order the elements automatically - is that correct? – smörkex May 07 '17 at 22:10
  • @Kurt Thinking about this I would probably go for something like `std::vector> events;` For the main list and then use `std::weak_ptr` for repeat/related events: `std::vector> repeats;`. Then you get good searching with stable pointers. – Galik May 07 '17 at 22:27
  • By 'time ordering' do you mean wall clock (i.e. time(0)) or something else. An embedded system I worked on fetched the current time of day (from the configured clock source ip) shortly after start-up, but sometimes not before a third party 'time' scheduler acquired some entries. 'spring forward' (or maybe it was 'fall back') broke that system start up, but only once a year. Be sure to specify. – 2785528 May 08 '17 at 01:27

1 Answers1

1
  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).

Community
  • 1
  • 1
WhiZTiM
  • 21,207
  • 4
  • 43
  • 68
  • I did not know about `merge,extract` - thanks! I guess that is the cleanest way to handle "rescheduling" in an ordered container without having to construct a new element - is that correct? Or is there some structure that "under the hood" does something more efficient than a `extract/insert` operation? – smörkex May 07 '17 at 22:16
  • 1
    @Kurt, yes that is correct. `extract/merge` are more efficient because, it only removes/merge the internal node of the container. Your object remains untouched when extracted or merged. `extract/merge` is way better than `erase/insert` – WhiZTiM May 07 '17 at 22:21