前言数据结构data structure这门课最容易上成背表格数组查找 O(1)、链表插入 O(1)、哈希表平均 O(1)、红黑树 O(log n)。背完表格遇到实际问题还是不知道怎么选。原理层面的数据结构其实是三件事的组合数据的物理布局——元素在内存里是挨着放还是各自散落、靠指针串起来不变量invariant——结构必须始终满足的约束比如左子树全部小于根、堆的父节点不小于子节点代价的分布——某个操作很快往往意味着代价被挪到了别处比如数组插入要搬数据链表查找要跟着指针跑。把这三件事看清楚那些复杂度表格就是推出来的结论不用背。需要先纠正两个常见误解其一O(1) 一定比 O(log n) 快。大 O 只描述增长趋势常数因子和缓存行为完全不在里面。在元素数量不大的时候一个 O(n) 的顺序扫描常常比 O(log n) 的树查找更快因为前者只碰一条连续内存。其二std::map是哈希表。不是。std::map是有序容器主流实现用红黑树操作是 O(log n)std::unordered_map才是哈希表。本文从内存布局讲到具体结构再到标准库容器的对应关系并给出读者可以自己跑的测量代码。示例以 C17 为基准。一、原理起点连续布局 vs 链式布局所有数据结构的分野几乎都能追溯到这一个选择。1.1 连续布局contiguous storage元素在一整块内存里依次排列。数组、std::vector、std::array、std::string都是这一类。优点第 i 个元素的位置可以直接算出来起始地址 i × 元素大小所以随机访问是 O(1)并且访问相邻元素时硬件缓存预取能起作用。代价在中间插入或删除需要把后面的元素整体搬移代价 O(n)容量固定要变长就得重新分配整块内存并搬迁。1.2 链式布局linked storage每个元素单独分配通常是一个节点节点里存着指向其他节点的指针。std::list、std::forward_list、各种树和图的节点都是这一类。优点已知位置时插入删除只改几个指针O(1)不需要一整块连续内存天然可以增长。代价访问第 i 个元素必须从头走O(n)每个节点多出指针开销节点在内存中零散分布缓存局部性差——这一点在实测中往往比复杂度差异更明显。1.3 缓存局部性为什么是原理级的问题CPU 访问内存不是逐字节的而是以缓存行cache linex86-64 上典型是 64 字节为单位搬运。连续布局下一次取数顺带把后面十几个元素也搬进了缓存后续访问直接命中链式布局下每个节点的地址由上一个节点决定无法预取每次跳转都可能是一次内存访问。这就是为什么复杂度相同的两种结构实测差异可能很大——复杂度分析里不包含内存层次结构。二、不变量结构靠什么维持正确每种结构都有一条必须始终成立的不变量结构不变量代价被挪到哪里动态数组前 n 个位置是从头连续填满的扩容时整体搬迁链表每个节点的 next 指向前驱/后继定位一个位置需要遍历哈希表同一桶内的元素哈希值同余冲突时退化成链式查找二叉搜索树左子树全部小于根右子树全部大于根插入必须沿着路径走平衡树树高被约束在对数范围内插入删除要旋转/变色堆父节点的键不小于或不大于子节点只能快速取最值不能快速查找任意值看这张表的最后两列就能发现一个规律结构不会让你免费得到什么它只是把代价挪到了别的地方。平衡树把查找快换来插入时要旋转堆把取最值快换来查找任意值慢。三、代价的分布摊还分析amortized analysisstd::vector::push_back的复杂度是摊还 O(1)而单次调用可能是 O(n)。这不是含糊其辞而是精确的结论容量满时扩容要重新分配并搬迁全部元素但每次扩容后容量会按某个倍数增长使得这 O(n) 的代价被分摊到后续的 n 次插入上平均下来每次仍是常数。这里有一个必须说清的边界扩容倍数growth factor是实现定义的标准没有规定。已知的常见选择是 libstdc 用 2 倍MSVC STL 的实现采用约 1.5 倍的策略以上为各实现对当前版本的做法可能随版本变化不要当标准断言。倍数越大扩容次数越少但内存浪费越多倍数越接近 1内存利用率越高但搬迁更频繁。链表没有这个问题——插入永远不需要搬迁但每次插入都要分配一个节点分配的代价被挪到了每次操作里。这就是典型的代价分布差异一个是偶尔很贵一个是每次都不便宜。四、抽象与实现分离容器适配器C 标准库把接口和实现分开得很清楚。std::stack、std::queue、std::priority_queue都是容器适配器container adaptor它们本身不存储数据而是包住一个底层容器只暴露受限的接口。适配器提供的语义默认底层容器为什么是它std::stack后进先出std::deque两端操作都高效std::queue先进先出std::deque需要在尾部插入、头部删除std::priority_queue每次取最大默认std::vector堆算法只需要随机访问默认底层容器是标准规定的stack与queue默认dequepriority_queue默认vector但适配器内部如何使用它属于实现细节。关键点是适配器不是容器它们没有迭代器不能直接用范围 for 遍历。五、标准库容器与数据结构的对应容器底层结构是否有序典型查找代价说明std::array定长连续数组按插入顺序O(n)无动态分配大小是类型的一部分std::vector动态数组按插入顺序O(n)尾部摊还 O(1) 插入std::deque分段连续实现定义按插入顺序O(n)两端插入删除都是常数std::list双向链表按插入顺序O(n)已知位置时插入 O(1)std::forward_list单向链表按插入顺序O(n)内存开销最小的链表std::set/std::map平衡二叉搜索树按键升序O(log n)主流实现用红黑树std::unordered_set/std::unordered_map哈希表无序平均 O(1)最坏 O(n)桶策略是实现定义std::stack/std::queue容器适配器不适用不适用无可遍历迭代器std::priority_queue基于堆的适配器只能取堆顶不适用取堆顶 O(1)插入 O(log n)六、自己动手量一量顺序 vs 链式不要相信任何快多少倍的说法包括本文。下面这段代码是给你自己跑的——它只打印你机器上的真实耗时。// locality.cpp — C17 #include chrono #include cstddef #include iostream #include list #include numeric #include vector templatetypename F double timeMs(F f) { const auto t0 std::chrono::steady_clock::now(); f(); const auto t1 std::chrono::steady_clock::now(); return std::chrono::durationdouble, std::milli(t1 - t0).count(); } int main() { constexpr std::size_t N 200000; std::vectorint v(N); std::iota(v.begin(), v.end(), 0); std::listint l(v.begin(), v.end()); volatile long long sink 0; // 防止结果被优化掉 const double tv timeMs([] { long long s 0; for (int x : v) s x; sink s; }); const double tl timeMs([] { long long s 0; for (int x : l) s x; sink s; }); std::cout vector: tv ms\n; std::cout list : tl ms\n; std::cout sink : sink \n; }编译与运行g -stdc17 -O2 -o locality locality.cpp ./locality三点使用说明这里测量的是遍历求和两种结构的复杂度都是 O(n)差异主要来自缓存局部性单次测量噪声很大想认真比较就把timeMs放进循环取多次、取中位数数字随机器、编译器、优化级别变化别把一次运行的结果当结论。同样的方法可以量别的东西push_back的摊还行为、std::map与std::unordered_map的查找、std::deque的两端插入。自己量的数据比任何文章里的数字都可靠。常见坑点1. 只看复杂度不看常数和缓存❌ 为了O(1) 插入给一个只有几百个元素、以遍历为主的集合换成std::list结果遍历变慢。✅ 先问自己主导操作是什么。遍历为主、元素不大时std::vector往往更好频繁在已知位置插入删除才考虑链表。2. 以为std::vector的扩容倍数是标准规定的❌ 写vector 每次扩容 2 倍所以不会有什么问题。倍数由实现决定libstdc 与 MSVC STL 的选择并不相同。✅ 只依赖标准保证的部分push_back摊还 O(1)、capacity()单调不减、扩容后所有引用和迭代器失效。3. 以为链表任意位置插入都是 O(1)❌std::list里想在下标 500 的位置插入以为不用遍历。✅ 找到那个位置本身就是 O(n)。链表的 O(1) 插入前提是你已经拿到了那个位置的迭代器。4. 扩容后继续用旧迭代器或引用❌auto first v[0]; v.push_back(1); use(first);——push_back触发扩容时first指向的是已被释放的旧缓冲区使用它是UB标准不保证任何行为。✅ 扩容后重新取引用或者在知道大致规模时先v.reserve(n)把扩容挡在取引用之前。5. 把std::map当哈希表用❌ 在只需要键到值的映射、且不关心顺序时用std::map白白付出 O(log n) 的查找与节点分配开销。✅ 不需要顺序就用std::unordered_map需要按序遍历才用std::map。6. 忘记哈希表的最坏情况❌ 假定std::unordered_map永远是 O(1)。标准只保证平均常数时间最坏是 O(n)——当大量键落进同一个桶时就会发生。✅ 设计好哈希函数与键的分布对不可信输入可能被构造冲突要考虑这一点。桶的数量与增长策略是实现定义的不能假定。7. 把容器适配器当容器遍历❌ 对std::stack写范围 for或调用begin()。✅ 适配器不提供迭代器。需要遍历就换用底层容器或者重新考虑数据结构选型。8. 大对象按值存进容器❌std::vectorBigObject反复push_back每次扩容都要拷贝全部元素。✅ 存指针或std::unique_ptr注意间接访问的代价或者确保BigObject有noexcept的移动构造函数让容器在扩容时选用移动而不是拷贝。总结原理要点结论布局决定一切连续 vs 链式是绝大多数性能差异的根源不变量每种结构都靠一条约束维持正确维护约束就是它的代价代价守恒快的地方一定有人在付账看代价被挪到了哪摊还分析偶尔很贵 大多很便宜 平均常数扩容倍数是实现定义缓存局部性复杂度相同实测可能差异明显因为它不在复杂度模型里抽象分离容器适配器只暴露受限接口不提供迭代器选型方法先定主导操作再看内存与顺序需求最后才看复杂度表数据结构不是记住哪张表而是理解数据在内存里怎么放、哪些不变量必须维持、代价落在哪一步操作上。这三件事想通了标准库该选哪个容器、该怎么写基本是自然结论。