C++之list类（超详细）

在上一节中我们学习了STL中的vector这个容器，这节我们来学习一下另外一个常用的容器——list。

文章目录

前言

一、list的介绍

二、list的使用及相关接口

1.list的使用

2.list的迭代器使用

3.list的相关接口

3.1 list capacity

3.2 list element access

3.3 list modifiers

三、list与vector的对比

四、list的模拟实现

---

前言

我们在vector中就已经介绍了C++中引入了STL的方便，这里我们就不多赘述了。我们上节所学习的vector，这个容器使用于那个存储空间连续的结构，因为它的底层设计是数组实现的。对于那些存储空间不连续的结构，如我们在数据结构中所学习的链表，它是有一个一个的指针连接起来的，这里我们就来学习一下这种容器——list。

---

一、list的介绍

上面这个介绍是引入C++文档指导的，我们从上面的文档中，我们可以知道list就是一个允许在任意位置进行插入/删除的序列容器，它同样可以使用迭代器，因此我们可以通过迭代器轻松遍历list中的内容。

如上图所示，我们在C++中所学习的list就是我们在数据结构中学习的带头双向循环链表，因此我们可以往前遍历，也可以往后遍历。因此它的头结点是一个关键的结点，我们要注意，后面我们在list的模拟实现中会着重介绍这个的。

二、list的使用及相关接口

1.list的使用

我们现在如果想要使用C++中的STL都是需要提前写出它们的头文件，并把它们包含起来，那么在主函数中，我们就可以直接使用它们了。list的头文件包含就是#include<list>，我们包含这个头文件之后，我们不仅可以使用list的迭代器还可以使用它的各种接口。

对于list对象的创建和之前的vector是一样的，我们在实例化对象时，我们写类类型的时候，我们要将类模板与数据类型一起写上去，这样才能够算是一个数据类型。

template<class T> //我们定义类模板中的元素类型
list<T>   //这就是一个list对象的数据类型

对于list的构造函数同样有好几种函数原型：

如上图所示，我们可以构造一个空的list，也可以构造一个包含n个值为val的元素的list,我们还可以使用迭代器区间中的元素来构造list，除了上面哪几种构造函数，我们其实还可以使用初始化列表来初始化list中的内容，初始化列表就是使用一对{ },里面放置的是我们想要进行初始化的内容。（这种构造方法我觉得挺香的，可以自己来初始化想要的内容，不然我们还得创建一个空的list，然后再逐个插入元素，才能得到我们想要的list)

2.list的迭代器使用

这里我们可以将迭代器认为是一个指针，但是它实际上比不是指针，只是功能与指针很相似，这点我们需要注意，我们学习就将它们进行一下类比学习。list中的迭代器与我们vector迭代器不一样，由于vector中的存储空间是连续的，因此它的迭代器就相当于原生指针，使用起来十分方便，但是list的存储空间不连续，那么它的迭代器就不能用原生指针来代替。这里我们只是来初步介绍一下如何使用list的迭代器，至于list中的迭代器是如何实现的，我们在后面的模拟实现中会着重讲解的。

对于容器的使用方式都是一个模板，我们首先先使用我们想要的容器类型来定义一个迭代器变量并给它初始化，我们一般把第一个迭代器作为初始值。后面我们根据自己的需求来使用迭代器。对于list的迭代器，我们就将容器类型换成list<int>即可。如下代码是我们使用list迭代器进行遍历访问list中的元素。

对于迭代器的函数基本都是一样的，如下图中的那几个函数就是迭代器的接口函数，我们根据不同的场合进行使用。

 

注意：

1.begin,end是正向迭代器函数，我们实行++操作的时候，迭代器向后移动；

2.rbegin,rend是反向迭代器函数，我们实行++操作的时候，迭代器向前移动。

3.list的相关接口

3.1 list capacity

对于list容器，它没有像vector,string那样的capacity函数，因为list是一个存储空间不连续的结构，因此它的容量大小，我们无法通过函数接口来获取，我们只能得到它当前的元素个数size，以及list是否为空。这两个接口使用起来也是十分简单的，和之前几种容器的使用方法一样，我们直接调用函数即可。

3.2 list element access

我们在介绍list的时候就已经说了list是一个带头双向循环链表。因此对于它有两个元素我们是可以直接获取的：表头元素，表尾元素。我们可以分别使用front和back这两个函数来获取。

3.3 list modifiers

list中那些增删函数与vector中的函数接口基本差不多，两者上面主要的区别就是list可以在表头，表尾进行插入/删除，而vector只能够进行尾删/尾插操作。它们两个都没有了find函数了（string类中有find函数），它们如果想要使用这个函数，可以直接使用库中的find函数,对于库中的find函数，原型如下所示：

输入参数：我们要输入一个迭代器区间，还有一个我们想要查找的值。我们一般使用这个函数使用下面这个模板(以list举例）：

#include<algorithm>
#include<iostream>
#include<list>
using namespace std;
int main()
{int x;cin >> x;auto it = find(lt.begin(), lt.end(),x);  //auto 推导出来的是迭代器类型return 0;
} 

如下代码，是插入/删除等函数的代码演示：

对于insert/erase这两个函数，我要好好来介绍一下。这里list中的insert/erase函数，它们的返回值类型都是迭代器类型(这里vector中的也是一样的）。而且我们传递的参数也是迭代器类型的参数或者迭代器区间。在vector中对于insert/erase中都会出现迭代器失效的情况，但是在list中insert并不会出现迭代器失效的情况，只有erase才会使得迭代器失效。因为我们在前面已经说了list是一个带头双向循环链表，这里迭代器失效即迭代器所指的结点无效，即该结点被删除了。因此插入结点时迭代器是不会失效的（我们每次插入的结点都是一个新的结点，都是有效的迭代器），而且erase导致迭代器失效的也只是指向被删除的那个结点的迭代器失效了，其他的结点并没有被影响。

这是文档中list::insert的介绍，我们传递的参数是迭代器位置，我们插入的位置是我们传递的迭代器位置的前一个迭代器位置，这一点我们要记住。至于它的返回值就是我们插入的位置的迭代器。

这是文档中list::erase的介绍，我们传递的参数迭代器就是我们想要删除位置的迭代器，但是它的返回值我们要注意了，它的返回值是我们被删除位置的下一个位置的迭代器。我们在vector中就说过了如何解决迭代器失效的方法：更新迭代器的值。因此，我们为了保证迭代器不会失效，我们可以将erase的函数返回值赋值给迭代器，那样迭代器进行了更新，就不会出现迭代器失效的情况了。

void TestListIterator1()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
其赋值l.erase(it);  ++it;}
}
// 改正
void TestListIterator()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it++);    // it = l.erase(it);}
}

三、list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及 应用场景不同，其主要不同如下：

四、list的模拟实现

#pragma once#include<assert.h>namespace hjc
{// 惯例// 全部都是公有，一般用structtemplate<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){}};// typedef list_iterator<T, T&, T*> iterator;// typedef list_iterator<T, const T&, const T*> const_iterator;template<class T, class Ref, class Ptr> //我们定义模板的时候，我们定义多个参数//我们除了定义元素类型的参数，还定义一个引用类型的参数和一个指针类型的参数//这个对于我们后面实例化出普通迭代器与const迭代器有着奇效struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;  //重命名的时候，我们要将上面模板中定义的参数都带上Node* _node;list_iterator(Node* node):_node(node){}//下面重载*和—>运算符的使用，我们要使用上面定义的参数作为返回值//因为，我们普通迭代器与const迭代器的区别就是在这解引用，我们const修饰的是迭代器所指向的内容即顶层constRef 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> iterator;typedef list_const_iterator<T> const_iterator;*///本质上还是实现了两个迭代器的类，这里不过是我们传递给模板参数，然后编译器帮我们实例化出来两种迭代器typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}//begin,end函数需要我们自己来重新定义，上面模板生成的迭代器，只是对那些运算符进行了重载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;  //初始化时，size=0}list(){empty_init();}// lt2(lt1)  拷贝构造，我们传递的参数是类类型的引用类型//我们先对其初始化，然后我们将值逐个插入到我们要拷贝的链表中list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}// lt2 = lt3//list& operator=(list lt)//对于赋值运算符的重载，我们可以直接将两个链表中的内容交换（交换一下头指针即可）list<T>& operator=(list<T> lt){swap(lt);   //使用我们自己实现的swap函数  这里实际是    this.swap(lt)return *this; //这是赋值后的链表内容，原来的链表内容交换给了lt//由于lt是一个局部变量，在这个函数结束的时候，然后它就自动销毁了}//~list(){clear();delete _head;_head = nullptr;}//链表中的交换函数（直接交换两个头指针即可）std中的swap函数则需要重新创建两个空间，然后分别将值拷贝过去void swap(list<T>& tmp){std::swap(_head, tmp._head);std::swap(_size, tmp._size); //两个链表中的有效元素个数也要进行交换}//使用迭代器+erase直接将链表中的元素都删除掉，但是这里可能会导致迭代器失效的情况，因此我们需要对迭代器进行更新//erase函数的返回值类型是迭代器类型，返回的迭代器是被删除的紧接着的下一个迭代器位置void clear(){auto it = begin();while (it != end()){it = erase(it);  //因此我们直接将erase的返回值赋给it,这样就相当于对迭代器更新+向后移动一位了}}//构造函数（构造n个相同值）list(size_t n, const T& val = T()){empty_init();//初始化 for (size_t i = 0; i < n; i++) //由于这里已经明确给了多少个元素了，于是我们就使用普通的for循环来插入值{push_back(val);}}//尾插 我们首先要定义一个要插入的新结点，然后找出插入结点与头结点等结点的关系//使用使用指针连续关系即可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(end(), x);  //我们可以直接使用insert来进行复用//end()即_head位置，这里是头结点之前的位置，即链表尾的位置}void push_front(const T& x){insert(begin(), x);  //begin()=>_head->_next，头结点的下一结点位置}void pop_front(){erase(begin());}void pop_back(){erase(--end());  //--end()指向的是头结点的上一个元素，即链表的最后一个元素}//插入位置是我们指定位置（pos)之前一个位置插入元素iterator insert(iterator pos, 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;++_size;return iterator(newnode);}//返回的位置为被删除位置的下一个迭代器位置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;--_size;return iterator(next);}private://这里，我们定义了两个成员变量，一个头指针，一个是元素的有效个数//size我们直接定义为成员变量，在上面的函数中如果有修改的地方我们就直接进行修改Node* _head;size_t _size;};//函数模板，这是std库中的//这个函数模板需要重新创建空间，然后拷贝内容过去template <class T>void swap(T& a, T& b){T c(a); a = b; b = c;}//这是list库中的swap函数模板template <class T>void swap(list<T>& a, list<T>& b)  //传递两个链表类型的引用作为参数{a.swap(b); //实际是对我们上面那个swap的函数的一个封装，写这个函数是想让编译器优先使用这个函数，而不用上面那个函数模板}
}

对于上面的list的模拟实现，我主要讲解一下，迭代器的模拟实现。由于list是个链表由一个个的节点所组成的，因此我们并不能够像之前的vector那样，直接使用原生指针typedef即可。我们需要使用类来进行封装。我们要将迭代器的那些操作（运算符的重载）都封装到一个类中，但是迭代器又有还几种迭代器（这里我们就实现比较简单的迭代器：普通迭代器和const迭代器，至于方向迭代器我们这里就暂时不模拟实现）我们知道两种迭代器的实现功能都是不一样的但是又很相似，如果我们为了const迭代器再重写一个类，这样就显得有点冗余（其中许多操作都是相似的，只是几处有所差别）于是，我们就在模板上做点手脚：我们在模板参数中多设定几个参数：一般我们写模板参数时只写一个参数：类中对象的数据类型，这里我们加了两个参数：一个引用类型的参数Ref，一个指针类型的参数Ptr。对于const迭代器，const修饰的是迭代器所指向的内容，我们并不能简单的使用const来修饰我们最初模拟实现的普通迭代器然后typedef就行了。我们需要修改它们解引用操作的那几个运算符，因此我们直接在模板中给定参数，在我们实例化时，我们给定我们想要的参数就行了。其实，我们在模板中多设定几个参数，然后再传递参数来实例化就是让编译器帮我们写两个迭代器的类，这样的粗活就不用我们自己亲自来做了。