尧图网站建设 
「中间插入删除用链表随机访问用数组」这条规则背了很多年但它只说对了一半。真把十万个int分别塞进std::list和std::vector链表的内存占用是后者的6 倍顺序遍历还要慢一个数量级。原因不在复杂度两者遍历都是 O(n)而在每个节点的额外指针和缓存局部性cache locality。这篇用实测把链表的开销算清楚也把链表真正不可替代的两个场景迭代器失效规则与splice零拷贝讲透最后给一条能直接用的选型结论。1. 引子一个反直觉的实测数字先把结论摆上桌同样遍历两万个intvector和list的复杂度都是 O(n)但在 gcc-13.2.0-O2下一次实测list慢了十几倍。这不是编译器没优化好list每走一步都要从当前节点读出下一个节点的地址再跳到那个地址去读数据两次访问落在两个互不相干的内存位置vector走一步只是把地址加 4 字节下一个元素大概率已经在同一条缓存行cache line里了。std::list是双向链表doubly linked liststd::forward_list是 C11 引入的单向链表singly linked list。它们与vector的差别不是「谁更快」而是内存布局布局决定缓存行为缓存行为才决定快慢。官方文档std::list — cppreference 官方文档std::forward_list — cppreference2. 节点布局指针比数据还大链表的每个元素都是一个独立分配的节点node节点里除了数据还有指向邻居的指针。vectorint一次分配、连续内存每元素 4 字节 [0][1][2][3][4][5][6][7][8][9][10][11][12][13][14][15] ... 一条 64B 缓存行装 16 个 int ^ data()地址连续it 就是 4 字节 listint每个元素一个节点每节点 24 字节 head | v ┌───────────┬───────────┬──────┬─────────┐ ┌───────────┬───────────┬──────┬─────────┐ │ prev(NUL) │ next ──── │ 20 │ padding │ │ prev ──── │ next ──── │ 21 │ padding │ └───────────┴───────────┴──────┴─────────┘ └───────────┴───────────┴──────┴─────────┘ 8B 8B 4B 4B 8B 8B 4B 4B | ^ ------------------------------------- 节点散落在堆上不同位置访问 21 要先读 20 的 next 字段 forward_listint每个元素一个节点每节点 16 字节 ┌───────────┬──────┬─────────┐ │ next ──── │ 20 │ padding │ └───────────┴──────┴─────────┘ 8B 4B 4B 单向链表省掉的正是 prev 指针list节点 两个指针 一个int按 8 字节对齐后是 24 字节forward_list节点 一个指针 一个int是 16 字节。容器对象本身的大小也不一样而且forward_list连size()都没有// fwd_list.cpp — 编译: g -stdc17 -Wall -O2 fwd_list.cpp -o fwd_list #include forward_list #include iostream #include iterator #include list int main() { std::forward_listint f{2, 3, 4}; f.push_front(1); // 单向链表没有 push_back f.insert_after(f.before_begin(), 0); // 只能「在某节点之后」插入 std::cout f ; for (int v : f) std::cout v ; std::cout \n; std::cout sizeof(forward_listint) sizeof(std::forward_listint) \n; std::cout sizeof(listint) sizeof(std::listint) \n; std::cout distance(f) std::distance(f.begin(), f.end()) (no size(), O(n))\n; return 0; }f 0 1 2 3 4 sizeof(forward_listint) 8 sizeof(listint) 24 distance(f) 5 (no size(), O(n))forward_list只有 8 字节一个 head 指针list是 24 字节两个哨兵指针再加一个元素计数器。forward_list没有size()不是标准委员会的疏忽是一个明确的设计取舍要支持 O(1) 的size()就得在容器里长期多存一个计数器并在每次insert_after/erase_after/splice_after里维护它单向链表的定位是「尽可能小的节点 尽可能少的簿记」所以把计数这件事推给想用的人自己数std::distance(f.begin(), f.end())是 O(n)。官方文档std::distance — cppreference 顺带记住单向链表的接口形态没有insert只有insert_after没有erase只有erase_afterbefore_begin()是「第一个元素之前」的虚拟位置专给头部插入用。3. 内存膨胀实测每个元素占多少堆sizeof(std::listint)只是容器对象真正吃内存的是节点。要量出「每个元素实际占了多少堆」最直接的办法是塞一个计数分配器counting allocator进去把每次allocate的字节数加起来。链表的节点同样是通过分配器分配的所以这本账是准的。关键技巧是把计数器放在非模板基类里list内部的节点分配器是CountingAllocator的另一个模板实例化如果计数器定义在模板里就会各自记一份放基类才能全算进同一本账。// list_mem.cpp — 编译: g -stdc17 -Wall -O2 list_mem.cpp -o list_mem #include cstddef #include forward_list #include iostream #include list #include memory #include vector struct ByteCounter { inline static std::size_t bytes 0; // C17 内联静态数据成员模板实例化之间共享 }; template typename T struct CountingAllocator : ByteCounter { using value_type T; CountingAllocator() default; template typename U CountingAllocator(const CountingAllocatorU) noexcept {} // 跨类型拷贝账本同一本 T* allocate(std::size_t n) { bytes n * sizeof(T); // 只记字节不碰内存内容 return std::allocatorT{}.allocate(n); } void deallocate(T* p, std::size_t n) noexcept { bytes - n * sizeof(T); std::allocatorT{}.deallocate(p, n); } template typename U bool operator(const CountingAllocatorU) const noexcept { return true; } template typename U bool operator!(const CountingAllocatorU) const noexcept { return false; } }; struct ListNode { ListNode* prev; ListNode* next; int value; }; struct FwdNode { FwdNode* next; int value; }; constexpr int N 100000; // 不写魔法数字量级放在一处 int main() { std::cout sizeof(int) sizeof(int) \n; std::cout sizeof(ListNode) sizeof(ListNode) (prev next int)\n; std::cout sizeof(FwdNode) sizeof(FwdNode) (next int)\n; auto report [](const char* name, std::size_t bytes) { std::cout name : bytes bytes for N ints bytes / N B/elem\n; }; { ByteCounter::bytes 0; std::listint, CountingAllocatorint lst; for (int i 0; i N; i) lst.push_back(i); report(list , ByteCounter::bytes); } { ByteCounter::bytes 0; std::forward_listint, CountingAllocatorint flst; for (int i 0; i N; i) flst.push_front(i); report(forward_list, ByteCounter::bytes); } { ByteCounter::bytes 0; std::vectorint, CountingAllocatorint vec; vec.reserve(N); // 用 reserve 把 vector 的一次分配定死好比较 for (int i 0; i N; i) vec.push_back(i); report(vector , ByteCounter::bytes); } return 0; }sizeof(int) 4 sizeof(ListNode) 24 (prev next int) sizeof(FwdNode) 16 (next int) list : 2400000 bytes for 100000 ints 24 B/elem forward_list : 1600000 bytes for 100000 ints 16 B/elem vector : 400000 bytes for 100000 ints 4 B/elem实测的每元素字节与手写节点的sizeof完全吻合24 / 16说明「节点里两个指针 对齐填充」这个模型是对的。换算成膨胀倍数存储 10 万个int每元素栈上/堆上字节总堆字节相对vector膨胀多出来的是什么std::vectorint4400 0001.0×——std::forward_listint161 600 0004.0×1 个next指针 4 字节对齐填充std::listint242 400 0006.0×prevnext两个指针 填充std::listLargeStruct24 sizeof(LargeStruct)随元素增大逐渐趋近 1×元素越大指针开销被摊薄最后一行的意思是指针开销是固定的元素本身越大链表的相对浪费越小存小对象int、float、指针时链表的 6 倍膨胀最刺眼。4. 缓存局部性遍历为什么反而不如 vectorCPU 不是一个个字节从内存取数据而是以64 字节的缓存行cache line为单位。vectorint的 16 个元素挤在一条缓存行里顺序遍历时每 16 个元素才可能缺一次行而且硬件预取器prefetcher能识别「地址连续递增」这种模式提前把后面的行拉进缓存。list是典型的指针追逐pointer chasing要访问下一个元素必须先把当前节点的next字段读进寄存器。这是一个内存访问它的结果决定了下一次访问的地址。CPU 无法提前知道地址预取器完全失效只能串行等待每个节点都几乎必然触发一次 cache miss而一次 miss 是几十到几百个时钟周期。这就是「同样 O(n)链表常数因子大得多」的物理原因。// list_cache.cpp — 编译: g -stdc17 -Wall -O2 list_cache.cpp -o list_cache #include chrono #include cstddef #include cstdint #include iostream #include iterator #include list #include memory #include vector constexpr int N 20000; int main() { std::vectorint vec; vec.reserve(N); std::listint lst; std::vectorstd::unique_ptrchar[] noise; // 模拟真实程序里穿插的其它分配 for (int i 0; i N; i) { vec.push_back(i); lst.push_back(i); noise.push_back(std::make_uniquechar[](64)); } long long sum_v 0; const auto t0 std::chrono::steady_clock::now(); for (int v : vec) sum_v v; // 连续内存 预取友好 const auto t1 std::chrono::steady_clock::now(); long long sum_l 0; const auto t2 std::chrono::steady_clock::now(); for (int v : lst) sum_l v; // 指针追逐每次都等内存 const auto t3 std::chrono::steady_clock::now(); const auto ms [](auto a, auto b) { return std::chrono::durationdouble, std::milli(b - a).count(); }; std::cout vector: sum sum_v time ms(t0, t1) ms\n; std::cout list : sum sum_l time ms(t2, t3) ms\n; auto addr_of [](const int r) { return reinterpret_caststd::uintptr_t(std::addressof(r)); }; std::cout vector: neighbour gap (addr_of(vec[1]) - addr_of(vec[0])) bytes\n; // list 只能前向遍历单向链表这里数前 1000 个节点的平均地址间距 std::uintptr_t prev addr_of(lst.front()); std::size_t total 0; std::size_t steps 0; for (auto it std::next(lst.begin()); it ! lst.end() steps 1000; it, steps) { const std::uintptr_t cur addr_of(*it); total static_caststd::size_t(cur prev ? cur - prev : prev - cur); prev cur; } std::cout list : avg neighbour gap total / steps bytes\n; std::cout noise alive noise.size() \n; return 0; }vector: sum199990000 time~~ ms list : sum199990000 time~~ ms vector: neighbour gap 4 bytes list : avg neighbour gap ~~ bytes noise alive 20000耗时每次运行都不同但量级稳定list比vector慢十几倍。更值得记住的是最后那个地址间距vector的相邻元素永远只隔 4 字节16 个元素共用一条缓存行而list的相邻节点平均相隔两百多字节也就是说每访问一个链表元素就要拉一条新的缓存行而这行里另外 60 字节全是浪费。维度std::vectorstd::list谁赢顺序遍历复杂度O(n)O(n)一样顺序遍历实际代价每 16 个元素一次 cache miss每个元素一次 cache missvector完胜硬件预取器能识别连续模式有效地址依赖上一次读取失效vector完胜中间插入O(n)尾部元素整体后移O(1)改指针list赢但前提是你已有迭代器按位置随机访问O(1)O(n)vector完胜每元素额外内存016 Bvector完胜迭代器失效扩容/插入点之后全失效仅被删元素失效list赢「中间插入 O(1)」这一条也常被误用list的insert是 O(1)但找到插入位置这一步通常要走 O(n)。只有当你已经持有那个位置的迭代器比如在遍历中途、或迭代器存在别的索引结构里O(1) 才是真收益。如果每次都要std::find找位置那list就变成「O(n) 查找 O(n) 慢遍历」全面落后。官方文档容器库 · 迭代器失效总表 — cppreference5. 第一个真优势迭代器失效规则完全不同这是链表最值钱的差别也是最容易踩坑的地方。vector扩容时必须整块搬家把元素逐个搬到新内存、释放旧内存所有迭代器、指针、引用一次性全部失效即使在中间insert没有触发扩容插入点之后的元素也要整体后移从插入点起的迭代器同样失效。list的insert/erase只是改几个指针不移动任何已有节点所以其他迭代器保持有效。操作vectordequelist/forward_listinsert中间未扩容插入点及其后全部失效全部失效全部有效insert触发扩容全部失效全部失效全部有效erase删除点及其后全部失效全部失效仅被删元素失效push_back/pop_back扩容时全部失效全部失效全部有效push_front/pop_front不支持全部失效全部有效整体搬迁扩容时发生通常不发生永不发生// list_iterator.cpp — 编译: g -stdc17 -Wall -O2 list_iterator.cpp -o list_iterator #include iostream #include iterator #include list #include vector int main() { std::listint lst{10, 20, 30}; auto it20 std::next(lst.begin()); auto it30 std::next(lst.begin(), 2); lst.insert(it30, 25); // 在 30 之前插入已有迭代器全部保持有效 std::cout list: size lst.size() *it20 *it20 *it30 *it30 \n; lst.erase(it20); // 只有 it20 自己失效it30 照常可用 std::cout list: size lst.size() *it30 *it30 front lst.front() \n; std::vectorint vec{10, 20, 30}; std::cout vector: capacity before insert vec.capacity() \n; vec.insert(vec.begin() 2, 25); // size capacity → 触发重新分配 std::cout vector: capacity after insert vec.capacity() \n; std::cout vector: insert/erase invalidates iterators at and after the point\n; return 0; }list: size4 *it2020 *it3030 list: size3 *it3030 front10 vector: capacity before insert 3 vector: capacity after insert 6 vector: insert/erase invalidates iterators at and after the point注意上面刻意没有使用失效后的vector迭代器那是未定义行为undefined behavior演示代码不该示范它。这里只用一个有明确定义的证据容量从 3 变成 6说明确实发生了重新分配。libstdc 的vector扩容按 2 倍增长标准不规定倍数只保证均摊 O(1)任何教材上写死的「1.5 倍」都只是某个实现的选择。6. 第二个真优势splice 零拷贝搬移list独有的splice拼接可以把一个节点或一整段、整个链表从一处搬到另一处只改指针不拷贝、不移动元素。用vector做同样的事只能insert一个拷贝、再erase原来的元素搬两次。当元素很大比如是个含std::string的结构体甚至已经拿到地址被外部引用时splice的价值非常实际元素对象的内存地址全程不变。// list_splice.cpp — 编译: g -stdc17 -Wall -O2 list_splice.cpp -o list_splice #include iostream #include iterator #include list #include memory #include string int main() { std::liststd::string a{aa, bb, cc}; std::liststd::string b{dd, ee}; auto it std::next(a.begin()); // 指向 bb const std::string* addr_before std::addressof(*it); b.splice(b.end(), a, it); // 整节点搬移不拷贝、不移动元素 std::cout a ; for (const auto s : a) std::cout s ; std::cout (size a.size() )\n; std::cout b ; for (const auto s : b) std::cout s ; std::cout (size b.size() )\n; std::cout element lived in place? (addr_before std::addressof(b.back())) \n; std::cout total elements kept a.size() b.size() \n; return 0; }a aa cc (size2) b dd ee bb (size3) element lived in place? 1 total elements kept 5element lived in place? 1是硬证据bb这个对象在搬移前后地址一模一样说明既没拷贝构造也没移动构造只是把节点从a的链上摘下来挂到b上。另外注意splice不涉及任何元素构造/析构元素总数守恒a.size() b.size()仍是 5。splice有三种重载整条链表splice(pos, other)、单个元素splice(pos, other, it)、一个区间splice(pos, other, first, last)。所有重载都保持迭代器有效性除了被搬走的那个元素它现在属于other但指向它的迭代器依然有效只是所属容器换了。官方文档std::list::splice — cppreference7. 完整示例用迭代器稳定性写一个 O(1) 的 LRU 缓存LRU 缓存是「链表不可替代」的经典场景也正好把前面两个优势串起来需要中间删除、把元素提到头部、并且长期持有指向元素的迭代器。如果用vector实现每次「提到最前」都要搬动后面一整段元素缓存的命中路径会退化到 O(n)。// lru_list.cpp — 编译: g -stdc17 -Wall -O2 lru_list.cpp -o lru_list #include iostream #include list #include string #include unordered_map class LruCache { public: explicit LruCache(std::size_t capacity) : capacity_(capacity) {} bool get(const std::string key, int out) { const auto found index_.find(key); // find未命中不会插入任何东西 if (found index_.end()) return false; order_.splice(order_.begin(), order_, found-second); // 提到最前零拷贝 out found-second-second; return true; } void put(const std::string key, int value) { const auto found index_.find(key); if (found ! index_.end()) { // 已存在改值 提到最前 found-second-second value; order_.splice(order_.begin(), order_, found-second); return; } if (order_.size() capacity_) { // 淘汰最久未用链表尾部 index_.erase(order_.back().first); order_.pop_back(); } order_.emplace_front(key, value); index_.emplace(key, order_.begin()); // 迭代器稳定可以长期存着 } void dump(const char* tag) const { std::cout tag : ; for (const auto item : order_) std::cout item.first item.second ; std::cout \n; } private: using Item std::pairstd::string, int; // key, value std::listItem order_; // front 最近使用 std::unordered_mapstd::string, std::listItem::iterator index_; std::size_t capacity_; }; int main() { LruCache cache(3); cache.put(a, 1); cache.put(b, 2); cache.put(c, 3); cache.dump(after put a,b,c); int value 0; std::cout get(a) hit cache.get(a, value) value value \n; cache.dump(after get a); cache.put(d, 4); // 容量满淘汰最久未用的 b cache.dump(after put d); std::cout get(b) hit cache.get(b, value) \n; return 0; }after put a,b,c: c3 b2 a1 get(a) hit1 value1 after get a: a1 c3 b2 after put d: d4 a1 c3 get(b) hit0这段代码的每一处都吃到了链表的特性index_里存的是std::listItem::iterator如果换成vector任何一次插入都可能让这些迭代器失效整个设计直接崩塌get命中时用splice把节点摘到头部是纯指针操作不管缓存里有一千条还是一百万条都是常数时间淘汰时从尾部pop_back也是 O(1)。换成vector的话这三个操作里有两个会退化成 O(n)这就是链表真正不可替代的地方。8. 选型表默认 vector链表是特例工具把整篇的结论压成一张表你的需求选谁理由不确定 / 没有特殊理由std::vector缓存友好、内存最省、遍历最快绝大多数场景的最优解尾部增删为主std::vectorpush_back均摊 O(1)连续内存需要按下标随机访问std::vectorO(1)list是 O(n)两头都要增删std::deque分段连续内存两端都 O(1)见《deque 与容器适配器全解》中间频繁增删且已持有迭代器std::listinsert/eraseO(1)不使其他迭代器失效需要在遍历中途删元素std::list迭代器稳定vector会被 O(n) 的元素搬移拖垮元素很大、需要零拷贝搬移std::listsplice只改指针元素地址不变省掉拷贝/移动构造元素很小、节点开销难以接受别用list存int时膨胀 6 倍纯亏只需要单向遍历、想省内存std::forward_list节点 16 B 而非 24 B容器对象 8 B 而非 24 B要求有序、按 key 查找std::map/std::set链表的查找是 O(n)见《map / set 完全指南红黑树与有序容器》一句话默认选vector只有当「已经持有迭代器 中间增删」或「splice零拷贝搬移」这两条真正成立时链表才是划算的。至于forward_list它是「省一个指针和 4 字节对齐填充」的极致优化代价是只能单向遍历、只能insert_after/erase_after、没有size()除非你在做内存极度受限的嵌入式场景否则list的接口更好用。官方文档C Core Guidelines「SL: Containers」——容器选型的一手依据 官方文档std::vector — cppreference9. 延伸阅读std::list — cppreference完整接口重点看splice的三个重载和复杂度标注。std::forward_list — cppreference注意它没有size()、没有push_back接口一律带_after。std::list::splice — cppreference明确写了「不拷贝也不移动元素只调整节点内部的指针」。容器库 · 迭代器失效总表 — cppreference哪条规则会失效、哪条不会以这张表为准不要凭印象。C Core Guidelines — isocpp.github.io容器与资源管理的基调来源。本知识库内的相关篇目《vector 扩容策略与迭代器失效全解》 —— vector 的 size 与 capacity 为什么分开、push_back 触发的扩容到底做了什么《deque 与容器适配器全解stack、queue、priority_queue 到底套了什么》 —— 讲透 std::deque 的分段连续内存结构——固定大小的缓冲块加一个中控数组《C map 与 unordered_map 怎么选底层结构、复杂度与决策流程》 —— std::map 和 std::unordered_map 接口几乎一样底层却完全不同。10. 一句话总结list/forward_list用「每个元素一个节点」换来 O(1) 的已知位置插入删除代价是固定 1624 字节的节点开销存int时膨胀 46 倍和指针追逐导致的缓存不友好所以顺序遍历反而比vector慢十几倍它们的真正价值只有两个insert/erase不使其他迭代器失效以及splice能零拷贝搬移元素。默认选vector把链表留给这两条确实成立的场景。 list 与 forward_list：链表真的比 vector 快吗
「中间插入删除用链表随机访问用数组」这条规则背了很多年但它只说对了一半。真把十万个int分别塞进std::list和std::vector链表的内存占用是后者的6 倍顺序遍历还要慢一个数量级。原因不在复杂度两者遍历都是 O(n)而在每个节点的额外指针和缓存局部性cache locality。这篇用实测把链表的开销算清楚也把链表真正不可替代的两个场景迭代器失效规则与splice零拷贝讲透最后给一条能直接用的选型结论。1. 引子一个反直觉的实测数字先把结论摆上桌同样遍历两万个intvector和list的复杂度都是 O(n)但在 gcc-13.2.0-O2下一次实测list慢了十几倍。这不是编译器没优化好list每走一步都要从当前节点读出下一个节点的地址再跳到那个地址去读数据两次访问落在两个互不相干的内存位置vector走一步只是把地址加 4 字节下一个元素大概率已经在同一条缓存行cache line里了。std::list是双向链表doubly linked liststd::forward_list是 C11 引入的单向链表singly linked list。它们与vector的差别不是「谁更快」而是内存布局布局决定缓存行为缓存行为才决定快慢。官方文档std::list — cppreference 官方文档std::forward_list — cppreference2. 节点布局指针比数据还大链表的每个元素都是一个独立分配的节点node节点里除了数据还有指向邻居的指针。vectorint一次分配、连续内存每元素 4 字节 [0][1][2][3][4][5][6][7][8][9][10][11][12][13][14][15] ... 一条 64B 缓存行装 16 个 int ^ data()地址连续it 就是 4 字节 listint每个元素一个节点每节点 24 字节 head | v ┌───────────┬───────────┬──────┬─────────┐ ┌───────────┬───────────┬──────┬─────────┐ │ prev(NUL) │ next ──── │ 20 │ padding │ │ prev ──── │ next ──── │ 21 │ padding │ └───────────┴───────────┴──────┴─────────┘ └───────────┴───────────┴──────┴─────────┘ 8B 8B 4B 4B 8B 8B 4B 4B | ^ ------------------------------------- 节点散落在堆上不同位置访问 21 要先读 20 的 next 字段 forward_listint每个元素一个节点每节点 16 字节 ┌───────────┬──────┬─────────┐ │ next ──── │ 20 │ padding │ └───────────┴──────┴─────────┘ 8B 4B 4B 单向链表省掉的正是 prev 指针list节点 两个指针 一个int按 8 字节对齐后是 24 字节forward_list节点 一个指针 一个int是 16 字节。容器对象本身的大小也不一样而且forward_list连size()都没有// fwd_list.cpp — 编译: g -stdc17 -Wall -O2 fwd_list.cpp -o fwd_list #include forward_list #include iostream #include iterator #include list int main() { std::forward_listint f{2, 3, 4}; f.push_front(1); // 单向链表没有 push_back f.insert_after(f.before_begin(), 0); // 只能「在某节点之后」插入 std::cout f ; for (int v : f) std::cout v ; std::cout \n; std::cout sizeof(forward_listint) sizeof(std::forward_listint) \n; std::cout sizeof(listint) sizeof(std::listint) \n; std::cout distance(f) std::distance(f.begin(), f.end()) (no size(), O(n))\n; return 0; }f 0 1 2 3 4 sizeof(forward_listint) 8 sizeof(listint) 24 distance(f) 5 (no size(), O(n))forward_list只有 8 字节一个 head 指针list是 24 字节两个哨兵指针再加一个元素计数器。forward_list没有size()不是标准委员会的疏忽是一个明确的设计取舍要支持 O(1) 的size()就得在容器里长期多存一个计数器并在每次insert_after/erase_after/splice_after里维护它单向链表的定位是「尽可能小的节点 尽可能少的簿记」所以把计数这件事推给想用的人自己数std::distance(f.begin(), f.end())是 O(n)。官方文档std::distance — cppreference 顺带记住单向链表的接口形态没有insert只有insert_after没有erase只有erase_afterbefore_begin()是「第一个元素之前」的虚拟位置专给头部插入用。3. 内存膨胀实测每个元素占多少堆sizeof(std::listint)只是容器对象真正吃内存的是节点。要量出「每个元素实际占了多少堆」最直接的办法是塞一个计数分配器counting allocator进去把每次allocate的字节数加起来。链表的节点同样是通过分配器分配的所以这本账是准的。关键技巧是把计数器放在非模板基类里list内部的节点分配器是CountingAllocator的另一个模板实例化如果计数器定义在模板里就会各自记一份放基类才能全算进同一本账。// list_mem.cpp — 编译: g -stdc17 -Wall -O2 list_mem.cpp -o list_mem #include cstddef #include forward_list #include iostream #include list #include memory #include vector struct ByteCounter { inline static std::size_t bytes 0; // C17 内联静态数据成员模板实例化之间共享 }; template typename T struct CountingAllocator : ByteCounter { using value_type T; CountingAllocator() default; template typename U CountingAllocator(const CountingAllocatorU) noexcept {} // 跨类型拷贝账本同一本 T* allocate(std::size_t n) { bytes n * sizeof(T); // 只记字节不碰内存内容 return std::allocatorT{}.allocate(n); } void deallocate(T* p, std::size_t n) noexcept { bytes - n * sizeof(T); std::allocatorT{}.deallocate(p, n); } template typename U bool operator(const CountingAllocatorU) const noexcept { return true; } template typename U bool operator!(const CountingAllocatorU) const noexcept { return false; } }; struct ListNode { ListNode* prev; ListNode* next; int value; }; struct FwdNode { FwdNode* next; int value; }; constexpr int N 100000; // 不写魔法数字量级放在一处 int main() { std::cout sizeof(int) sizeof(int) \n; std::cout sizeof(ListNode) sizeof(ListNode) (prev next int)\n; std::cout sizeof(FwdNode) sizeof(FwdNode) (next int)\n; auto report [](const char* name, std::size_t bytes) { std::cout name : bytes bytes for N ints bytes / N B/elem\n; }; { ByteCounter::bytes 0; std::listint, CountingAllocatorint lst; for (int i 0; i N; i) lst.push_back(i); report(list , ByteCounter::bytes); } { ByteCounter::bytes 0; std::forward_listint, CountingAllocatorint flst; for (int i 0; i N; i) flst.push_front(i); report(forward_list, ByteCounter::bytes); } { ByteCounter::bytes 0; std::vectorint, CountingAllocatorint vec; vec.reserve(N); // 用 reserve 把 vector 的一次分配定死好比较 for (int i 0; i N; i) vec.push_back(i); report(vector , ByteCounter::bytes); } return 0; }sizeof(int) 4 sizeof(ListNode) 24 (prev next int) sizeof(FwdNode) 16 (next int) list : 2400000 bytes for 100000 ints 24 B/elem forward_list : 1600000 bytes for 100000 ints 16 B/elem vector : 400000 bytes for 100000 ints 4 B/elem实测的每元素字节与手写节点的sizeof完全吻合24 / 16说明「节点里两个指针 对齐填充」这个模型是对的。换算成膨胀倍数存储 10 万个int每元素栈上/堆上字节总堆字节相对vector膨胀多出来的是什么std::vectorint4400 0001.0×——std::forward_listint161 600 0004.0×1 个next指针 4 字节对齐填充std::listint242 400 0006.0×prevnext两个指针 填充std::listLargeStruct24 sizeof(LargeStruct)随元素增大逐渐趋近 1×元素越大指针开销被摊薄最后一行的意思是指针开销是固定的元素本身越大链表的相对浪费越小存小对象int、float、指针时链表的 6 倍膨胀最刺眼。4. 缓存局部性遍历为什么反而不如 vectorCPU 不是一个个字节从内存取数据而是以64 字节的缓存行cache line为单位。vectorint的 16 个元素挤在一条缓存行里顺序遍历时每 16 个元素才可能缺一次行而且硬件预取器prefetcher能识别「地址连续递增」这种模式提前把后面的行拉进缓存。list是典型的指针追逐pointer chasing要访问下一个元素必须先把当前节点的next字段读进寄存器。这是一个内存访问它的结果决定了下一次访问的地址。CPU 无法提前知道地址预取器完全失效只能串行等待每个节点都几乎必然触发一次 cache miss而一次 miss 是几十到几百个时钟周期。这就是「同样 O(n)链表常数因子大得多」的物理原因。// list_cache.cpp — 编译: g -stdc17 -Wall -O2 list_cache.cpp -o list_cache #include chrono #include cstddef #include cstdint #include iostream #include iterator #include list #include memory #include vector constexpr int N 20000; int main() { std::vectorint vec; vec.reserve(N); std::listint lst; std::vectorstd::unique_ptrchar[] noise; // 模拟真实程序里穿插的其它分配 for (int i 0; i N; i) { vec.push_back(i); lst.push_back(i); noise.push_back(std::make_uniquechar[](64)); } long long sum_v 0; const auto t0 std::chrono::steady_clock::now(); for (int v : vec) sum_v v; // 连续内存 预取友好 const auto t1 std::chrono::steady_clock::now(); long long sum_l 0; const auto t2 std::chrono::steady_clock::now(); for (int v : lst) sum_l v; // 指针追逐每次都等内存 const auto t3 std::chrono::steady_clock::now(); const auto ms [](auto a, auto b) { return std::chrono::durationdouble, std::milli(b - a).count(); }; std::cout vector: sum sum_v time ms(t0, t1) ms\n; std::cout list : sum sum_l time ms(t2, t3) ms\n; auto addr_of [](const int r) { return reinterpret_caststd::uintptr_t(std::addressof(r)); }; std::cout vector: neighbour gap (addr_of(vec[1]) - addr_of(vec[0])) bytes\n; // list 只能前向遍历单向链表这里数前 1000 个节点的平均地址间距 std::uintptr_t prev addr_of(lst.front()); std::size_t total 0; std::size_t steps 0; for (auto it std::next(lst.begin()); it ! lst.end() steps 1000; it, steps) { const std::uintptr_t cur addr_of(*it); total static_caststd::size_t(cur prev ? cur - prev : prev - cur); prev cur; } std::cout list : avg neighbour gap total / steps bytes\n; std::cout noise alive noise.size() \n; return 0; }vector: sum199990000 time~~ ms list : sum199990000 time~~ ms vector: neighbour gap 4 bytes list : avg neighbour gap ~~ bytes noise alive 20000耗时每次运行都不同但量级稳定list比vector慢十几倍。更值得记住的是最后那个地址间距vector的相邻元素永远只隔 4 字节16 个元素共用一条缓存行而list的相邻节点平均相隔两百多字节也就是说每访问一个链表元素就要拉一条新的缓存行而这行里另外 60 字节全是浪费。维度std::vectorstd::list谁赢顺序遍历复杂度O(n)O(n)一样顺序遍历实际代价每 16 个元素一次 cache miss每个元素一次 cache missvector完胜硬件预取器能识别连续模式有效地址依赖上一次读取失效vector完胜中间插入O(n)尾部元素整体后移O(1)改指针list赢但前提是你已有迭代器按位置随机访问O(1)O(n)vector完胜每元素额外内存016 Bvector完胜迭代器失效扩容/插入点之后全失效仅被删元素失效list赢「中间插入 O(1)」这一条也常被误用list的insert是 O(1)但找到插入位置这一步通常要走 O(n)。只有当你已经持有那个位置的迭代器比如在遍历中途、或迭代器存在别的索引结构里O(1) 才是真收益。如果每次都要std::find找位置那list就变成「O(n) 查找 O(n) 慢遍历」全面落后。官方文档容器库 · 迭代器失效总表 — cppreference5. 第一个真优势迭代器失效规则完全不同这是链表最值钱的差别也是最容易踩坑的地方。vector扩容时必须整块搬家把元素逐个搬到新内存、释放旧内存所有迭代器、指针、引用一次性全部失效即使在中间insert没有触发扩容插入点之后的元素也要整体后移从插入点起的迭代器同样失效。list的insert/erase只是改几个指针不移动任何已有节点所以其他迭代器保持有效。操作vectordequelist/forward_listinsert中间未扩容插入点及其后全部失效全部失效全部有效insert触发扩容全部失效全部失效全部有效erase删除点及其后全部失效全部失效仅被删元素失效push_back/pop_back扩容时全部失效全部失效全部有效push_front/pop_front不支持全部失效全部有效整体搬迁扩容时发生通常不发生永不发生// list_iterator.cpp — 编译: g -stdc17 -Wall -O2 list_iterator.cpp -o list_iterator #include iostream #include iterator #include list #include vector int main() { std::listint lst{10, 20, 30}; auto it20 std::next(lst.begin()); auto it30 std::next(lst.begin(), 2); lst.insert(it30, 25); // 在 30 之前插入已有迭代器全部保持有效 std::cout list: size lst.size() *it20 *it20 *it30 *it30 \n; lst.erase(it20); // 只有 it20 自己失效it30 照常可用 std::cout list: size lst.size() *it30 *it30 front lst.front() \n; std::vectorint vec{10, 20, 30}; std::cout vector: capacity before insert vec.capacity() \n; vec.insert(vec.begin() 2, 25); // size capacity → 触发重新分配 std::cout vector: capacity after insert vec.capacity() \n; std::cout vector: insert/erase invalidates iterators at and after the point\n; return 0; }list: size4 *it2020 *it3030 list: size3 *it3030 front10 vector: capacity before insert 3 vector: capacity after insert 6 vector: insert/erase invalidates iterators at and after the point注意上面刻意没有使用失效后的vector迭代器那是未定义行为undefined behavior演示代码不该示范它。这里只用一个有明确定义的证据容量从 3 变成 6说明确实发生了重新分配。libstdc 的vector扩容按 2 倍增长标准不规定倍数只保证均摊 O(1)任何教材上写死的「1.5 倍」都只是某个实现的选择。6. 第二个真优势splice 零拷贝搬移list独有的splice拼接可以把一个节点或一整段、整个链表从一处搬到另一处只改指针不拷贝、不移动元素。用vector做同样的事只能insert一个拷贝、再erase原来的元素搬两次。当元素很大比如是个含std::string的结构体甚至已经拿到地址被外部引用时splice的价值非常实际元素对象的内存地址全程不变。// list_splice.cpp — 编译: g -stdc17 -Wall -O2 list_splice.cpp -o list_splice #include iostream #include iterator #include list #include memory #include string int main() { std::liststd::string a{aa, bb, cc}; std::liststd::string b{dd, ee}; auto it std::next(a.begin()); // 指向 bb const std::string* addr_before std::addressof(*it); b.splice(b.end(), a, it); // 整节点搬移不拷贝、不移动元素 std::cout a ; for (const auto s : a) std::cout s ; std::cout (size a.size() )\n; std::cout b ; for (const auto s : b) std::cout s ; std::cout (size b.size() )\n; std::cout element lived in place? (addr_before std::addressof(b.back())) \n; std::cout total elements kept a.size() b.size() \n; return 0; }a aa cc (size2) b dd ee bb (size3) element lived in place? 1 total elements kept 5element lived in place? 1是硬证据bb这个对象在搬移前后地址一模一样说明既没拷贝构造也没移动构造只是把节点从a的链上摘下来挂到b上。另外注意splice不涉及任何元素构造/析构元素总数守恒a.size() b.size()仍是 5。splice有三种重载整条链表splice(pos, other)、单个元素splice(pos, other, it)、一个区间splice(pos, other, first, last)。所有重载都保持迭代器有效性除了被搬走的那个元素它现在属于other但指向它的迭代器依然有效只是所属容器换了。官方文档std::list::splice — cppreference7. 完整示例用迭代器稳定性写一个 O(1) 的 LRU 缓存LRU 缓存是「链表不可替代」的经典场景也正好把前面两个优势串起来需要中间删除、把元素提到头部、并且长期持有指向元素的迭代器。如果用vector实现每次「提到最前」都要搬动后面一整段元素缓存的命中路径会退化到 O(n)。// lru_list.cpp — 编译: g -stdc17 -Wall -O2 lru_list.cpp -o lru_list #include iostream #include list #include string #include unordered_map class LruCache { public: explicit LruCache(std::size_t capacity) : capacity_(capacity) {} bool get(const std::string key, int out) { const auto found index_.find(key); // find未命中不会插入任何东西 if (found index_.end()) return false; order_.splice(order_.begin(), order_, found-second); // 提到最前零拷贝 out found-second-second; return true; } void put(const std::string key, int value) { const auto found index_.find(key); if (found ! index_.end()) { // 已存在改值 提到最前 found-second-second value; order_.splice(order_.begin(), order_, found-second); return; } if (order_.size() capacity_) { // 淘汰最久未用链表尾部 index_.erase(order_.back().first); order_.pop_back(); } order_.emplace_front(key, value); index_.emplace(key, order_.begin()); // 迭代器稳定可以长期存着 } void dump(const char* tag) const { std::cout tag : ; for (const auto item : order_) std::cout item.first item.second ; std::cout \n; } private: using Item std::pairstd::string, int; // key, value std::listItem order_; // front 最近使用 std::unordered_mapstd::string, std::listItem::iterator index_; std::size_t capacity_; }; int main() { LruCache cache(3); cache.put(a, 1); cache.put(b, 2); cache.put(c, 3); cache.dump(after put a,b,c); int value 0; std::cout get(a) hit cache.get(a, value) value value \n; cache.dump(after get a); cache.put(d, 4); // 容量满淘汰最久未用的 b cache.dump(after put d); std::cout get(b) hit cache.get(b, value) \n; return 0; }after put a,b,c: c3 b2 a1 get(a) hit1 value1 after get a: a1 c3 b2 after put d: d4 a1 c3 get(b) hit0这段代码的每一处都吃到了链表的特性index_里存的是std::listItem::iterator如果换成vector任何一次插入都可能让这些迭代器失效整个设计直接崩塌get命中时用splice把节点摘到头部是纯指针操作不管缓存里有一千条还是一百万条都是常数时间淘汰时从尾部pop_back也是 O(1)。换成vector的话这三个操作里有两个会退化成 O(n)这就是链表真正不可替代的地方。8. 选型表默认 vector链表是特例工具把整篇的结论压成一张表你的需求选谁理由不确定 / 没有特殊理由std::vector缓存友好、内存最省、遍历最快绝大多数场景的最优解尾部增删为主std::vectorpush_back均摊 O(1)连续内存需要按下标随机访问std::vectorO(1)list是 O(n)两头都要增删std::deque分段连续内存两端都 O(1)见《deque 与容器适配器全解》中间频繁增删且已持有迭代器std::listinsert/eraseO(1)不使其他迭代器失效需要在遍历中途删元素std::list迭代器稳定vector会被 O(n) 的元素搬移拖垮元素很大、需要零拷贝搬移std::listsplice只改指针元素地址不变省掉拷贝/移动构造元素很小、节点开销难以接受别用list存int时膨胀 6 倍纯亏只需要单向遍历、想省内存std::forward_list节点 16 B 而非 24 B容器对象 8 B 而非 24 B要求有序、按 key 查找std::map/std::set链表的查找是 O(n)见《map / set 完全指南红黑树与有序容器》一句话默认选vector只有当「已经持有迭代器 中间增删」或「splice零拷贝搬移」这两条真正成立时链表才是划算的。至于forward_list它是「省一个指针和 4 字节对齐填充」的极致优化代价是只能单向遍历、只能insert_after/erase_after、没有size()除非你在做内存极度受限的嵌入式场景否则list的接口更好用。官方文档C Core Guidelines「SL: Containers」——容器选型的一手依据 官方文档std::vector — cppreference9. 延伸阅读std::list — cppreference完整接口重点看splice的三个重载和复杂度标注。std::forward_list — cppreference注意它没有size()、没有push_back接口一律带_after。std::list::splice — cppreference明确写了「不拷贝也不移动元素只调整节点内部的指针」。容器库 · 迭代器失效总表 — cppreference哪条规则会失效、哪条不会以这张表为准不要凭印象。C Core Guidelines — isocpp.github.io容器与资源管理的基调来源。本知识库内的相关篇目《vector 扩容策略与迭代器失效全解》 —— vector 的 size 与 capacity 为什么分开、push_back 触发的扩容到底做了什么《deque 与容器适配器全解stack、queue、priority_queue 到底套了什么》 —— 讲透 std::deque 的分段连续内存结构——固定大小的缓冲块加一个中控数组《C map 与 unordered_map 怎么选底层结构、复杂度与决策流程》 —— std::map 和 std::unordered_map 接口几乎一样底层却完全不同。10. 一句话总结list/forward_list用「每个元素一个节点」换来 O(1) 的已知位置插入删除代价是固定 1624 字节的节点开销存int时膨胀 46 倍和指针追逐导致的缓存不友好所以顺序遍历反而比vector慢十几倍它们的真正价值只有两个insert/erase不使其他迭代器失效以及splice能零拷贝搬移元素。默认选vector把链表留给这两条确实成立的场景。