DrumGizmo
DGEdit
General
We are proud members of:
DrumGizmo sponsors:
Congratulations GNU
We are proud members of:
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| dev:event_data_structure [2020/01/11 19:13] – chaot | dev:event_data_structure [2020/01/11 23:56] (current) – chaot | ||
|---|---|---|---|
| Line 3: | Line 3: | ||
| This page is to make a suggestion for a new events data structure to achieve the following goals: | This page is to make a suggestion for a new events data structure to achieve the following goals: | ||
| * avoid the usage of std::list | * avoid the usage of std::list | ||
| - | * store events such that we can quickly retrieve the k-th last event for a specific instrument (for fixed k) | + | * store events such that we can quickly retrieve the k-th last event for a specific instrument (for variable |
| * generally make this part of the code more beautiful and usable | * generally make this part of the code more beautiful and usable | ||
| + | |||
| + | === Abstraction === | ||
| + | |||
| + | Currently we just use a plain std:: | ||
| + | |||
| + | === 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, | ||
| + | |||
| + | === Misc Comments === | ||
| + | |||
| + | * The list currently contains pointers because of polymorphism of Event. | ||
| + | * IRC conversation: | ||
| + | |||