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

List（3）

news 来源：原创 2025/9/11 14:39:03

前言

上一节我们讲解了list主要接口的模拟实现，本节也是list的最后一节，我们会对list的模拟实现进行收尾，并且讲解list中的迭代器失效的情况，那么废话不多说，我们正式进入今天的学习

list的迭代器失效

之前在讲解vector的时候，我们提到了迭代器失效这一个概念。list中其实也存在迭代器失效的情况，但是不同于vector，在list中调用insert函数不会造成迭代器失效

		list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();lt.insert(it, 10);*it += 10;print_container(lt);

可以看到，这里并没有产生问题

而对于vector而言，在插入一个数据以后，我们可以认为插入数据的位置后面的所有迭代器都失效了。因为vector是存储在一个连续的物理空间中的，只要插入一个数据，就要对整个数组中的内容进行挪动。而list在插入数据的时候，迭代器it并没有改变。因为list存储空间是不连续的，对数据的插入完全不会影响插入位置后面的数据

但是list的erase函数也存在迭代器失效的问题。我们就举和学习vector迭代器失效一模一样的例子来说明list的迭代器失效：

假设我们要删除list中所有的偶数：

		list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();lt.insert(it, 10);*it += 10;auto it = lt.begin();while (it != lt.end()){if (*it % 2 == 0){lt.erase(it);}++it;}print_container(lt);

这里运行代码不成功。之所以运行不成功，是因为如果我们要删除pos位置的数据，就对应的把pos节点中指向下一个节点的指针也删除了，此时pos前一个位置的数据无法找到pos的下一个数据，就不能实现链表的遍历，并且产生了野指针

所以我们要修改erase函数，让它执行完删除操作以后，返回下一个位置的迭代器（这与库中erase函数的实现一致）

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

这里我们直接返回next，让它走隐式类型转换变成迭代器类型

接着来修改一下测试代码：

		list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);auto it = lt.begin();while (it != lt.end()){if (*it % 2 == 0){it = lt.erase(it);}else{++it;}}print_container(lt);

（因为形式和代码含义与vector中的很像，所以就不做过多讲解了）

list析构函数的模拟实现

要想实现链表的析构，就需要遍历链表，并且一个接一个的释放节点，这里提供一个很简单的思路：

首先需要实现一个很简单的接口clear，注意clear不清除哨兵位的头节点。

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

对于析构函数的实现就只需要调用clear接口，并且释放哨兵位的头节点即可

list拷贝构造函数的实现

我们根据理解，可能会采取复用push_back函数的方式来实现list的拷贝构造函数，但是此时我们写出测试用例检测的时候会发现无法成功运行：

		list(const list<T>& lt){for (auto& e : lt){push_back(e);}}

		list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int> lt2(lt1);print_container(lt1);print_container(lt2);

这里需要注意到：push_back需要有哨兵位的头节点，而在lt2中什么都没有，所以要在这里添加哨兵位的头节点，我们在类中创建一个名为empty_init的函数，用于对空链表的初始化，顺便可以调整一下构造函数，让它复用empty_init函数，简化代码：

		void empty_init(){_head = new Node(T());_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}

最后调整一下拷贝构造函数，让它也走空初始化

		list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}

list的赋值重载函数

之前学习vector的时候学习了赋值重载函数的现代写法，那么就根据现代写法也来完成list的赋值重载函数吧：

首先还是需要自己实现一个swap函数：

		void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}

		list<T>& operator=(list<T> lt){swap(lt);return *this;}

依旧注意参数不能传引用，具体实现的细节可参照vector，这里就不做过多赘述了

list中多参数的初始化

之前在初始化时，我们一直采取的是push_back的形式，但是库中还支持有一种多参数的初始化方式（C++11）：

		std::list<int> lt1 = { 1,2,3,4,5 };print_container(lt1);

那么这种初始化方式是怎么实现的呢？

我们先来查看一下库中文件的说明：

这里是调用了initializer_list这个类来实现的初始化：

		initializer_list<int> il = { 1,2,3,4 };//或者写作auto il = { 1,2,3,4 };cout << typeid(il).name() << endl;cout << sizeof(il) << endl;

它的底层实现大致如下：它会根据初始化的内容，在栈上开辟一个数组。这个对象有两个指针，一个指针指向开始，一个指针指向结束（所以说initializer_list这个对象在32位下有8个字节，因为有两个指针）

initializer_list中有迭代器成员，但是这里的迭代器只能读不能写

要想在list类中实现这样的初始化方式，我们就还需要重载一个构造函数，构造函数的参数如下：

		list(initializer_list<T> il)

随后我们再调用空初始化给链表一个头节点的哨兵位。最后调用范围for，把initializer_list中的数据一一插入至链表之中（注意这里尽量使用&，因为不知道类型，使用&可以避免过量拷贝）

		list(initializer_list<T> il){empty_init();for (auto& e : il){push_back(e);}}

我们来写一下测试代码：

		list<int> lt1 = { 1,2,3,4,5 };//实际写法为list<int> lt1({1,2,3,4,5});print_container(lt1);

实际上下面的写法才是标准的写法，上面的写法是隐式类型的转换，因为有隐式类型转换这种形式，所以我们在给函数传参数的时候就有这样的方法：

	void func(const list<int>& lt){print_container(lt);}void test_list3(){func({ 1,2,3,4,5 });}

这种初始化方式实际上是根据python的写法来模仿的

结尾

那么到这节为止，list的所有内容就结束了，下一节我们将分析栈和队列的STL，希望可以给你带来帮助，谢谢您的浏览！！！！！！！！！！！！！！！！！！！！！！

前言

list的迭代器失效

list析构函数的模拟实现

list拷贝构造函数的实现

list的赋值重载函数

list中多参数的初始化

结尾

相关文章：