选std::vector更优：频繁随机访问、遍历或数据量固定时，其连续内存带来o(1)查找和高缓存命中率；std::list仅在高频中间插入/删除且不需随机访问时才可能胜出，但实际中vector配合reserve()和erase-remove通常性能更好。
选数组还是链表，关键看操作模式：如果频繁按位置读取、遍历多、数据量固定，std::vector（底层是动态数组）几乎总是更优；如果高频在任意位置插入/删除，且不关心随机访问，才值得考虑std::list（双向链表）。
为什么 std::vector 查找快但插入慢
数组内存连续，vec[i] 只需地址偏移，O(1) 完成；但insert() 或 erase() 在中间位置时，后续所有元素都要拷贝移动——10 万个元素时，一次中间插入可能触发数万次拷贝。即使使用emplace_back()追加，若触发扩容，仍要整体搬迁旧数据。
- 连续内存带来 CPU 缓存友好，遍历速度常比链表快 3–5 倍
-
reserve()预分配可避免多次扩容，但无法解决中间插入的移动开销 - 指针/引用在插入后可能失效（因内存重分配），而链表节点地址稳定
为什么 std::list 插入快但遍历慢
每个节点独立堆分配，insert() 只需改两个指针（前驱和后继），O(1)；但operator[] 不存在，std::list::at() 是线性查找，O(n)。遍历时 CPU 缓存命中率极低——节点散落在堆各处，每次跳转都可能触发缓存未命中。
- 节点额外占 8–16 字节（指针 + 对齐），小对象（如
int）空间开销翻倍以上 -
splice()搬运子链表是真正O(1)，但多数场景用不到 - 迭代器稳定：插入/删除不使其他迭代器失效（
std::vector中仅尾后迭代器保证有效）
std::vector 和 std::list 的真实性能拐点在哪
没有统一阈值，但经验上：单次插入/删除频次超过总元素数的 1% 且集中在中间位置时，std::list 才可能显出优势；而只要涉及大量遍历、排序、二分查找或需要 & 取地址，std::vector 几乎必胜。C++ 标准库实现中，std::list 的构造、析构、内存分配成本远高于 std::vector。
- 现代编译器对
std::vector的循环常做向量化优化，链表完全无法受益 -
std::deque是折中选择：分段连续，首尾插入O(1)，随机访问O(1)，但中间操作仍是O(n) - 真要高频任意位置增删，应先确认是否能用索引压缩（如
std::vector<bool></bool>）、延迟删除（标记+批量清理）或换用跳表等结构
实际项目里，90% 以上本想用链表的场景，换成带 reserve() 和批量操作的 std::vector，配合移动语义和 erase-remove 惯用法，性能反而更好——链表的“理论优势”常被内存分配、缓存缺失和间接寻址吃掉。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
