【C++】list 链表的使用+模拟实现

文章目录

前言

一、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);}
}