Events Data Structure

This page is to make a suggestion for a new events data structure to achieve the following goals:

  • avoid the usage of std::list
  • store events such that we can quickly retrieve the k-th last event for a specific instrument (for variable k)
  • generally make this part of the code more beautiful and usable

Abstraction

Currently we just use a plain std::list<Event*>. Probably we should give it a dedicated type to make the code clearer and also facilitate future refactoring and avoiding bugs. I suggest EventsDS as the type name.

Replacement of std::list

As the events don't need to be in a specific order, we can replace std::list by a std::vector using a standard technique of swapping the element to be removed to the back and doing a pop_back(). This is only possible if the swapping is cheap. Currently the std::list contains pointers, so swapping is cheap. Also Event contains only some bytes (something around 30 maybe), so swapping is also still reasonably cheap.

Access to the k-th last event

To access the k-th last event, we have two extreme (with respect to running time and memory tradeoff) options:

  • for each instrument store its last events
  • just give IDs to each event and then linearly search for the k-th largest ID

If we know that we only need the query for the k-th last event for specific instruments, we can restrict storing this information to those instruments.

Misc Comments

  • The list currently contains pointers because of polymorphism of Event.
  • IRC conversation: here
dev/event_data_structure.txt ยท Last modified: 2020/01/11 23:56 by chaot
Trace: event_data_structure
GNU Free Documentation License 1.3
Valid CSS Driven by DokuWiki Recent changes RSS feed Valid XHTML 1.0