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

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.

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.

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.

• The list currently contains pointers because of polymorphism of Event.
• IRC conversation: here