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

【C++】- 掌握STL List类：带你探索双向链表的魅力

news 来源：原创 2025/6/12 19:34:30

在这里插入图片描述

文章目录

前言：
一.list的介绍及使用
- 1. list的介绍
- 2. list的使用
- - 2.1 list的构造
  - 2.2 list iterator的使用
  - 2.3 list capacity
  - 2.4 list element access
  - 2.5 list modiﬁers
  - 2.6 list的迭代器失效
二.list的模拟实现
- 1. list的节点
- 2. list的成员变量
- 3.list迭代器相关问题
- - 3.1 普通迭代器
  - 3.2 const迭代器
- 4. list的成员函数
- - 4.1 list的空初始化
  - 4.2 push_back
  - 4.3 构造函数
  - 4.4 insert
  - 4.4 erase
  - 4.5 push_front
  - 4.6 pop_front
  - 4.7 pop_back
  - 4.8 clear
  - 4.8 析构函数
  - 4.9 swap
  - 4.10 赋值运算符重载
最后想说：

前言：

C++中的List容器是标准模板库（STL）中的一种序列容器，它实现了双向链表的功能。与数组（如vector）和单向链表相比，List容器提供了更加灵活的元素插入和删除操作，特别是在容器中间位置进行这些操作时。

一.list的介绍及使用

1. list的介绍

双向链表结构： list容器使用双向链表来存储元素，每个元素（节点）都包含数据部分和两个指针，分别指向前一个元素和后一个元素。这种结构使得在链表的任何位置进行插入和删除操作都非常高效，时间复杂度为O(1)。
动态大小： list容器的大小可以在运行时动态改变，即可以在程序运行过程中添加或移除元素。
不支持随机访问： 与vector和array等连续内存的容器不同，list不支持随机访问迭代器，不能直接通过索引获取元素，而需要通过迭代器遍历。
迭代器稳定性： 在list中插入或删除元素不会导致其他迭代器失效（除了指向被删除元素的迭代器）。这是因为它通过调整相邻节点的指针来维护链表结构，而不需要移动元素或重新分配内存。

2. list的使用

list的使用参考文档：list的文档介绍
在这里插入图片描述

2.1 list的构造

构造函数	接口说明
list (size_type n, const value_type& val =value_type() )	构造的list中包含n个值为val的元素
list()	构造空的list
list (const list& x)	拷贝构造函数
list (InputIterator ﬁrst, InputIterator last)	用[ﬁrst, last)区间中的元素构造list

代码演示：

#include<list>
int main()
{list<int> l1;//构造空的l1;list<int> l2(4,100);//l2中存放4个值为100的元素list<int> l3(l2.begin(),l2.end());//用l2的[begin,end）左开右闭区间构造l3;list<int> l4(l3);//用l3拷贝构造l4// 以数组为迭代器区间构造l5int array[] = { 16,2,77,29 };list<int> l5(array, array + sizeof(array) / sizeof(int));// 列表格式初始化C++11list<int> l6{ 1,2,3,4,5 };// 用迭代器方式打印l5中的元素list<int>::iterator it = l5.begin();while (it != l5.end()){cout << *it << " ";++it;}cout << endl;// C++11范围for的方式遍历for (auto& e : l5)cout << e << " ";cout << endl;return 0;
}

2.2 list iterator的使用

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。

函数声明	接口说明
begin	返回第一个元素的迭代器
end	返回最后一个元素下一个位置的迭代器
rbegin	返回一个指向容器中最后一个元素的反向迭代器（即容器的反向起始）
rend	返回一个反向迭代器，该迭代器指向列表容器中第一个元素之前的理论元素（该元素被认为是其反向结束）。

注意：

begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

代码演示：

int main()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));// 使用正向迭代器正向list中的元素// list<int>::iterator it = l.begin();   // C++98中语法auto it = l.begin();                     // C++11之后推荐写法while (it != l.end()){cout << *it << " ";++it;}cout << endl;// 使用反向迭代器逆向打印list中的元素// list<int>::reverse_iterator rit = l.rbegin();auto rit = l.rbegin();while (rit != l.rend()){cout << *rit << " ";++rit;}cout << endl;return 0;
}

2.3 list capacity

函数声明	接口说明
front	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数

2.4 list element access

函数声明	接口说明
front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用

2.5 list modiﬁers

函数声明	接口说明
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中的有效元素

代码演示：

#include<iostream>
#include<vector>
using namespace std;void PrintList(const list<int>& l)
{// 注意这里调用的是list的 begin() const，返回list的const_iterator对象for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it){cout << *it << " ";}cout << endl;
}// list插入和删除
// push_back/pop_back/push_front/pop_front
void TestList1()
{int array[] = { 1, 2, 3 };list<int> L(array, array + sizeof(array) / sizeof(array[0]));// 在list的尾部插入4，头部插入0L.push_back(4);L.push_front(0);PrintList(L);// 删除list尾部节点和头部节点L.pop_back();L.pop_front();PrintList(L);
}// insert /erase 
void TestList2()
{int array1[] = { 1, 2, 3 };list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));// 获取链表中第二个节点auto pos = ++L.begin();cout << *pos << endl;// 在pos前插入值为4的元素L.insert(pos, 4);PrintList(L);// 在pos前插入5个值为5的元素L.insert(pos, 5, 5);PrintList(L);// 在pos前插入[v.begin(), v.end)区间中的元素vector<int> v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());PrintList(L);// 删除pos位置上的元素L.erase(pos);PrintList(L);// 删除list中[begin, end)区间中的元素，即删除list中的所有元素L.erase(L.begin(), L.end());PrintList(L);
}// resize/swap/clear
void TestList3()
{// 用数组来构造listint array1[] = { 1, 2, 3 };list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));PrintList(l1);// 交换l1和l2中的元素list<int> l2;l1.swap(l2);PrintList(l1);PrintList(l2);// 将l2中的元素清空l2.clear();cout << l2.size() << endl;
}int main()
{TestList1();TestList2();TestList3();return 0;
}

运行结果：
在这里插入图片描述

2.6 list的迭代器失效

前面已经说过了，此处可以将迭代器理解为类似于指针的东西，迭代器失效即迭代器指向的节点失效了，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list进行插入操作时不会导致迭代器失效，只有删除时才会失效，并且失效的是被删除节点的迭代器，其他迭代器不会受到影响。

二.list的模拟实现

1. list的节点

template<class T>
struct list_node
{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr){}
};

2. list的成员变量

template<class T>
class list
{typedef list_node<T> Node;
public://成员函数
private:Node* _head; //哨兵位的头节点
};

没有用访问限定符限制的成员class默认是私有的，struct默认是公有的，如果一个类既有公有也有私有就用class，全部为公有一般用struct。这不是规定，只是个惯例。

3.list迭代器相关问题

简单分析：
&emsp；这里不能像以前一样给一个结点的指针作为迭代器，如果it是typedef的节点的指针，it解引用得到的是节点，不是里面的数据，但是我们期望it解引用是里面的数据，++it我们期望走到下一个节点去，而list中++走不到下一个数据，因为数组的空间是连续的，++可以走到下一个数据。但是链表达不到这样的目的。所以原身指针已经无法满足这样的行为，怎么办呢？这时候我们的类就登场了
用类封装一下节点的指针，然后重载运算符，模拟指针。
例如：

reference operator*()const
{return (*node).data;
}
self& opertor++()
{node = (link_type)((*node).next);return *this;
}

3.1 普通迭代器

template<class T>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T> Self;Node* _node;list_iterator(Node* node):_node(node){}T& operator*() //用引用返回可以读数据也可以修改数据{return _node->_data;}T* operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}
};

3.2 const迭代器

const迭代器在定义的时候不能直接定义成typedef const list_iterator<T> const_iterator,const迭代器的本质是限制迭代器指向的内容不能被修改，而前面的这种写法限制了迭代器本身不能被修改，所以迭代器就不能进行++操作。那该怎能办呢？答案是我们可以实现一个单独的类：

template<class T>
struct list_const_iterator
{typedef list_node<T> Node;typedef list_const_iterator<T> Self;Node* _node;list_const_iterator(Node* node):_node(node){}const T& operator*(){return _node->_data; //返回这个数据的别名，但是是const别名，所以不能被修改}const T* operator->(){return &_node->_data; //我是你的指针，const指针}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}
};

普通法迭代器与const迭代器的区别就是：普通迭代器可读可写，const迭代器只能读
上面是我们自己实现的普通迭代器和const迭代器，用两个类，并且这两个类高度相似，下来就让我们一起看一看库里面是怎么实现的吧！

在这里插入图片描述
我们可以看到库里面是写了两个模板，让编译器去生成对应的类。其本质上也是写了两个类，只不过是让编译器去生成对应的类。

迭代器不需要我们自己写析构函数、拷贝构造函数、赋值运算符重载函数，因为这里要的是浅拷贝，例如我把一个迭代器赋值给另外一个迭代器，就是期望两个迭代器指向同一个节点，这里用浅拷贝即可，拷贝给你我们两个迭代器就指向同一个节点。

4. list的成员函数

4.1 list的空初始化

void empty_init() //空初始化
{_head = new Node();_head->_next = _head;_head->_prev = _head;
}

4.2 push_back

//普通版本
void push_back(const T& x)
{Node* new_node = new Node(x);Node* tail = _head->_prev;tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;
}
//复用insert版本insert(end(),x);

4.3 构造函数

list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr)
{}

4.4 insert

iterator insert(iterator position; const T& val)
{Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;//prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);
}

4.4 erase

iterator erase(iterator pos)
{assert(pos != end());Node* del = pos._node;Node* prev = del->_prev;Node* next = del->_next;prev->_next = next;next->_prev = prev;delete del;return iterator(next);
}

4.5 push_front

void push_front(const T& x)
{insert(begin(), x);
}

4.6 pop_front

void pop_front()
{erase(begin());
}

4.7 pop_back

void pop_back()
{erase(--end());
}

4.8 clear

void clear()
{auto it = begin();while (it != end()){it = erase(it);}
}

4.8 析构函数

~list()
{clear();delete _head;_head = nullptr;
}

4.9 swap

void swap(list<T>& tmp)
{std::swap(_head, tmp._head);//交换哨兵位的头节点
}

4.10 赋值运算符重载

//现代写法
//lt2=lt3
//list<T>& operator=(list<T> lt)
list& operator=(list lt) //不加模板参数
{swap(lt);//交换就是交换哨兵位的头节点return *this;
}//lt3传给lt去调用拷贝构造，所以lt就和lt3有一样大的空间一样大的值，lt2很想要，也就是/this想要，lt2之前的数据不想要了，交换给lt,此时lt2就和lt3有一样大的空间一样大的值，
//lt出了作用域就被销毁了

构造函数和赋值运算符重载函数的形参和返回值类型可以只写类名 list，不需要写模板参数，这种写法在类里面可以不加，只能在类里面可以这样写，类外面是不行的，一般情况下加上好一点。

最后想说：

本章我们STL的List就介绍到这里，下期我将介绍关于stack和queue的有关知识，如果这篇文章对你有帮助，记得点赞，评论+收藏，最后别忘了关注作者，作者将带领你探索更多关于C++方面的问题。

文章目录

前言：

一.list的介绍及使用

1. list的介绍

2. list的使用

2.1 list的构造

2.2 list iterator的使用

2.3 list capacity

2.4 list element access

2.5 list modiﬁers

2.6 list的迭代器失效

二.list的模拟实现

1. list的节点

2. list的成员变量

3.list迭代器相关问题

3.1 普通迭代器

3.2 const迭代器

4. list的成员函数

4.1 list的空初始化

4.2 push_back

4.3 构造函数

4.4 insert

4.4 erase

4.5 push_front

4.6 pop_front

4.7 pop_back

4.8 clear

4.8 析构函数

4.9 swap

4.10 赋值运算符重载

最后想说：

相关文章：