目录
文章目录
前言
一、list的简介
二、list的使用方法
三、list的模拟实现
1.基本框架：
2.迭代器实现
3.常用接口实现
四、完整代码
总结
前言
本文主要介绍C++【STL】容器中的 list，包括接口说明和模拟实现。其中讲解了迭代器功能上的分类，让你了解为何 list 要实现这个接口。
一、list的简介
- list就是链表，对应我们在C语言数据结构中学的带头双向循环链表。
- 既然是链表，那么它在内存中就是不连续的，数据由节点组成。
- list为模版类，创建时需要传数据类型类型。
我们接着前面 string 和 vector 继续讲解，因为STL中容器的使用方法很相似，因此我写的比较简洁：
二、list的使用方法
1.list 的构造
常用构造：
| 构造函数 | 接口说明 |
| list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的 元素 |
| list() | 构造空的list |
| list (const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用迭代器[first, last)区间中的元素构造 list |
| list (initializer_list<value_type> il) | 用initializer_list构造 |
简单演示：
#include <iostream>
#include <list>
#include <vector>
using namespace std;int main()
{//(1)list<int> l1(8, 6);for (auto e : l1){cout << e << " ";}cout << endl;//(2)vector<int> v({ 1,2,3,4,5,6,7,8 });list<int>l2(v.begin(), v.end());for (auto e : l2){cout << e << " ";}cout << endl;//(3)list<int> l3({ 1,2,3,4,5,6 });for (auto e : l3){cout << e << " ";}cout << endl;return 0;
}运行结果：
2.list的迭代器、list遍历
迭代器：
- 用法和 string、vector 一样，不赘述。
遍历方式：
（1）迭代器和范围for
#include <iostream>
#include <list>
using namespace std;int main()
{list<int> l1({ 9, 8, 7, 6, 5, 4, 12 });//迭代器遍历auto it = l1.begin();while (it != l1.end()){cout << *it << " ";++it;}cout << endl;//范围for，支持迭代器就支持范围forfor (auto e : l1){cout << e << " ";}cout << endl;return 0;
}
运行结果：
注意：因为 [ ] 对于链式结构的数据来说，效率不高，因此 list 并没有重载 [ ]
3.常见方法
| 函数声明 | 接口说明 |
| size() | 返回list中有效节点的个数 |
| empty() | 检测list是否为空，是返回true，否则返回false |
| front() | 返回list的第一个节点中值的引用 |
| back() | 返回list的最后一个节点中值的引用 |
| push_front (const value_type& val) | 在list首元素前插入值为val的元素 |
| pop_front() | 删除list中第一个元素 |
| push_back (const value_type& val) | 在list尾部插入值为val的元素 |
| pop_back() | 删除list中最后一个元素 |
| emplace_back (Args&&... args) | 模版函数，与push_back大致相同，具体区别下面在讲 |
| insert | 在list position 位置中插入值为val的元素 |
| swap | 交换两个list中的元素 |
| clear | 清空list中的有效元素 |
简单演示：
（1）size、empyt、front、back、push_front、pop_front、pop_back
#include <iostream>
#include <list>
using namespace std;int main()
{list<int> l1({ 1,2,3 });l1.push_front(88);for (auto e : l1){cout << e << " ";}cout << endl;cout << "size: " << l1.size() << endl;cout << "empty: " << l1.empty() << endl;cout << "front: " << l1.front() << endl;cout << "back: " << l1.back() << endl;l1.pop_back();l1.pop_front();for (auto e : l1){cout << e << " ";}cout << endl;return 0;
}运行结果：
- 因为list是链式结构，所以头插头删是没有效率消耗的。
（2）push_back 和 emplace_back 的区别
- 首先 emplace_back 是一个模版函数
用法异同：
#include <iostream>
#include <list>
using namespace std;struct Pos
{int _row;int _col;Pos(int row = 0, int col = 0):_row(row),_col(col){}
};int main()
{list<Pos> l1;list<Pos> l2;Pos p;//push_back支持：l1.push_back(p);l1.push_back(Pos(1, 2));//匿名对象l1.push_back({ 1,2 });//大括号//emplace_back支持：l2.emplace_back(p);l2.emplace_back(Pos(1, 2));l2.emplace_back(1, 2);//支持直接传参l2.emplace_back(1);//支持直接传参return 0;
}
- 简单说：push_back 支持大括号传参
- emplace_back 支持直接传参
（3）insert、erase、迭代器失效问题
在 vector 中，我们接触了迭代器失效的问题，而在 list 中，迭代器失效只会出现在 erase 中
- list中，insert 插入数据迭代器不失效的原因就是，pos 指向的节点没有改变，因为 list 是链式结构，不存在扩容以及原空间销毁等问题。insert（1）的返回值是新节点的迭代器。
- 而在 erase 中，删除节点就等于将迭代器指定的空间销毁，因此 erase 的返回值是被删除节点的下一个节点。
演示：
#include <iostream>
#include <list>
using namespace std;int main()
{list<int> l1;//插入auto it = l1.insert(l1.begin(), 22);cout << *it << endl;//迭代器没有失效l1.insert(l1.end(), 33);l1.insert(l1.end(), 44);l1.insert(l1.end(), 55);for (auto e : l1){cout << e << " ";}cout << endl;cout << endl;//删除，我们可以借助 find 函数来找到需要删除的节点auto del = find(l1.begin(), l1.end(), 44);del = l1.erase(del);//迭代器失效，需要更新迭代器cout << *del << endl;for (auto e : l1){cout << e << " ";}cout << endl;return 0;
}运行结果：
4.特有方法
| 函数声明 | 接口说明 |
| splice | 将另一个list对象中的元素拿出来插入到自己元素中。 |
| remove | 删除指定元素 |
| unique | 删除 list 中重复值，需先排序 |
| merge | 合并两个链表，被合并的链表会变为空，合并前两个链表需先排序 |
| sort | 链表特供的排序 |
| reverse | 逆置 |
（1）sort排序 和 迭代器分类
通过前面 string 和 vector 的学习，我们知道它们两个都没有提供 sort 接口，而是直接使用算法库中的 sort。那么为什么 list 要提供 sort 接口？这里就涉及迭代器分类的问题了。
- 首先，我们可以发现算法库中的 sort 的参数列表，迭代器的名字带有随机的字样。这里的命名其实就提示了使用者该函数需要的迭代器类型了。
- 还有一个原因是 list 需要自己实现 sort 的：
- 我们在 sort 的定义中大致可以看出，算法库中的 sort 为了计算排序元素的个数其实通过地址相减得到的，这对于连续型存储空间的容器来说确实可以，但是 list 是链式结构，因此 list 不能使用算法库中的 sort 来进行排序。
<1.1>迭代器分类
按使用上分类：
- 使用上分类就是我在 string 中讲到的 普通迭代器、const迭代器、反向迭代器等。这是我们按照使用上进行分类的。
按功能性分类：
- 单向迭代器：只支持++，比如 forward_list（单链表）
- 双向迭代器：支持++、--，比如 list（双链表）
- 随机迭代器：支持++、--、+、-，比如 string,vector
从官方文档中也能看到每个容器的迭代器类型：
例如：vector（随机迭代器）
例如：list（双向迭代器）
例如：forward_list（单向迭代器）
- 所以算法库中 sort 的参数名其实就暗示了只有随机迭代器才能使用。
- 当然这里还要注意一点，就是如果一个函数只支持双向迭代器，那么其实随机迭代器也可以使用，我们记住： 随机迭代器 > 双向迭代器 > 单向迭代器，类似包含的关系，如果一个接口支持单向迭代器，那么双向和随机迭代器也可以使用，但如果只支持随机，那么单向和双向都不能使用
例如1：算法库中的 reverse 逆置方法
- 算法库中的 reverse 显示支持双向迭代器，那么 list 其实是可以直接使用算法库中的 reverse，那么为什么还要自己实现一个 reverse，关于这一点应该是效率问题。
例如2：算法库中的 find 接口
- 这里显示的迭代器名称其实是可读迭代器，这涉及另外一种分类，但是其实 find 按功能是支持单向迭代器的，也就是 单向、双向、随机迭代器都可以使用该接口进行查找元素的。
<1.2>对比sort排序效率：
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;int main()
{srand((unsigned int)time(0));const int N = 1000000;vector<int> v1;list<int> l1;for (size_t i = 0; i < N; i++){v1.push_back(rand());l1.push_back(v1[i]);}int begin1 = clock();sort(v1.begin(), v1.end());int end1 = clock();int begin2 = clock();l1.sort();int end2 = clock();cout << "vector_sort: " << end1 - begin1 << endl;cout << "list_sort: " << end2 - begin2 << endl;return 0;
}运行结果：
- 我们可以看到，排一百万个数据时，list 比 vector 多花了3倍多的时间。
- 所以效率上，list 的 sort 是比不上算法库的 sort 的
我们可以试着将 list 的数据拷贝到 vector 进行排序，然后再拷回 list，看看效率如何：
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;int main()
{srand((unsigned int)time(0));const int N = 1000000;vector<int> v;list<int> l1;list<int> l2;for (size_t i = 0; i < N; i++){l1.push_back(rand());}l2.assign(l1.begin(), l1.end());//assign用于重新赋值int begin1 = clock();v.assign(l1.begin(), l1.end());sort(v.begin(), v.end());l1.assign(v.begin(), v.end());int end1 = clock();int begin2 = clock();l2.sort();int end2 = clock();cout << "list_vector_sort_list: " << end1 - begin1 << endl;cout << "list_sort: " << end2 - begin2 << endl;return 0;
}运行结果：
- 我们可以很直观的发现，list 的 sort 效率甚至比不上，list 拷贝给vector排再拷回来的效率。所以我们一般不直接使用 list 的 sort 进行排序，因为效率不高，除非数据量少，一般我们还是拷贝给 vector 进行排序，毕竟连续型空间排序优势很大。
（2）splice、remove、unique、merge 和 reverse 演示
splice：
- （1）将 x 的全部数据插入到自己的 pos 位置，x 中的数据将会清除
- （2）将 x 中 i 位置的数据插入到自己 pos 位置，x 中该数据会删除
- （3）将 x 中的一段迭代器区间的内容插入到 pos 位置，x 中这些数据会删除
简单演示：
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;int main()
{list<int> l1{ 1,2,3,4,5 };list<int> l2{ 6,7,8,9,10 };auto it = find(l2.begin(), l2.end(), 8);l1.splice(l1.begin(), l2, it);for (auto e : l1){cout << e << " ";}cout << endl;for (auto e : l2){cout << e << " ";}cout << endl;return 0;
}运行结果：
uinque、merge:
- 这两个的第二个重载都涉及仿函数，仿函数下篇再讲
- 注意这两个接口使用前，需要先将数据排成有序的。
简单演示：
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;int main()
{list<int> l1{ 5,8,3,3,1,2,2,8 };list<int> l2({ 4, 4, 9, 9, 9, 6, 6, 5 });l1.sort();l2.sort();l1.unique();//删除重复项for (auto e : l1){cout << e << " ";}cout << endl;l2.unique();//删除重复项for (auto e : l2){cout << e << " ";}cout << endl;l1.merge(l2);//合并for (auto e : l1){cout << e << " ";}cout << endl;for (auto e : l2){cout << e << " ";}cout << "没了" << endl;return 0;
}
运行结果：
reverse、remove:
- remove 只要知道元素内容就能删除
演示：
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;int main()
{list<int> l1({ 1,2,3,4,5 });l1.remove(2);//删除for (auto e : l1){cout << e << " ";}cout << endl;l1.reverse();//逆置for (auto e : l1){cout << e << " ";}cout << endl;return 0;
}运行结果：
小结：
- list常用方法当然还有一些，比如关系运算等，这些比较简单就不一一演示了
- 接下来我们就模拟实现 list。
三、list的模拟实现
我们不完全模拟，主要实现出 list 常用的接口，加强印象和使用。
1.基本框架：
namespace txp
{//定义节点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){}};//链表template<class T>class list{typedef list_node<T> Node;//节点public://初始化void empty_init(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;}//默认构造list(){empty_init();}private:Node* _head;size_t _size;};
}节点：
- 首先，依然需要命名空间来与库里的list区分
- 然后，定义节点，我们之前学过链表，链表是由一个个节点连接组成的，既然是双向带头循环链表，那么就有三个成员变量，存储数据的_data，存储下一个节点地址的_next，存储上一个节点的地址_prev。
- 节点 list_node 需要写成模版类，模版参数即是存储数据的类型，然后我们需要手动写一个默认构造，将成员初始化。
- 注意：你可能想知道为啥 list_node 要用 struct 进行定义，这里简单说一下。
使用 struct 定义节点的原因：
- 在学习c++类时，我们知道 c++ 中 struct 和 class 的区别，其实大致上没有区别，c++中 struct 也能定义类。
- 唯一的区别就是如果不加访问限定符，struct 的成员默认是公有的，而 class 不加访问限定符则成员默认是私有的。
- 然后行业内就有一个不成文的规定：假如类中的每个成员都需要写成公有的，那么就用 struct 进行定义，反之则使用 class 进行定义。
- 因为 list_node 的每个成员都需要被频繁的访问，所以 list_node 成员全部为公有成员，故而不加访问限定符，直接使用 struct 进行定义。
链表：
- 链表有两个成员变量，一个是头结点 _head，另一个是记录节点个数的 _size。
- 头结点的类型由节点类决定，因此对节点类进行重命名，这里重命名到链表类中，其实相当于将节点类设置为链表的内部类了，并且重命名在 public 的上面，这样节点就是私有的，对外部来说无法访问。
- 链表的初始化先写到一个函数 empty_init 中，不直接写在构造函数中，是因为构造有很多，为了避免重复写就直接写成一个函数给构造函数调用。
- 初始化：因为是双向带头循环链表，因此头结点是不储存数据的，也就是哨兵位。然后_next 和 _prev 指针初始化时需要指向自己，这样才算是循环链表。
2.迭代器实现
在 string 和 vector 的模拟实现中，迭代器是直接对指针进行重命名的，这样迭代器++、--就能遍历数据了，但是在 list 中，这种方法行不通，因为链表的存储结构是不连续的，在这种情况下，我们该怎么实现迭代器呢？
- 其实之前我们就能发现迭代器很像指针，但我们不能说它就是指针，其实它是对指针的一种封装，面向对象的三大特征之一就是封装，为什么要封装，就是为了通用性，在STL中，迭代器是通用的功能，都叫一个名字，但其实底层实现不一样。
- 对于 list 来说，想要实现迭代器就需要对指针进行封装，封装成一个类，在类中重载 ++、--等操作符，对于迭代器来说，++就是走到下一个数据，那么链表要实现这样的效果，就是将指针指向下一个节点。
- 按照这样的思路，我们实现出 list 的迭代器
//定义迭代器
template<class T, class Ref, class Ptr>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr 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;}//重载==bool operator==(const Self& s){return _node == s._node;}
};
- 首先，迭代器的全部功能都需要公开，因此直接写成 struct 类。
- 迭代器只要一个成员变量 _node，也就是节点指针。
- 然后你会发现迭代器有3个模版参数，这其实是一种巧妙的设计，我们模拟迭代器时一般只模拟两个迭代器：普通迭代器和const迭代器。这两个迭代器在解引用返回值上有差别，const 迭代器解引用返回的是 const 修饰的数据，不能修改。因此，如果只有一个模版参数用来替换数据类型时，那么对于这两个迭代器就需要手动写两个迭代器类了。
- 为了避免再手动写一个高度相似的迭代器类，因此另加两个参数 Ref 和 Ptr。
然后我们在链表中传递不同参数就能得到两种迭代器了：
//链表
template<class T>
class list
{typedef list_node<T> Node;//节点
public:typedef list_iterator<T, T&, T*> iterator;//迭代器typedef list_iterator<T, const T&, const T*> const_iterator;//const迭代器
（注意：迭代器重命名在 public 下方，迭代器需要被外部访问）
其实这样重命名后，编译器会根据模版自动生成两份迭代器类，只是减少了我们的代码量，将本来应该我们写两份迭代器类的工作交给了编译器。
Ref 和 Ptr 只用于解引用操作符* 和 ->中：
- *的重载函数就是返回对应节点的 _data 即可。
- ->的重载函数就需要返回对应节点 _data 的地址了，写法就是前面加个取地址符
关于其他的运算符重载：
- 如前置++、--，其实就是将节点指针移动到下一个节点或者上一个节点即可，后置同理只不过返回的是修改前的地址。
- 另外需要重载的就是 != 和 == 了，!= 就是为了支持我们迭代器遍历，==有时候需要用到。
3.常用接口实现
（1）迭代器
//链表template<class T>class list{typedef list_node<T> Node;//节点public:typedef list_iterator<T, T&, T*> iterator;//迭代器typedef list_iterator<T, const T&, const T*> const_iterator;//const迭代器iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}
- begin() 就是头结点的下一个节点
- end() 就是头结点了
（2）insert
//insert
iterator insert(iterator pos, const T& val)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(val);cur->_prev = newnode;newnode->_next = cur;prev->_next = newnode;newnode->_prev = prev;++_size;return iterator(newnode);
}
- 直接看示意图：
- 最后需要返回新节点的指针。
（3）push_back、push_front
- 我们先实现了insert，那么这两个就可以直接复用insert了
//尾插
void push_back(const T& x)
{//复用写法insert(end(), x);
}//头插
void push_front(const T& val = T())
{insert(begin(), val);
}（4）erase
//erase
iterator erase(iterator pos)
{assert(pos != end());Node* del = pos._node;Node* next = del->_next;Node* prev = del->_prev;next->_prev = prev;prev->_next = next;delete del;del = nullptr;--_size;return iterator(next);
}
- 先改变待删节点的前后节点指向，最后删除。
- 注意，不能删除头结点，使用assert进行断言
- 最后需要返回被删节点的下一个节点的迭代器
（5）pop_back，pop_front
同样，当我们实现了erase后，就可以直接复用
//尾删
void pop_back()
{erase(--end());
}//头删
void pop_front()
{erase(begin());
}
- 注意尾删需要--end()，因为end()返回的是头结点。
（6）size、swap，clear、析构和更多的构造
//size
size_t size()
{return _size;
}//交换
void swap(list<T>& tmp)
{std::swap(_head, tmp._head);std::swap(_size, tmp._size);
}//赋值运算符重载
list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}//clear
void clear()
{auto it = begin();while (it != end()){it = erase(it);}
}//析构
~list()
{clear();delete _head;_head = nullptr;
}//n个val构造
list(size_t n, const T& val = T())
{empty_init();for (size_t i = 0; i < n; i++){push_back(val);}
}//initializer_list构造
list(std::initializer_list<T> il)
{empty_init();for (auto& e : il){push_back(e);}
}//拷贝构造
list(const list<T>& lt)
{empty_init();for (auto& e : lt){push_back(e);}
}
- 这里面需要注意的就是 swap 的操作，swap 本身是通过调用算法库中的swap交换两个list对象的指针和 _size 实现的。
- swap 配合赋值运算符重载，能极大简化代码，这里就是函数参数使用传值传参，这样参数相当完成了拷贝，将参数与自己调换就完成了赋值。
- clear 删除元素，配合析构也能简化代码。
- 其他的就很好理解了，不再赘述
全局的 swap:
//全局的swap
template<class T>
void swap(list<T>l1, list<T>l2)
{l1.swap(l2);
}
- 全局的 swap 存在主要是怕调用到算法库中的 swap，官方的文档中也有实现两个swap。
- 这样一来，当我们不用 对象. 去调用swap，而是直接调用 swap 也能高效的调换两个list对象了
- 关于 list 模拟就实现这么多，当然剩下的你如果有想法可以自己试着实现。
四、完整代码
#pragma once
#include <assert.h>namespace txp
{//定义节点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){}};//定义迭代器template<class T, class Ref, class Ptr>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr 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;}//重载==bool operator==(const Self& s){return _node == s._node;}};//链表template<class T>class list{typedef list_node<T> Node;//节点public:typedef list_iterator<T, T&, T*> iterator;//迭代器typedef list_iterator<T, const T&, const T*> const_iterator;//const迭代器iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}//初始化void empty_init(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;}//默认构造list(){empty_init();}//n个val构造list(size_t n, const T& val = T()){empty_init();for (size_t i = 0; i < n; i++){push_back(val);}}//initializer_list构造list(std::initializer_list<T> il){empty_init();for (auto& e : il){push_back(e);}}//拷贝构造list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}//析构~list(){clear();delete _head;_head = nullptr;}//sizesize_t size(){return _size;}//赋值运算符重载list<T>& operator=(list<T> lt){swap(lt);return *this;}//交换void swap(list<T>& tmp){std::swap(_head, tmp._head);std::swap(_size, tmp._size);}//clearvoid clear(){auto it = begin();while (it != end()){it = erase(it);}}//尾插void push_back(const T& x){//原始写法/*Node* new_node = new Node(x);Node* tail = _head->_prev;tail->_next = new_node;new_node->_prev = tail;_head->_prev = new_node;new_node->_next = _head;*///复用写法insert(end(), x);}//头插void push_front(const T& val = T()){insert(begin(), val);}//尾删void pop_back(){erase(--end());}//头删void pop_front(){erase(begin());}//insertiterator insert(iterator pos, const T& val){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(val);cur->_prev = newnode;newnode->_next = cur;prev->_next = newnode;newnode->_prev = prev;++_size;return iterator(newnode);}//eraseiterator erase(iterator pos){assert(pos != end());Node* del = pos._node;Node* next = del->_next;Node* prev = del->_prev;next->_prev = prev;prev->_next = next;delete del;del = nullptr;--_size;return iterator(next);}private:Node* _head;size_t _size;};//全局的swaptemplate<class T>void swap(list<T>l1, list<T>l2){l1.swap(l2);}
}总结
以上就是本文的全部内容了，感谢支持！