网站导航
> 技术文档 > 【C++强基篇】学习C++就看这篇---＞STL之list使用及实现

【C++强基篇】学习C++就看这篇---＞STL之list使用及实现

网友: 技术文档 2025-07-30 12:28:53

主页：HABUO🍁主页：HABUO

🍁C++入门到精通专栏🍁

🍁如果再也不能见到你，祝你早安，午安，晚安🍁

目录

📕一、list的介绍

📕二、list的使用  

✨2.1 构造与初始化 

✨2.2 list iterator （迭代器）的使用 

✨2.3 list 容量查询 

✨2.4 list 元素访问

✨2.5 list 修改操作

✨2.6  迭代器失效问题 

📕三、list的简单模拟实现   

📕四、总结

前言： 

上篇博客我们了解了STL中的vector类，本篇博客我们继续对STL中的容器进行学习，这篇博客我们来了解list，学习思路与前面的string和vector是一样的，第一步就是：是什么怎么用，第二步就是我们能不能自己实现一个简单的vector（即为了了解它的底层原理），经过这两步的学习之后，应对绝大多数的场景已经足够使用。经过之前的string与vector的学习，list学起来是相对比较轻松的，因为各种接口的使是相差不大的。但是要是理解它底层的原理还是有点难度，但是也不大，因为毕竟链表大家前面学习数据结构也有相对的了解，它不像顺序表或者字符串那样可以随机的访问，因此是有差别的。只要认真点，问题不大，希望大家有所收获！

📕一、list的介绍

std::list 是 C++ 标准模板库（STL）提供的双向链表容器。它支持在任意位置高效插入和删除元素，但不支持随机访问。定义在头文件  中，是 std::list 模板类的实例。

🌟 核心特性（相比 vector/deque）

  • 双向链表结构：每个元素包含数据值、前驱和后继指针

  • 任意位置 O(1) 插入/删除：已知迭代器位置时高效

  • 迭代器稳定性：插入/删除操作不会使其他元素的迭代器失效（被删除元素除外）

  • 非连续内存：元素分散存储，不需要大块连续内存

  • 无容量概念：动态增长，每次插入只分配一个节点

  • 双向遍历：支持前向和后向迭代器

我们可以思考一下为什么要有list？

我们先看vector的缺点：

1. 头部和中间插入删除数据效率是比较低的。O(N)，因为需要挪动数据

2. 插入数据空间不够需要增容，增容开辟空间，拷贝数据、释放旧空间，付出代价是比较大的。

优点：

1. 支持下标的随机访问，间接的就很好的支持排序、二分查找、堆算法等等。

list为什么要出现就是要解决vector所不能解决的事情。

list优点：

1. list头部、中间插入或删除不需要挪动数据，效率高，O(1)

2. list插入数据是新增节点，不需要增容。

缺点：

1. 不支持随机访问。

因此list与vector是相辅相成的，在实际的使用当中是互补的。

📕二、list的使用  

 📂 头文件与命名空间

#include  // 必须包含的头文件using namespace std; // 或显式使用 std::list

类似于string与vector，我们学习使用主要针对的就是，定义：构造（无参的有参的）、拷贝构造。修改：insert、erase、push_back、pop_back、resize、reserve、operator=。输出：operator[]。结束：析构。下面我们；来一一介绍。 

✨2.1 构造与初始化 

构造函数声明 接口说明 list(size_type n, const value_type& val = value_type()) 构造包含 n 个值为 val 的元素的 list list()（重点） 构造空的 list list(const list& x)（重点） 拷贝构造函数 list(InputIterator first, InputIterator last) 用 [first, last) 区间中的元素构造 list 
std::list lst1; // 空链表std::list lst2(5, 100); // 5个值为100的元素std::list lst3 = {1, 2, 3}; // 初始化列表 (C++11)std::list lst4(lst3); // 拷贝构造std::list lst5(arr, arr+3); // 从数组构造 [C风格]

✨2.2 list iterator （迭代器）的使用 

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。 （等到下面介绍list模拟实现的时候就会知道实际上它是一个自定义的封装类型）

函数声明 接口说明 begin + end（重点） begin：返回第一个元素的迭代器；end：返回最后一个元素下一个位置的迭代器 rbegin + rend rbegin：返回最后一个元素的 reverse_iterator（即 end 位置）；rend：返回第一个元素前一个位置的 reverse_iterator（即 begin 位置） 
// 双向迭代器for (auto it = lst1.begin(); it != lst1.end(); ++it) { // 前向遍历}for (auto rit = lst1.rbegin(); rit != lst1.rend(); ++rit) { // 反向遍历}// C++11 范围for循环for (int val : lst1) { // 顺序访问}

✨2.3 list 容量查询 

函数声明 接口说明 empty 检测 list 是否为空，是返回 true，否则返回 false size（重点） 返回 list 中有效节点的个数 
bool empty = lst1.empty(); // 是否为空size_t size = lst1.size(); // 元素数量lst1.resize(10);  // 调整大小 (增/删尾部元素)

✨2.4 list 元素访问

函数声明 接口说明 front（重点） 返回 list 第一个节点中值的引用 back（重点） 返回 list 最后一个节点中值的引用 
int front = lst2.front(); // 首元素 (不检查空)int back = lst2.back(); // 尾元素 (不检查空)// 迭代器访问 (无随机访问操作符 [])auto it = lst3.begin(); // 指向第一个元素std::advance(it, 2); // 移动迭代器 (O(n))int val = *it; // 获取值

✨2.5 list 修改操作

函数声明 接口说明 push_front（重点） 在 list 首元素前插入值为 val 的元素 pop_front（重点） 删除 list 中第一个元素 push_back（重点） 在 list 尾部插入值为 val 的元素 pop_back（重点） 删除 list 中最后一个元素 insert（重点） 在 list 的 position 位置插入值为 val 的元素 erase（重点） 删除 list 中 position 位置的元素 swap（重点） 交换两个 list 中的元素 clear（重点） 清空 list 中的有效元素 
// 添加元素lst1.push_front(10); // 头部插入lst1.push_back(20); // 尾部插入auto pos = lst1.begin();lst1.insert(pos, 15); // 指定位置插入// 删除元素lst1.pop_front(); // 删除头部lst1.pop_back(); // 删除尾部lst1.erase(pos); // 删除指定位置lst1.remove(100); // 删除所有值为100的元素lst1.clear(); // 清空链表// 链表专有操作lst1.splice(lst1.end(), lst2); // 将lst2所有元素移动到lst1尾部lst1.merge(lst3); // 合并有序链表 (需先排序)lst1.sort(); // 排序 (成员函数)lst1.reverse(); // 反转链表

✨2.6  迭代器失效问题 

上篇博客在介绍vector时就遇到了迭代器失效的问题，vector中的迭代器失效本质原因就是，要么1. 空间变了，但是我们的迭代器（指针）没有跟着变，导致还在指向原始的空间（已经交给操作系统） 要么2. 空间没变，但是内容变了（如erase）删除元素之后的所有元素会向前移动（内存位置改变），后续操作 ++it 或解引用* it 会导致未定义行为（程序崩溃或数据错误）

在list中迭代器失效，就和vector有些差别，如insert、push_back等添加内容时就不会导致迭代器失效的问题，因为牵扯不到增容以及挪动数据的问题， 但是erase会导致迭代器失效，因为只要其中的一个节点被删除了，那这个节点的空间就交还给了操作系统，那迭代器还在指向那块空间，当然就不行了，所以解决办法也和vector是一致的只需更新一下迭代器即可。

因此总结一下：判断一个迭代器是否失效就是看这个迭代器所指向的内容是否发生了本质意义的变化，如果发生变动那就失效了，没发生就没失效。

📕三、list的简单模拟实现   

在list中最重要的便是迭代器的实现，上面我们就提到了，链表在数据结构大家都学过，实现起来不难，但是它的迭代器我们怎么可以像前面vector、string那样用起来，它毕竟不是连续的空间，只是逻辑上让我们觉得是连续的，但实际上不是，所以实现了迭代器也就完成了list的模拟实现。

 templatestruct __list_iterator{//const迭代器就是不能修改，但是如果要写的话就必须重新再写一个类型，这样代码复用率不高，因此下面就有一个很巧妙的写法typedef __list_node Node;typedef __list_iterator Self;Node* _node;__list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator++(int){Self tmp(*this);//_node = _node->_next;++(*this);return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self& operator--(int){Self tmp(*this);//_node = _node->_next;--(*this);return tmp;}bool operator!=(const Self& it){return _node != it._node;}};

剖析：

上面有个非常巧妙的地方就是  template，这个模板，让我们既可以实现iterator也可以实现const_iterator，只需要在list类里面这样做

typedef __list_iterator iterator;typedef __list_iterator const_iterator;

它就会自动根据你传参的类型进行匹配，如果不这样做就只能在写一份const_iterator的代码，这样代码复用率就不高。

部分接口实现：

 void insert(iterator pos, const T& x) {Node* newnode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* next = cur->_next;Node* prev = cur->_prev;prev->_next = next;next->_prev = prev;delete cur;cur = nullptr;return iterator(next);}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}

补充小知识点：

1. 左值（lvalue）与右值（rvalue）

  • 左值（lvalue）：有持久状态的对象（有名称的变量），可以出现在赋值语句的左侧

int a = 10; // a 是左值int* p = &a; // 可以对左值取地址
  • 右值（rvalue）：临时对象（没有名称），即将被销毁的值
42;  // 字面量是右值a + 5; // 表达式结果是右值func();  // 函数返回的临时对象是右值

2. 非 const 左值引用

  • 只能绑定到左值，不能绑定到右值（临时对象）

int x = 10;int& ref1 = x; // 正确：绑定到左值int& ref2 = 42; // 错误！不能绑定到右值int& ref3 = x+5; // 错误！不能绑定到右值
引用类型 可以绑定到 示例 T& (非 const 左值引用) 仅左值 int x; int& r = x; const T& (const 左值引用) 左值和右值 const int& r1 = x; const int& r2 = 42; T&& (右值引用) 仅右值 int&& r = std::move(x);

如果需要其它接口实现，更详细的请见本人代码库：

 https://gitee.com/hanaobo/c-learningcode/blob/master/list_simulate/list.h

学到这里，有几个问题想必大家游刃有余。

1、vector和list的区别?
2、vector和list底层是如何实现的?
3、vector是如何增容的?
4、什么是迭代器失效?

1. 这个问题在本篇博客的开头

2. 请看上述内容以及上篇博客

3. vector博客也已经进行了讲述【C++强基篇】学习C++就看这篇---＞STL之vector使用及实现

4. 两篇博客均有在讲

📕四、总结

这篇博客我们了解学习了list。 std::list 是 STL 的双向链表，支持 O(1) 插入/删除，但不支持随机访问。常用函数：构造（空、n个值、拷贝、区间、初始化列表）、容量（empty/size/resize）、访问（front/back）、修改（push_front/pop_front、push_back/pop_back、insert/erase、clear、splice/merge/sort/reverse）。迭代器为双向，支持 begin/end、rbegin/rend；范围for遍历。注意：erase 会失效迭代器，需接收返回值更新。模拟实现核心是自定义节点和迭代器模板，利用 Ref/Ptr 区分普通与 const 版本，重载 *、++、--、!= 等，实现链式遍历。最重要的就是它的迭代器，希望大家仔细的理解加记忆！

网络标签：

相关问题