Taming the performance Beast - Klaus Iglberger - Meeting C++ 2015
53 5 3672
Taming the performance Beast
Meeting C++ 2015
Meeting C++ 2016 Schedule: https://meetingcpp.com/index.php/schedule16.html
By anonymous 2017-09-20
std::deque is a far better option. Or if you had benchmarked std::deque and found its performance to be inadequate for your specific use, you could implement a circular buffer in a fixed size array, storing the index of the start of the buffer. When replacing an element in the buffer, you would overwrite the element at the start index, and then set the start index to its previous value plus one modulo the size of the buffer.
List traversal is very slow, as list elements can be scattered throughout memory, and vector shifting is actually surprisingly fast, as memory moves on a single block of memory are quite fast even if it is a large block.
The talk Taming The Performance Beast from the Meeting C++ 2015 conference might be of interest to you.