Re:Implementing Mario's Stack Blur 15 times in C++ (with tes...
by sudara on Friday November 10, 2023 @02:48PM
(#38223612)
Thanks for this!
Re:Implementing Mario's Stack Blur 15 times in C++ (with tes...
by vitus on Friday November 10, 2023 @05:09PM
(#38225200)
> std::deque will never beat your hand-rolled ring buffer.
std::deque may never beat a hand-rolled ring buffer of fixed size that maintains cursors, but it will beat a hand-rolled linked-list implementation.
The typical implementation will generally exhibit better cache locality than a linked list, and will outperform it for random access as required by the specification (amortized constant, vs linear).
(The typical implementation per cppreference, although I don't think this is formally required by the spec, is a sequence of fixed-length arrays.)
Re:Implementing Mario's Stack Blur 15 times in C++ (with tes...
by klyrs on Saturday November 11, 2023 @12:30PM
(#38232369)
After some thought, I figured out a way to implement a chunked array of the sort specified by the c++ standard library, which does not require reallocation if the queue length stays below the chunksize. It involves storing cyclic offsets for each chunk.
So what I wrote isn't quite correct about needing to fiddle with memory regardless. But there is still overhead -- even if there's well-optimized code for the single chunk case, the container needs to check that condition.
* for your purpose! Therein lies the challenge of writing standard libraries... choices must be made.