当前位置： 首页 > news >正文

C++ std::list

news 2025/9/16 10:17:57

std::list 是 C++ STL 中基于双向链表实现的序列容器，其设计目标是提供高效的任意位置插入 / 删除操作。

1、底层结构与核心原理

1.1 节点与链表结构

节点组成：每个元素存储在独立的节点中，节点包含三部分

template <typename T>
struct ListNode {T data;          // 元素值ListNode* prev;  // 指向前驱节点ListNode* next;  // 指向后继节点
};

容器内部指针：std::list 维护两个关键指针：

  • head：指向第一个节点（首节点）。
  • tail：指向最后一个节点（尾节点）。

1.2 核心特性

  1. 非连续存储

    • 元素分散在内存的各个地方，不像vector或array是连续块。

  2. 高效的插入与删除 (O(1))

    • 在任何已知位置（通过迭代器指定）的插入和删除操作都是常数时间复杂度。
    • 操作仅涉及指针的重新赋值，不需要移动任何其他元素。
      • 插入：新分配一个节点，然后调整相邻节点的指针指向这个新节点。
      • 删除：调整目标节点前后节点的指针，让它们彼此指向对方，然后释放目标节点的内存。

  3. 迭代器稳定性

    • 这是list最强大的特性之一。插入操作不会使任何现有的迭代器、指针或引用失效。
    • 删除操作只会使指向被删除元素的迭代器、指针或引用失效，其他元素的迭代器仍然完全有效。
    • 这与vector和deque形成鲜明对比，后者在插入/删除时极易导致迭代器大面积失效。

  4. 不支持随机访问 (O(n))

    • 无法使用[]运算符或at()方法直接访问第n个元素。
    • 访问某个特定位置的元素需要从begin()或end()开始逐步递增或递减迭代器，时间复杂度为线性O(n)。

2、常用操作与示例代码

2.1 初始化

#include <list>
#include <iostream>// 1. 空list
std::list<int> list1;// 2. 包含 n 个元素，每个元素使用默认值初始化 (int 为 0)
std::list<int> list2(5); // {0, 0, 0, 0, 0}// 3. 包含 n 个元素，每个元素都是 value
std::list<int> list3(5, 100); // {100, 100, 100, 100, 100}// 4. 通过初始化列表 (C++11)
std::list<int> list4 = {1, 2, 3, 4, 5};// 5. 通过迭代器范围（另一个容器的）
std::vector<int> vec = {6, 7, 8};
std::list<int> list5(vec.begin(), vec.end()); // {6, 7, 8}// 6. 拷贝构造函数
std::list<int> list6(list4); // {1, 2, 3, 4, 5}

2.2 元素访问

std::list<int> l = {10, 20, 30};// 访问第一个和最后一个元素
std::cout << l.front(); // 10
std::cout << l.back();  // 30// 错误！list不支持随机访问
// int a = l[1];
// int b = l.at(1);// 正确但低效的方法：使用迭代器步进
auto it = l.begin();
std::advance(it, 1); // 将迭代器 it 前进 1 步，现在指向 20
std::cout << *it;    // 20
// 注意：advance(it, n) 对于list是O(n)操作

2.3 增加元素

std::list<int> l = {1, 2, 3};// 在尾部添加
l.push_back(4);   // {1, 2, 3, 4} - 拷贝或移动
l.emplace_back(5); // {1, 2, 3, 4, 5} - 原地构造，更高效// 在头部添加
l.push_front(0);   // {0, 1, 2, 3, 4, 5}
l.emplace_front(-1); // {-1, 0, 1, 2, 3, 4, 5}// 在指定位置插入
auto it = l.begin();
std::advance(it, 3); // it 现在指向 2
l.insert(it, 99);    // 在 2 之前插入 99 -> {-1, 0, 1, 99, 2, 3, 4, 5}
l.emplace(it, 88);   // 同理，但原地构造 -> {-1, 0, 1, 99, 88, 2, 3, 4, 5}// 插入多个值或一个区间
l.insert(it, 3, 77); // 在 it 前插入 3 个 77
std::vector<int> v = {55, 66};
l.insert(it, v.begin(), v.end()); // 插入一个区间

2.4 删除元素

std::list<int> l = {-1, 0, 1, 77, 77, 77, 55, 66, 88, 2, 3, 4, 5};// 删除头部元素
l.pop_front(); // {0, 1, 77, 77, 77, 55, 66, 88, 2, 3, 4, 5}// 删除尾部元素
l.pop_back(); // {0, 1, 77, 77, 77, 55, 66, 88, 2, 3, 4}// 删除指定位置的元素
auto it = l.begin();
std::advance(it, 3);
it = l.erase(it); // 删除第三个元素（第一个77），erase返回被删除元素的下一个元素的迭代器
// l: {0, 1, 77, 77, 55, 66, 88, 2, 3, 4}// 删除一个区间的元素 [first, last)
auto first = l.begin();
auto last = l.begin();
std::advance(first, 1);
std::advance(last, 4);
l.erase(first, last); // 删除 [第二个元素1, 第五个元素55) 之间的元素（左闭右开）
// l: {0, 55, 66, 88, 2, 3, 4}// 删除所有值等于特定值的元素
l.remove(88); // l: {0, 55, 66, 2, 3, 4}// 删除满足条件的所有元素（例如，删除所有偶数）
l.remove_if([](int n) { return n % 2 == 0; }); // 使用Lambda表达式
// l: {55, 3}// 删除所有元素
l.clear();

2.5 大小与容量操作

std::list<int> l = {1, 2, 3};
std::cout << l.size(); // 3
std::cout << l.empty(); // false (0)l.resize(5); // 将大小增大到5，新增的元素默认初始化为0 -> {1, 2, 3, 0, 0}
l.resize(2); // 将大小减小到2，尾部的元素被丢弃 -> {1, 2}
l.resize(4, 99); // 将大小增大到4，新增的元素初始化为99 -> {1, 2, 99, 99}// list 没有 capacity() 和 reserve() 概念，因为内存是动态按需分配的。

2.6 splice：转移元素的神器

// 将另一个list的元素转移到本list中，不涉及元素的拷贝或移动，只改变指针。
std::list<int> list1 = {1, 2, 3};
std::list<int> list2 = {4, 5, 6};auto it = list1.begin();
std::advance(it, 1); // it 指向 2// 1. 转移整个list2到list1的it位置之前
list1.splice(it, list2);
// list1: {1, 4, 5, 6, 2, 3}
// list2: (空)// 2. 转移另一个list中的单个元素
std::list<int> list3 = {7, 8, 9};
auto it3 = list3.begin(); // it3 指向 7
list1.splice(list1.begin(), list3, it3); // 将list3的it3元素转移到list1开头
// list1: {7, 1, 4, 5, 6, 2, 3}
// list3: {8, 9}// 3. 转移另一个list中的一个元素范围
std::list<int> list4 = {10, 11, 12, 13};
auto first4 = list4.begin(); // 10
auto last4 = first4;
std::advance(last4, 2); // 12
list1.splice(list1.end(), list4, first4, last4); // 转移[10, 11)（左闭右开）
// list1: {7, 1, 4, 5, 6, 2, 3, 10, 11}
// list4: {12, 13}

2.7 sort：成员函数排序

std::list<int> l = {3, 1, 4, 1, 5};
l.sort(); // 默认升序 -> {1, 1, 3, 4, 5}
l.sort(std::greater<int>()); // 传入比较函数，降序 -> {5, 4, 3, 1, 1}
// 使用成员函数sort而不是std::sort，因为它通过修改指针链接而非移动元素来排序，对list更高效。

2.8 merge：合并两个已排序的list

std::list<int> listA = {1, 3, 5};
std::list<int> listB = {2, 4, 6};
listA.merge(listB); // 将listB合并到listA中，两个list都必须已按升序排序。
// listA: {1, 2, 3, 4, 5, 6}
// listB: (空)

2.9 unique：去除连续的重复元素

std::list<int> l = {1, 1, 2, 3, 3, 3, 2, 1};
l.sort(); // 先排序 -> {1, 1, 1, 2, 2, 3, 3, 3}
l.unique(); // 去除连续的重复元素 -> {1, 2, 3}
// 可以传入自定义的二元谓词来判断两个元素是否“重复”

2.10 循环

2.10.1 范围-based for 循环 (C++11+)
#include <iostream>
#include <list>int main() {std::list<int> numbers = {1, 2, 3, 4, 5};// 只读访问for (int num : numbers) {std::cout << num << " ";}// 输出: 1 2 3 4 5// 修改元素for (int& num : numbers) {num *= 2; // 每个元素乘以2}// 再次输出for (int num : numbers) {std::cout << num << " ";}// 输出: 2 4 6 8 10return 0;
}
2.10.2 使用迭代器循环
#include <iostream>
#include <list>int main() {std::list<std::string> fruits = {"Apple", "Banana", "Cherry"};// 正向迭代器for (auto it = fruits.begin(); it != fruits.end(); ++it) {std::cout << *it << " ";}// 输出: Apple Banana Cherry// 常量迭代器for (auto cit = fruits.cbegin(); cit != fruits.cend(); ++cit) {std::cout << *cit << " ";}return 0;
}

3、常见问题

  1. list 和 vector 的区别？各自的适用场景？
  • vector：
    • 优点：连续存储，支持快速随机访问(O(1))，缓存友好（ locality of reference ）。
    • 缺点：在非尾部位置插入删除效率低(O(n))，动态扩容有性能成本。
    • 场景：需要高效随机访问，不经常在中间插入删除，元素数量变化相对可预测。
  • list：
    • 优点：在任何位置插入删除都是常数时间(O(1))，操作不会使其他迭代器失效（除了被删除的）。
    • 缺点：不支持随机访问（访问需要O(n)），内存开销大（每个元素都需要额外的指针空间），缓存不友好。
    • 场景：需要频繁在任意位置进行插入删除，且不需要随机访问（如实现链表结构、频繁调整的序列）。

  1. 为什么 list 有自己的 sort 成员函数？
    标准算法std::sort要求随机访问迭代器（因为它需要像begin() + n这样的操作），而list的迭代器是双向迭代器，不支持随机访问。因此，list提供了自己的sort成员函数，它使用归并排序的变体，只通过迭代器的增量和递减来操作，时间复杂度也是O(n log n)。

  2. std::list 为什么不支持 operator[]？
    因为 std::list 是双向链表，元素存储在非连续内存中，无法通过指针算术直接计算第 n 个元素的地址，必须从表头/表尾遍历（O(n) 时间），不符合 operator[] 预期的 O(1) 效率，因此 STL 设计时未提供该操作。

  3. std::list 的 size() 方法时间复杂度是 O(1) 吗？

    • C++11 之前：部分实现（如 GCC）中 size() 需遍历链表计数（O(n)），因维护一个 size 成员会增加插入/删除的开销。
    • C++11 之后：标准强制要求 size() 为 O(1)，实现中通过一个 size_t 成员变量实时记录元素数量。

  4. std::list 与 std::forward_list 的区别？

    • std::list 是双向链表，支持双向遍历和首尾操作。
    • std::forward_list 是单向链表（C++11 新增），仅支持正向遍历，内存开销更小（每个节点仅 1 个指针），但功能更有限（无 back()、pop_back() 等）。

  5. 如何选择 std::list 与 std::vector？
    核心看操作类型：

    • 若以随机访问或尾部操作为主：选 vector。
    • 若以任意位置插入/删除为主：选 list。
    • 若元素数量固定：优先选 std::array 或 vector（空间效率更高）。
http://www.wxhsa.cn/company.asp?id=5397

相关文章：

  • 函数是编程范式的原理是什么？
  • 能耐高温400度密封圈用什么材质
  • 【IEEE出版|Fellow云集】第五届电气工程与机电一体化技术国际学术会议（ICEEMT 2025）
  • APDU笔记
  • AR眼镜：远程协作的“破局者”，让困难解决“云手帮”
  • 跨网文件摆渡系统功能全解析
  • 跨平台代码同步新时代：Gitee携手GitHub打造开发者高效协作生态
  • CTFer
  • 家政小程序源码一站式开发：助力家政企业数字化转型
  • Gitee推出跨平台镜像功能：一键同步GitHub仓库，开发者协作效率提升50%
  • DeClotH: Decomposable 3D Cloth and Human Body Reconstruction from a Single Image
  • 在 Streamable HTTP 传输模式下启动并测试 MCP Serverr （二）
  • 从0到1上手阿里云ARMS：让Java服务监控变得简单
  • 聚焦实用：内外网文件摆渡系统品牌推荐来了！
  • 生物活性肽：从基础研究到治疗应用的潜力与挑战，及计算机辅助筛选的关键作用
  • MySQL视图定义者和安全性definer/invoker的区别
  • 软件测试day2
  • 软件测式学习
  • 担心安全与速度？这份跨网文件传输方式推荐清单请收好！
  • kettle基本操作3：剪切原字段末尾的空格符
  • Guid g = Guid.Empty;Guid.TryParse(, out g);
  • 【IEEE出版|上海理工大学】第六届大数据、人工智能与物联网工程国际会议（ICBAIE 2025）
  • MDI Jade9.0中文版详细下载及安装教程，附免费免激活版MDI Jade安装包！！
  • C++ std::vector
  • RC-Explainer | Reinforced Causal Explainer for Graph Neural Networks
  • 批量遍历文件夹内得文件生成md5值
  • 使用源码启动 seata tc server
  • OpenLDAP 常见命令行命令及解析
  • 自动化http请求脚本
  • 绕过亚马逊儿童版家长控制的技术漏洞分析