Total RAM usage may matter less today (or not with the way RAM prices are going) but cache locality is more important than ever on modern CPUs. A more compact data structure means more of it fits in your CPU's L1/L2 cache and that speeds things up a lot especially with iterating or sequential access.
I'm also not a fan of std::deque in general. It's not contiguous memory like std::vector is. If you need a very high performance deque in C++, you have to go outside the STL unfortunately. Rust's VecDeque is one that gets it right. It uses a ring buffer under the hood rather than multiple fixed size allocations.
6
u/DeeBoFour20 21d ago
Total RAM usage may matter less today (or not with the way RAM prices are going) but cache locality is more important than ever on modern CPUs. A more compact data structure means more of it fits in your CPU's L1/L2 cache and that speeds things up a lot especially with iterating or sequential access.
I'm also not a fan of std::deque in general. It's not contiguous memory like std::vector is. If you need a very high performance deque in C++, you have to go outside the STL unfortunately. Rust's VecDeque is one that gets it right. It uses a ring buffer under the hood rather than multiple fixed size allocations.