链表可以当成双端队列来使用——至少在渐进时空复杂度上，它们是相同的。
但在现代化的 CPU 的支持下，std::vector 由于内存的连贯性，在小规模数据下甚至可以做到比 std::deque 更好的性能，更别提在随机访问上 std::vector 有巨大优势了。
灵感来源： C++ list vs vector 性能测试 - 君实的文章 - 知乎 https://zhuanlan.zhihu.com/p/1888283969994336101
测试代码：
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <list>
#include <string>
#include <type_traits>
#include <vector>
constexpr int TEST_ITERS = 100000;
template <typename T>
requires std::is_same_v<T, std::list<int>> ||
std::is_same_v<T, std::vector<int>> ||
std::is_same_v<T, std::deque<int>>
void test_for(const char *name, int count) {
auto t_0 = std::chrono::system_clock::now();
T container;
for (int i = 0; i < count; i++) {
container.push_back(i);
}
auto t_initialized = std::chrono::system_clock::now();
for (int i = 0; i < TEST_ITERS; i++) {
int elem = rand() % count;
auto iter = std::ranges::find(container, elem);
container.erase(iter);
container.push_back(elem);
}
auto t_random_test = std::chrono::system_clock::now();
for (int i = 0; i < TEST_ITERS; i++) {
auto elem = *container.begin();
container.erase(container.begin());
container.push_back(elem);
}
auto t_pop_front_test = std::chrono::system_clock::now();
std::cout << "====================================================\n"
<< "test final for " << name << " with count: " << count << "\n"
<< "\ttime_init = " << t_initialized - t_0 << "\n"
<< "\ttime_random_erase = " << t_random_test - t_initialized << "\n"
<< "\ttime_pop_front = " << t_pop_front_test - t_random_test << "\n"
<< std::endl;
}
template <typename T> void test_for_str(const char *name, int count) {
auto t_0 = std::chrono::system_clock::now();
T container;
for (int i = 0; i < count; i++) {
container.push_back(std::to_string(i));
}
auto t_initialized = std::chrono::system_clock::now();
for (int i = 0; i < TEST_ITERS; i++) {
auto elem = *container.begin();
container.erase(container.begin());
container.push_back(elem);
}
auto t_pop_front_test = std::chrono::system_clock::now();
std::cout << "====================================================\n"
<< "test final for " << name << " with count: " << count << "\n"
<< "\ttime_init = " << t_initialized - t_0 << "\n"
<< "\ttime_pop_front = " << t_pop_front_test - t_initialized << "\n"
<< std::endl;
}
int main() {
test_for<std::vector<int>>("std::vector<int>", 16);
test_for<std::list<int>>("std::list<int>", 16);
test_for<std::deque<int>>("std::deque<int>", 16);
test_for<std::vector<int>>("std::vector<int>", 256);
test_for<std::list<int>>("std::list<int>", 256);
test_for<std::deque<int>>("std::deque<int>", 256);
test_for<std::vector<int>>("std::vector<int>", 4096);
test_for<std::list<int>>("std::list<int>", 4096);
test_for<std::deque<int>>("std::deque<int>", 4096);
test_for<std::vector<int>>("std::vector<int>", 32768);
test_for<std::list<int>>("std::list<int>", 32768);
test_for<std::deque<int>>("std::deque<int>", 32768);
test_for_str<std::vector<std::string>>("std::vector<std::string>", 16);
test_for_str<std::list<std::string>>("std::list<std::string>", 16);
test_for_str<std::deque<std::string>>("std::deque<std::string>", 16);
test_for_str<std::vector<std::string>>("std::vector<std::string>", 256);
test_for_str<std::list<std::string>>("std::list<std::string>", 256);
test_for_str<std::deque<std::string>>("std::deque<std::string>", 256);
test_for_str<std::vector<std::string>>("std::vector<std::string>", 8192);
test_for_str<std::list<std::string>>("std::list<std::string>", 8192);
test_for_str<std::deque<std::string>>("std::deque<std::string>", 8192);
test_for_str<std::vector<std::string>>("std::vector<std::string>", 32768);
test_for_str<std::list<std::string>>("std::list<std::string>", 32768);
test_for_str<std::deque<std::string>>("std::deque<std::string>", 32768);
}
测试输出
====================================================
test final for std::vector<int> with count: 16
time_init = 4500ns
time_random_erase = 2478100ns
time_pop_front = 548300ns
====================================================
test final for std::list<int> with count: 16
time_init = 2200ns
time_random_erase = 4760000ns
time_pop_front = 2577000ns
====================================================
test final for std::deque<int> with count: 16
time_init = 1300ns
time_random_erase = 3194600ns
time_pop_front = 938800ns
====================================================
test final for std::vector<int> with count: 256
time_init = 4300ns
time_random_erase = 5934600ns
time_pop_front = 1134400ns
====================================================
test final for std::list<int> with count: 256
time_init = 27900ns
time_random_erase = 19486100ns
time_pop_front = 2807300ns
====================================================
test final for std::deque<int> with count: 256
time_init = 13300ns
time_random_erase = 10613400ns
time_pop_front = 980900ns
====================================================
test final for std::vector<int> with count: 4096
time_init = 43400ns
time_random_erase = 190562800ns
time_pop_front = 313020900ns
====================================================
test final for std::list<int> with count: 4096
time_init = 134500ns
time_random_erase = 634532100ns
time_pop_front = 3362300ns
====================================================
test final for std::deque<int> with count: 4096
time_init = 6900ns
time_random_erase = 99171000ns
time_pop_front = 879800ns
====================================================
test final for std::vector<int> with count: 32768
time_init = 81800ns
time_random_erase = 1844930700ns
time_pop_front = 2943559900ns
====================================================
test final for std::list<int> with count: 32768
time_init = 902000ns
time_random_erase = 6683027100ns
time_pop_front = 3578600ns
====================================================
test final for std::deque<int> with count: 32768
time_init = 69700ns
time_random_erase = 790749400ns
time_pop_front = 886100ns
====================================================
test final for std::vector<std::string> with count: 16
time_init = 3100ns
time_pop_front = 3449700ns
====================================================
test final for std::list<std::string> with count: 16
time_init = 1800ns
time_pop_front = 2865500ns
====================================================
test final for std::deque<std::string> with count: 16
time_init = 17200ns
time_pop_front = 672300ns
====================================================
test final for std::vector<std::string> with count: 256
time_init = 147700ns
time_pop_front = 48857700ns
====================================================
test final for std::list<std::string> with count: 256
time_init = 19900ns
time_pop_front = 2907400ns
====================================================
test final for std::deque<std::string> with count: 256
time_init = 5600ns
time_pop_front = 758500ns
====================================================
test final for std::vector<std::string> with count: 8192
time_init = 254700ns
time_pop_front = 1175939400ns
====================================================
test final for std::list<std::string> with count: 8192
time_init = 303600ns
time_pop_front = 2826500ns
====================================================
test final for std::deque<std::string> with count: 8192
time_init = 172300ns
time_pop_front = 646900ns
====================================================
test final for std::vector<std::string> with count: 32768
time_init = 679900ns
time_pop_front = 5407818600ns
====================================================
test final for std::list<std::string> with count: 32768
time_init = 1202400ns
time_pop_front = 3050200ns
====================================================
test final for std::deque<std::string> with count: 32768
time_init = 639600ns
time_pop_front = 712600ns
分析测试数据可以发现，在 16 和 256 的 int 数据这样极小的数据中，已知迭代器的擦写 vector<int> 甚至可以比 deque<int> 还快，更别提 cache miss 吃满的 list<int>。
但是在 std::string 的容器中，由于 string 移动常数明显地比 int 大很多，即使是 16 这样的小容器也是 vector 更慢一些。
对于常用的 先 find 再 remove （即，remove-if）的过程，更是很难说有什么不用 vector 的理由。直到 4096 这样的数字，vector 随机删除会移动后续所有元素的性质才开始与 deque 拉开距离。deque<int> 在 256 的时候随机删除仍然不如 vector<int>
而链表，顺序迭代的速度更是费拉不堪，比 vector 和 deque 可能慢 3 倍有余。
链表在工程上已经失去了绝大多数的用武之地。
或许只有你需要保持迭代器的有效性的同时，还要在已知迭代器的情况下进行随机删除的时候 std::list 是一个不错的选择。
版权声明： CC BY-SA 4.0