一，list的介绍

1，list初步

（1）list是 C++ 标准模板库 (STL) 中的一个双向链表容器。它允许在常数时间内进行任意位置的插入和删除操作，但不支持随机访问。

（2）list容器的底层数据结构为带头双向循环链表，list的元素可以存储在非相邻的内存中，所以list在插入和删除元素中有着独特的优势，其时间复杂度仅为常数。

注意：list还需要额外的存储空间来存储前一个元素和后一个元素

头文件：

#include<list>

2，list的特点

优点：（1）list在插入和删除操作过程中不会使得迭代器失效，仍旧可以对迭代器遍历和操作。

（2）list可以动态的存储数据，可以有效地处理大量数据并且不会浪费过多的空间

补充：list和数据结构中的快速排序算法的平均时间复杂度是一样的，都是，但是快速排序的最坏情况的时间复杂度为，比list要快。

缺点：（1）list在访问元素的时候需要从头遍历链表，时间复杂度为O（n），因此在随机访问元素时效率低下

（2）内存占用相比其他容器更大，list需要额外的指针维护链表

（3）list不支持指针算术运算，无法像指针那样给进行加减操作

3，list的底层

我们想要观察list的源代码，可以通过everything这个小软件打开

通过将这个文件拖拽到VS上就可以观察到list头文件的源代码

通过观察list头文件中的一些函数，我们可以发现list的底层，这里拿clear举例

我们通过这种方法，可以发现list的底层是一个带头双向循环链表

使用结点指针达不到迭代器的功能：当一个it是指向结点的指针的时候，对it解引用得到的是这个结点而不是值，同时it++也不可以保证到下一个位置，因为下一个位置我们无法确定其地址与本结点的大小

解决方案：用一个类型对结点指针进行封装，再对结点指针和++两个操作进行重载

insert的源代码

创建一个tmp新的结点，tmp结点中next指针指向pos结点，tmp结点中的pre指针指向pos结点中的pre指针（即前一个结点），同时将pos前一个结点的next指针指向tmp，pos处结点的pre指针指向tmp，完成插入一个新的元素。

这与链表中插入思想是一样的

补充：在链表底层中_prev和_next被定义为void*类型的，所以取节点指针时要先强转一下，所以才会出现（link_type(.....）这种情况。

4，迭代器分类

迭代器分类依据之一是其移动方式，与容器的底层结构有关。

迭代器正常下有五种：输入迭代器，输出迭代器，前向迭代器，双向迭代器，随机访问迭代器

这里我们有另一种迭代器分类方式：单向，双向和随机

单向迭代器（Forward Iterator）：仅仅支持++操作，不支持--和随机访问，同时单向迭代器是可读可写的（常量是只读）

双向迭代器（Bidirectional Iterator）：支持++和--操作，但是不支持随机访问，同时双向迭代器是可读可写的（常量是只读）

随机访问迭代器（Random Access Iterator）：支持+，-，+=，-=等算术运算，支持下标访问和双向迭代器的所有功能，同时还支持距离运算和比较运算

一些STL库的迭代器类型：

那么我们怎样知道这些容器的迭代器类型的呢？

string

list

vector

我们可以发现算法的迭代器参数类型，暗示了要求的迭代器类型。

二，list的定义

我们可以发现list的定义要求：

template <class T, class Allocator = allocator<T>>

T是指存储的元素类型，如int,char，结构体或者STL容器等

allocator是内存分配器

代码例子：

list<int>lt;

我们再通过调试观察其结构：

三，list容器的接口

1，list的构造

在标准库中定义图

（1）构造一个类型的空容器

list<int> lt; //构造int类型的空容器

（2）构造一个含有n个val值的一个类型容器

list<int>lt(7,7)//构造含有7个元素为7的int类型容器

（3）拷贝构造某类型容器

list<int>lt(lt1);//拷贝构造int类型的lt1容器

(4)迭代器拷贝构造某一段数据

string v("Manchester United");
list<char> lt(v.begin(),v.end()); //构造string对象某段迭代器区间的内容

(5)构造数组某段区间内容

int arr[] = { 1, 2, 3, 4, 5 };
int sz = sizeof(arr) / sizeof(arr[1]);
list<int> lt5(arr, arr + sz); //构造数组某一段数据

(6)使用花括号构造内容

list<int> lt{ 1,2,3,4,5 };  // 直接使用括号进行构造

在C++11中引入使用

2，list遍历

（1）迭代器

除此以外还有cbegin，drend等等，这些在vector中我们已经做过接触，这里就不再细述了

正向迭代器

反向迭代器

我们可以借用rbegin和rend来实现

（2）for循环

迭代器是一定支持范围for操作的

3，list的容量操作

（1）我们可以发现list容器中没有capacity()操作和reserve()操作，这是因为链表不需要提前分配内存

（2）list容量操作中resize时间复杂度为O(n)，其余操作时间复杂度为O(1)

size

empty

resize

resize 有两种重载方式

代码展示：

clear

4，list的成员接口

这些操作大家可以自己课下一一尝试，这里就不给大家挨个展示了，只展示重点接口

insert

我们可以发现这里insert的接口很多，这里只介绍三种经典的接口即第一个，第二个和第四个

（1）在指定位置插入单个元素

iterator insert(const_iterator pos, const T& value);

代码展示：

（2）在指定位置插入多个相同元素

iterator insert(const_iterator pos, size_type count, const T& value);

代码展示：

（3）在指定位置插入另一个容器的元素范围

template<class InputIt>
iterator insert(const_iterator pos, InputIt first, InputIt last);

代码展示：

erase

我们可以看到erase有两种接口

（1） 删除单个元素（通过迭代器）

iterator erase(const_iterator pos);

代码展示：

（2）删除元素范围（通过迭代器范围）

iterator erase(const_iterator first, const_iterator last);

代码展示：

注意：类似于begin和end这类区间都是左闭右开的

5，list容器的特殊操作

splice

（1）移动单个元素

void splice(const_iterator pos, list& other, const_iterator it);

代码展示：

（2）移动元素范围 

void splice(const_iterator pos, list& other, const_iterator first, const_iterator last);

代码展示：

（3）移动整个链表 

void splice(const_iterator pos, list& other);

代码展示：

remove

（1）删除所有等于指定值的元素

void remove(const T& value);

代码展示：

remove_if

（1）删除满足条件的元素

template <class Predicate>
void remove_if(Predicate pred);

代码展示：

unique

（1）删除连续重复元素

void unique();

代码展示：

（2）自定义去重规则

template <class BinaryPredicate>
void unique(BinaryPredicate pred);

代码展示：

merge

（1）默认升序合并

void merge(list& other);

代码示例：

（2）自定义排序规则合并

template <class Compare>
void merge(list& other, Compare comp);

代码示例：

sort

（1）默认升序排序

void sort();

代码展示：

（2）自定义排序规则

template <class Compare>
void sort(Compare comp);

代码展示：

reverse

（1）反转链表元素顺序

void reverse();

代码展示：

四，list的模拟实现

带头双向循环链表结点

一般定义一个类都用class，但是当我们不用访问限定符进行限制成员的时候，用struct

那么为什么？

因为在链表中我们在模拟实现中其实用到的不是结点的指针，而是通过一个迭代器访问这个链表的。

之所以不用指针，是因为不同平台对list中的链表规定不同

template<class T>
struct list_node
{list_node* _prev;list_node* _next;T _data;
};

链表的初始化

class list
{typedef list_node<T> node;//将结点私有化，外界访问结点的时候只能通过上面的list_node访问
public:list(){_head = new node;_head->_next = _head;_head->_prev = _head;}
private:node* _head;//哨兵位头结点};

构造函数

list_node(const T& x=T())//要注意哨兵位初始化时的值的类型是不确定的，所以这里可以写成匿名对象或者全缺省: _next(nullptr), _prev(nullptr), _data(x)
{ }

链表迭代器模板类型框架

通过迭代器结构体模拟目标指针行为，从而遍历链表，再定义类型别名方便后续使用，随后node*_node来保存当前指向的链表节点的指针

template<class T>
struct list_iterator
{typedef list_node<T>node;node* _node;
};

链表迭代器

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;}// 重载前置++操作符self& operator++() {           //移动到下一个节点_node = _node->_next;return *this;              }//重载后置++操作符self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}//重载前置++操作符self& operator--(){_node = _node->_prev;return *this;}//重载后置++操作符self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}//重载不等比较操作符bool operator != (const self & s) const{return _node != s.node;}//重载相等运算符bool operator==(const self& s) const{return _node == s._node;}
};

typedef list_iterator<T>iterator;//将底层迭代器起别名，这说明上层的迭代器相似，但其实底层迭代器实现方式是不同的iterator begin()
{return iterator(_head->_next);
}
iterator end()
{return iterator(_head);
}

测试用例：

list<int>::iterator it = lt.begin();  //获取指向链表首元素的迭代器
while (it != lt.end()) {              //循环直到链表末尾*it += 10;                        //修改当前元素值cout << *it << " ";               //输出当前元素++it;                             //移动到下一个元素
}

图解：

这里的拷贝就是浅拷贝，不需要写析构函数了：

（1）链表迭代器本质就是对原生指针_node的封装，不能影响链表本身结点生命周期

（2）链表节点的创建和销毁由链表容器管理，如果迭代器释放会出现释放两次的情况，影响链表本身内存

push-back实现

思路：

找到尾结点，新增一个尾结点，将newnode的prev指向tail，next指向_head，同时tail的_next指向newnode,_head的prev指向newnode

这个方法优势是可以不必区分链表空或者非空

当链表为空的时候

按上述思路仍可以进行

代码展示：

提示：这串代码是不完整的，库函数，类的定义等等作者都忽略了，大家自己补充或者看后文的完整版代码即可。

void push_back(const T& x)
{node* tail = _head->_prev;node* newnode = new node(x);tail->_next = newnode;newnode->_prev = tail;newnode->next = _head;_head->_prev = newnode;
}

测试用例

list<int>lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);

insert实现

void insert(iterator pos, const T& x) {node* cur = pos._node;      //获取当前位置对应的节点指针node* prev = cur->_prev;    //找到前驱节点node* newnode = new node(x); //创建新节点（假设node构造函数接受T值）// 调整指针关系：prev->_next = newnode;      //前驱节点的next指向新节点newnode->_prev = prev;      //新节点的prev指向前驱newnode->_next = cur;       //新节点的next指向原节点cur->_prev = newnode;       //原节点的prev指向新节点
}

insert不需要检查迭代器，因为所有结点都可以插入

借用insert实现头插，尾插等

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

erase实现

void erase(iterator pos) {assert(pos != end());      //确保不删除尾哨兵节点node* cur = pos._node;    //获取要删除的节点node* prev = cur->_prev;  //前驱节点node* next = cur->_next;  //后继节点// 调整指针：prev->_next = next;       //前驱节点直接指向后继next->_prev = prev;       //后继节点直接指向前驱delete cur;               //释放目标节点内存
}

借用erase实现头删和尾删

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

上述的测试用例大家自己写自己测试即可。

那么list的插入和删除是否有迭代器失效的情况呢？

list的insert不存在迭代器失效，但是list的erase存在迭代器失效的问题。

因为insert只是进行链表的插入操作，修改局部结点的指针不会使得内存重新分配，因而不存在迭代器失效的问题。

erase会使被删除元素的迭代器失效，因为erase操作会删除结点，使得其前后结点的next和prev指针变成野指针，但是其仅仅影响被删除元素结点，不影响其他结点的地址和其他迭代器。

析构函数

~list()
{clear();delete _head;//哨兵位头结点也要释放掉_head = nullptr;
}void clear()
{auto it = begin();while (it != end())//哨兵位的头结点不清除{it = erase(it);}
}

size

size_t size()
{return _size;
}

这里要补充一个私有成员变量size，来完成size函数

同时要在insert和erase中对size进行更改

深拷贝构造函数

初始化链表

void empty_init() {_head = new Node;       //创建头哨兵节点（不存储有效数据）_head->_next = _head;   //next指向自己_head->_prev = _head;   //prev指向自己_size = 0;              //大小置零
}

拷贝构造函数

// lt2(lt1)
//list(const list<T>& lt)  这里const对象要用const对象的迭代器
list(list<T>& lt)
{empty_init();          //初始化空链表for (auto& e : lt) {   //遍历源链表push_back(e);      //逐个元素尾插}
}

初始化列表构造链表

list(initializer_list<T> il)  //初始化列表参数
{empty_init();             //初始化空链表结构for (auto& e : il)        //遍历初始化列表{push_back(e);         //将每个元素添加到链表尾部}
}

swap

void swap(list<T>& lt) {std::swap(_head, lt._head);  // 交换头指针std::swap(_size, lt._size);  // 交换元素计数
}

交换的是当前链表*this和目标链表lt

拷贝赋值

list<T>& operator=(list<T> lt)  //参数为值传递（会调用拷贝构造）
{swap(lt);                  //交换当前对象与副本的内容return *this;              //返回当前对象的引用
}

参数创建时会隐式调用拷贝构造函数创建lt

const对象

注意const迭代器不要在最前面加上const，这样修饰的是整个迭代器，但是我们要求的是const迭代器不是本身不能被修改，而是指向的内容不能被修改

所以我们要对operator*进行操作，使得其解引用不能被修改就可以达到目的

typedef list_const_iterator<T> const_iterator;

同样在struct中也要随之改变

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;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& s) const{return _node != s._node;}bool operator==(const self& s) const{return _node == s._node;}
};

但是我们发现两个类是有点冗余的，而且我们发现这个类只有个别的类型不同，所以我们可以考虑复用，借用Ref模板参数完成这项工作

同时，我们也有疑惑，就是箭头操作怎么重载？这里可以再添加一个模板参数，来接收和生成

// typedef list_iterator<T, T&, T*> iterator;// typedef list_iterator<T, const T&, const T*> const_iterator;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++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const self& s) const{return _node == s._node;}};

通过复用我们就完成了一个通用的双向链表迭代器模板，实现了普通迭代器和常量迭代器的统一处理。

五，list失效问题

迭代器失效即迭代器所指向的节点的无 效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入 时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭 代器，其他迭代器不会受到影响。

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的反向迭代器

反向迭代器的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++， 因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对 正向迭代器的接口进行包装即可。

template<class Iterator>
class ReverseListIterator
{// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态
成员变量// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:typedef typename Iterator::Ref Ref;typedef typename Iterator::Ptr Ptr;typedef ReverseListIterator<Iterator> Self;
public:// 构造ReverseListIterator(Iterator it): _it(it){}// 具有指针类似行为Ref operator*(){Iterator temp(_it);--temp;return *temp;}Ptr operator->(){    return &(operator*());}// 迭代器支持移动Self& operator++(){--_it;return *this;}Self operator++(int){Self temp(*this);--_it;return temp;}Self& operator--(){++_it;return *this;}Self operator--(int){Self temp(*this);++_it;return temp;}// 迭代器支持比较bool operator!=(const Self& l)const{ return _it != l._it;}bool operator==(const Self& l)const{ return _it != l._it;}Iterator _it;
};

七，list和vector的比较