首页 › C/C++论坛 › C++ 中的 list

段李俊 發表於 2026-1-3 23:02:00

C++ 中的 list

<p></p><div class="toc"><div class="toc-container-header">目录</div><ul><li>核心概念与底层原理</li><li>初始化与构造</li><li>独有的操作优势（<code>std::vector</code> 做不到的）<ul><li>头部操作</li><li>接合（Splicing）</li><li>专用成员函数</li></ul></li><li>迭代器特性</li><li><code>std::list</code> 和 <code>std::vector</code> 的选择</li><li>C++11 新增：<code>std::forword_list</code></li></ul></div><p></p>
<blockquote>
<p><strong>本文首发于我的个人博客：Better Mistakes</strong></p>
<p><strong>版权声明</strong>：本文为原创文章，转载请附上原文出处链接及本声明。<br>
由于技术迭代较快，文章内容可能随时更新（含勘误及补充）。为了确保您看到的是最新版本，并获得更好的代码阅读体验，请访问：</p>
<p>🍭 <strong>原文链接</strong>：https://bfmhno3.github.io/note/list-in-cpp/</p>
</blockquote>
<hr>
<p>在现代 C++ 开发中，虽然 <code>std::vector</code> 足以应付绝大多数的场景，但是在某些特定场景下，<code>std::list</code> 依旧是不可替代的神器。</p>
<h2 id="核心概念与底层原理">核心概念与底层原理</h2>
<ul>
<li>头文件：<code>#include &lt;list&gt;</code></li>
<li>本质：<strong>双向链表</strong>（Doubly Linked List）</li>
<li>内存模型：<strong>非连续内存</strong>。每个元素（节点）都是独立分配在堆上的，节点之间通过指针（<code>prev</code> 和 <code>next</code>）连接</li>
<li>特点：
<ul>
<li><strong>不支持随机访问</strong>：不能使用下标 <code>l</code> 访问元素，必须从头一个一个遍历过去</li>
<li><strong>插入 / 删除极快</strong>：只要持有了某个位置的迭代器，在该位置插入或删除元素的操作是 <span class="math inline">\(O(1)\)</span> 的，且<strong>不需要移动其他元素</strong></li>
</ul>
</li>
</ul>
<h2 id="初始化与构造">初始化与构造</h2>
<p>用法与 <code>std::vector</code> 非常相似：</p>
<pre><code class="language-cpp">#include &lt;list&gt;

std::list&lt;int&gt; l1;            // 空链表
std::list&lt;int&gt; l2 = {1, 2, 3};// 列表初始化
std::list&lt;int&gt; l3(l2);          // 拷贝构造
std::list&lt;int&gt; l4(5, 100);      // 5 个 元素，全是 100
</code></pre>
<h2 id="独有的操作优势stdvector-做不到的">独有的操作优势（<code>std::vector</code> 做不到的）</h2>
<p>这是 <code>std::list</code> 存在的理由。由于它是链表，它支持一些操作极其高效，或者提供了 <code>std::vector</code> 根本没有的接口。</p>
<h3 id="头部操作">头部操作</h3>
<p><code>std::vector</code> 在头部插入 / 删除操作极其低效（<span class="math inline">\(O(N)\)</span>），而 <code>std::list</code> 则是瞬间完成（<span class="math inline">\(O(1)\)</span>）。</p>
<ul>
<li><code>push_front(val)</code>：头部插入</li>
<li><code>pop_front()</code>：头部删除</li>
</ul>
<h3 id="接合splicing">接合（Splicing）</h3>
<p>可以将一个 <code>std::list</code> 的元素（全部或部分）直接 “剪切” 并 “粘贴” 到另一个 <code>std::list</code> 中，这是<strong>纯指针操作</strong>，没有数据拷贝，所以速度极快。</p>
<pre><code class="language-cpp">std::list&lt;int&gt; list1 = {1, 2, 3};
std::list&lt;int&gt; list2 = {4, 5, 6};

auto it =list1.begin();
++it; // 指向 2

// 将 list2 的所有元素 “移动” 到 list1 的 2 前面
// list2 变空，list1 变为 {1, 4, 5, 6, 2, 3}
list1.splice(it, list2);
</code></pre>
<h3 id="专用成员函数">专用成员函数</h3>
<p>由于 <code>std::list</code> 无法随机访问，标准库算法（如 <code>std::sort</code>）对它无效。因此 <code>list</code> 自带了一套经过优化的成员函数：</p>
<ul>
<li><code>l.sort()</code>：排序（稳定排序，底层通常是归并排序）。注意：千万别读 <code>std::list</code> 用 <code>std::sort(l.begin(), l.end())</code>，编译会报错</li>
<li><code>l.remove(val)</code>：删除所有等于 <code>val</code> 的元素</li>
<li><code>l.remove_if(pred)</code>：删除满足条件的元素</li>
<li><code>l.unique()</code>：删除<strong>相邻</strong>的重复元素（去重前通常要先 sort）</li>
<li><code>l.reverse()</code>：逆置链表</li>
<li><code>l.merge(l2)</code>：合并两个<strong>已排序</strong>的链表（<code>l2</code> 会变空）</li>
</ul>
<h2 id="迭代器特性">迭代器特性</h2>
<p>这是决定选择 <code>std::vector</code> 还是 <code>std::list</code> 的关键因素。</p>
<ul>
<li>类型：<strong>双向迭代器</strong>（<em>Bidirectional Iterator</em>）
<ul>
<li>支持：<code>++it</code>、<code>--it</code>、<code>*it</code></li>
<li>不支持：<code>it + 5</code>，<code>it &lt; other_it</code>（不能跳跃，不能比较大小）</li>
</ul>
</li>
<li>稳定性（Validity）：极高
<ul>
<li><strong>掺入操作</strong>：绝对不会让现有的迭代器失效</li>
<li><strong>删除操作</strong>：只有指向<strong>被删除节点</strong>的那个迭代器会失效，其他的完全不受影响</li>
<li>对比 <code>std::vector</code>：<code>std::vector</code> 一旦扩容，所有迭代器全部失效；中间插入，后面所有迭代器失效。</li>
</ul>
</li>
</ul>
<h2 id="stdlist-和-stdvector-的选择"><code>std::list</code> 和 <code>std::vector</code> 的选择</h2>
<p>这是一个经典的 Trade-off（权衡）问题：</p>
<table>
<thead>
<tr>
<th style="text-align: left">特性</th>
<th style="text-align: left"><code>std::vector</code></th>
<th style="text-align: left"><code>std::list</code></th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align: left">随机访问</td>
<td style="text-align: left"><span class="math inline">\(O(1)\)</span>（支持 <code>[]</code>）</td>
<td style="text-align: left">不支持（<span class="math inline">\(O(N)\)</span>）</td>
</tr>
<tr>
<td style="text-align: left">尾部插入</td>
<td style="text-align: left"><span class="math inline">\(O(1)\)</span></td>
<td style="text-align: left"><span class="math inline">\(O(1)\)</span></td>
</tr>
<tr>
<td style="text-align: left">头部/中间插入</td>
<td style="text-align: left"><span class="math inline">\(O(N)\)</span>（很慢，要挪动数据）</td>
<td style="text-align: left"><span class="math inline">\(O(1)\)</span>（很快，前提是有迭代器）</td>
</tr>
<tr>
<td style="text-align: left">内存布局</td>
<td style="text-align: left">连续（Cache 命中率高）</td>
<td style="text-align: left">分散（Cache 命中率低）</td>
</tr>
<tr>
<td style="text-align: left">额外内存</td>
<td style="text-align: left">较少（少量预留空间）</td>
<td style="text-align: left">较大（每个元素都要存两个指针）</td>
</tr>
<tr>
<td style="text-align: left">迭代器失效</td>
<td style="text-align: left">容易失效</td>
<td style="text-align: left">几乎不失效</td>
</tr>
</tbody>
</table>
<p>结论：</p>
<ul>
<li>95% 的情况用 <code>std::vector</code>：现代 CPU 的缓存机制非常依赖内存连续性。即使是在中间插入，对于小对象（如 <code>int</code>），<code>std::vector</code> 往往也比 <code>std::list</code> 快，因为 <code>std::list</code> 的遍历会导致大量的 Cache Miss。</li>
<li>以下情况可以用 <code>std::list</code>：
<ol>
<li>需要频繁在头部或中间插入 / 删除，且元素总数很多</li>
<li>对象非常大，拷贝代价极高（虽然 C++11 移动语义缓解了这个问题）</li>
<li>核心需求：你需要保存指向某个元素的迭代器，并且在后续操作中（无论怎么插入删除其他元素），希望这个迭代器一直有效</li>
</ol>
</li>
</ul>
<h2 id="c11-新增stdforword_list">C++11 新增：<code>std::forword_list</code></h2>
<p>C++11 引入了 <code>std::forword_list</code>（单向链表）：</p>
<ul>
<li>特点：只有 <code>next</code> 指针，没有 <code>prev</code> 指针</li>
<li><strong>优势</strong>：比 <code>std::list</code> 更省内存（少存一个指针）</li>
<li><strong>劣势</strong>：只能向前遍历，功能受限</li>
<li>场景：极其追求内存优化的哈希表桶实现等</li>
</ul>
<hr>
<blockquote>
<p>📢 <strong>写在最后</strong></p>
<p>如果你觉得这篇文章对你有帮助，欢迎到我的个人博客 <strong>Better Mistakes</strong> 逛逛。</p>
<p>在那里我归档了更多高质量的技术文章，也欢迎通过 RSS 订阅我的最新动态！</p>
</blockquote><br><br>
来源：https://www.cnblogs.com/bfmhno3/p/19435120

查看完整版本: C++ 中的 list