std::vector的operator[]是O(1)，但std::find仍是O(n)；查找值需遍历，虽缓存友好而实际更快，但复杂度未变；std::list不支持operator[]，查找和随机访问均为O(n)且更慢。
std::vector 的 operator[] 是 O(1)，但 std::find 仍是 O(n)
很多人误以为 std::vector “因为连续内存所以查找快”，其实只对**按索引随机访问**成立。如果你在找某个值（比如 std::find(vec.begin(), vec.end(), x)），它和 std::list 一样，都得逐个比对，时间复杂度都是 O(n)。区别在于：std::vector 的每次内存访问更友好——CPU 缓存命中率高，实际运行往往快 2–5 倍；而 std::list 每次跳转都要读新内存页，cache miss 频繁。
std::list 根本不支持随机访问，operator[] 不存在
std::list 是双向链表，没有下标运算符。写 lst[5] 直接编译失败，错误信息类似：Error: no match for 'operator[]'。想取第 n 个元素？只能用 std::next(lst.begin(), n)，这会从头开始走 n 步，是 O(n) —— 而且每一步都是非连续指针解引用，性能远差于 std::vector 的地址偏移。
查找性能真正拉开差距的场景：带排序或需频繁插入/删除中间
如果数据天然有序，又常做查找，别硬刚 std::vector 或 std::list —— 改用 std::set（红黑树，O(log n) 查找）或排序后配 std::binary_search（O(log n) + O(n log n) 预处理）。若必须用序列容器且要高频中间插入/删除，std::list 的 O(1) 插删优势才可能抵消它 O(n) 查找的劣势；但一旦查找变多，整体反而更慢。
- 查得多、改得少 → 优先
std::vector+ 排序 +std::binary_search - 改得多（尤其中间）、查得少 →
std::list才有存在意义 - 既查又改还要求稳定 O(log n) → 直接换
std::set或std::unordered_set
一个实测差异明显的例子
在 10 万整数中查找末尾元素：
立即学习“C++免费学习笔记（深入）”；
#include #include #include #include std::vector v(100000, 0); v.back() = 999; std::list l(v.begin(), v.end()); auto t1 = std::chrono::high_resolution_clock::now(); std::find(v.begin(), v.end(), 999); auto t2 = std::chrono::high_resolution_clock::now(); std::find(l.begin(), l.end(), 999); auto t3 = std::chrono::high_resolution_clock::now(); // 在典型机器上，t2-t1 通常为 10–30μs，t3-t2 为 150–400μs
差距主要来自内存局部性，不是算法阶数——这点容易被忽略。