Why Choosing std::list May Not Be the Best Decision
Written on
Introduction to C++ Sequence Containers
In a recent analysis of C++ sequence containers, I explored their advantages and disadvantages, including various benchmarks. One finding was particularly surprising: the performance of std::list was significantly lower than expected. This prompted me to share insights on why std::list may not be the ideal choice for certain applications.
Benchmarks of std::list vs. std::vector and std::deque
Building on the results from my previous post, I decided to conduct further benchmarks to gain a more comprehensive understanding of these containers. Below is the code utilized for these benchmarks:
#include <benchmark/benchmark.h>
#include <list>
#include <vector>
#include <deque>
// Benchmark functions for vector, list, and deque
// ... (code remains unchanged)
The benchmark results were as follows:
In this video, we explore the implications of using "using namespace std" in C++ programming and why it's often seen as a poor practice.
Let's analyze the performance of the different containers based on the benchmark output:
Overview of Benchmark Results
The results from the benchmarks are as follows:
Benchmark Time CPU Iterations
BM_vector_push_back/8 16.0 ns 16.0 ns 42144195
BM_vector_push_back/64 130 ns 130 ns 5713682
BM_vector_push_back/4096 8397 ns 8396 ns 82078
BM_vector_push_back/65536 137274 ns 137268 ns 5603
BM_list_push_back/8 122 ns 122 ns 5516691
BM_list_push_back/64 667 ns 667 ns 1000000
BM_deque_push_back/8 12.4 ns 12.4 ns 58000329
The performance of pushing elements into a std::list is noticeably slower compared to std::vector. The best results were achieved with std::deque, which performed slightly better than std::vector.
Push and Pop Operations
For the pop_back operations:
Benchmark Time CPU Iterations
BM_vector_pop_back/8 0.000 ns 0.000 ns 1000000000
BM_list_pop_back/8 100 ns 100 ns 6795561
BM_deque_pop_back/8 7.23 ns 7.23 ns 98280521
The std::vector handles pop_back operations efficiently, while std::deque also outperforms std::list. This confirms that std::list is not the best option when it comes to performance.
In this video, we delve into the std::list template in C++, analyzing its features and use cases.
Why std::list Lags Behind
The underperformance of std::list can largely be attributed to cache misses. This is a well-documented phenomenon, and for an in-depth discussion, I recommend checking out Bjarne Stroustrup’s insights on the topic.
Conclusion
While std::list has its place, particularly for inserting elements in the middle of a sequence, it should generally be avoided in performance-critical scenarios. Instead, consider using std::vector or std::deque based on your specific requirements.