How to Make C++ Code Run 90x Faster

Author of blog post compared random insertion / random deletion speed with vectors and lists of up to 100k elements, based on a talk by Bjarne Stroustroup: https://youtu.be/YQs6IC-vgmo

The surprising result is that vectors are MUCH (almost two orders of magnitude) faster at this than lists, altough your CS background would make you expect a result in the opposite direction.

From Bjarne's talk (very interesting) we see that for example finding a single element in the middle of a vector by linear search, and then having to move the subsequent 50k elements forward by one position, is still MUCH faster than finding that element in the linked list and performing the minor pointer surgery to remove it.

The reason is that the linked list traversal is accessing memory all over the show, while the linear and predictable vector traversal and memory copy is superbly handled by modern caching architectures, and hence so much faster.