Port curve container types to `std::vector`

[heinezen]

So far, we have used std::list as the underlying type for curve containers. Lists are nice because they offer constant time insertions and erasure from anywhere in the data structure and have stable iterators, i.e. changing the list doesn't invaliate the iterators.

However, these properties may not be as important for our applications and std::vector could be better for performance under these assumptions:

• As elements in the curve are sorted by simulation time, insertions will like be at the end of the container in normal gameplay situations
• Random access for reading elements is likely used more than insertion/removal
• Copying the curve container, e.g. when passing the curve over thread boundaries, would put the the contigious memory layout of std::vector at an advantage over std::list

This PR changes the underlying container type of KeyframeContainer and Queue to std::vector to show that its usage is possible with minimal changes.

[TheJJ]

how about std::deque? especially since we probably can't retain all events for the whole game and need to either serialize/forget them at earlier times

[heinezen]

@TheJJ std::deque is not contigous which might not be as great for hot code. The faster removal of elements at the front is nice but I don't know how often this would happen in a standard game compared to the other operations.

[TheJJ]

we can test/benchmark when it gets relevant, and we can easily swap it hopefully ^^ the deque isn't fully continuous but i think around 100 elements are, so its a mixture of the list and vector as far as i remember. but yea we can vector it for now i guess

[heinezen]

As long as we get rid of the list, it should be an improvement either way :D

[TheJJ]

then why not try the deque? :) should definitely be an improvement for the regular use-cases

[heinezen]

I've created a new branch in https://github.com/SFTtech/openage/pull/1637 to preserve the changes from this PR. We could still switch to vector in the future :)

[heinezen]

After a quick detour with https://github.com/SFTtech/openage/pull/1637 I think using vector is the better choice :D Iterator stability for std::deque is only guaranteed for insertion/erasure at the front and end, so caching would become more complicated in many situations. In comparison, the std::vector implementation uses indices which only require simple bounds checks to make sure that the cached index ist still in range.

I also found a C++ benchmark – std::vector VS std::list VS std::deque which compares the standard containers performance. Looks like vector is still not that much slower than deque, even for random inserts.

[heinezen]

It's ready to review again!