文章目录
- list介绍
- list的使用
- 构造函数（constructor）
- 迭代器
- list capacity
- list modify（修改）
- 其他接口函数
- list迭代器失效问题
- list实现
- 基础框架(节点类）
- 基础框架（迭代器类）
- 基础框架（链表主体类）
- 链表主体函数
二次修改于date：2024：3：20
list介绍
在STL中list底层使用的是双向带头循环链表，这是一个很完善的结构，可以做到在O（1）时间内完成pos位置的插入删除。
唯一的缺点是不支持随机访问，如果要访问list中的第三个元素，只能通过遍历迭代器或者范围for来访问第三个元素。
所以list不支持算法库里面的sort（因为算法库中的sort底层是快速排序，快速排序为了防止最坏的情况也就是已排序好的数据，在这种情况下的效率就是O（N^2)因此引入了三数取中，但是如果不支持随机访问，三数取中就不可以使用了）
要想对sort进行排序只能使用list自带的sort来进行排序，但是list也很少排序，如果是需要排序的数据一般是用顺序表来存储。其次list内置sort效率很低，数据量大的时候甚至不如先将数据拷贝到vector中排序完再拷贝回来。
这是list的双向带头循环链表的一个逻辑结构图
常见的迭代器类型
单向---->只能++，例如：forword_list和unorder_map
双向---->可++和–，例如：list
随机访问---->可以++/–/+/-/+=/-=等任意方式访问，有vector和string
在文档中根据迭代器名称可以判断出，当前函数支持什么类型的迭代器，这几个迭代器从上到下满足继承关系，单向的迭代器可以调用的函数双向的迭代器一定也可以，但是双向可以调用的函数单向的不一定能调用。
list的使用
构造函数（constructor）
C++这里提供了四种构造函数
1.不传参数构造空链表（也就是只有一个头结点）alloc是空间配置器，也就是内存池
2.使用n个val来构造链表
3.使用了一个迭代器区间来构造（左闭右开），可以是其他容器的迭代器来构造链表
4.拷贝构造
#include<iostream>
#include<list>
#include<string>
using namespace std;
template<class T>
void Print(T& tmp)
{
typename T::iterator it = tmp.begin();
while (it != tmp.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
int main()
{
list<int> l1;
list<int> l2(10, 6);
string s("hello kisskernel");
list<char> l3(s.begin(), s.end());
Print(l1);
Print(l2);
Print(l3);
return 0;
}
这里实现了一个可以打印任意类型容器的模板打印函数，在访问模板内的内嵌类型的时候，如果不加typename就会报错，因为模板在没有实例化之前是不能取模板的内嵌类型的，这时候编译器根本就不认识T，也不知道T是什么类型，取内嵌的iterator就会报错。所以前面加上了typename就是告诉编译器这个参数是个模板类型，等实例化之后再去里面取内嵌类型。
迭代器
list的迭代器和其他容器一样的不多赘述。
虽然迭代器的使用类似指针的操作，在前面的vector和string中迭代器也确实就是指针，但是list迭代器如果单单是指针的话，不能满足list这里的迭代器要求，比如it++如果时原生指针就时地址++，并不能跳到下一个节点。
所以list的迭代器封装了节点的指针，然后通过重载运算符来完成迭代器的操作，包括后面的map和set也是类似的。
迭代器的价值：
- 封装底层实现，不暴露底层细节
- 统一访问方式，减少学习成本
算法中的函数模板理论上都是通用的，传什么迭代器都是可以的，但是因为算法中可能用到了不同的迭代器操作，有一些迭代器可能不支持这些操作，比如sort需随机访问，list的iterator是不支持的。
注意：begin的位置就是第一个节点的位置，end的位置是最后一个节点的下一个位置，也就是头结点（哨兵位）的位置。
结构如下：
begin是正向迭代器的开始，++向着逆时针移动。
rbegin是反向迭代器的开始，++向着顺时针方向移动
反向迭代器：关于反向迭代器，这里为了让end和rbegin保持一致，所以他们都是指向头结点的，但是rbegin解引用拿到的是最后一个节点4，这是因为反向迭代器的实现重载*的时候是返回的前一个位置的值。所以rend解引用拿到的就是头结点（这里会报错，这也证明了拿到的确实就是头节点）。
list capacity
1.判断链表是否为空（用迭代器begin和end判断是不是相等的就可以了，相等就是空）
2.返回链表的元素个数（可以遍历链表来计数，也可在成员中加一个_size来记录，插入就++，删除就–）
list modify（修改）
修改函数只需要了解框选出来的即可。
1.push_front头插
2.popfront头删
3.push_back尾插
4.pop_back尾删
5.insert随机插入（在pos位置之前插入）
返回值是新插入的元素的第一个位置（如果只插入一个元素，就返回这个插入的元素的位置）。
6.erase删除
返回的迭代器是最后一个被删除的位置的下一个位置的迭代器。如果已将容器最后一个元素删除那么返回的就是end()；
7.swap交换
8.clear清空链表
其他接口函数
assign就是将对象重新赋值，第一个就是将容器内的数据清空然后将这个迭代器区间内的数据插入进去，第二个就是清空然后插入n个val
splice的意思就是拼接结合的意思。将一个容器的元素接合到另一个容器中。
1.将x容器内的元素全部接合到调用容器的position位置。
2.将x容器内的i之后的元素接合到pos位置。
3.将x容器[ first，last）的这个区间接合到pos位置。
list迭代器失效问题
list底层是双向带头循环链表，使用迭代器插入一个节点并不会导致迭代器失效，因为插入的节点不会导致其他节点的物理地址的变换。使用erase删除一个节点同样也不会导致迭代器失效，只会导致删除的这个节点失效。
list实现
需要了解list容器总共有几部分组成，list内成员，就是一个指针，指向双向带头循环链表的头节点。然后将节点封装成一个类。vector和string的迭代器都可以使用原生指针来实现，因为他们的存储空间是连续的，++ 或者-- 后就能找到附近的元素，但是list的存储空间是不连续的。
所以list的原生指针行为不能满足list对于迭代器的定义，就需要通过类来封装原生指针，重载运算符来实现迭代器功能。这里一共需要三个类，list，_list_node , _list_iterator。
正因为使用类封装迭代器重载了运算符，所以在使用的时候可以不需要关注容器底层到底是数组，链表或者是树形结构，都可以使用简单统一的方法来访问修改容器，这其实就是迭代器的意义。
基础框架(节点类）
//封装节点类
template<class T>
struct _list_node
{
typedef _list_node<T> node;
_list_node(const T& val = T())
:_val(val)
,_next(nullptr)
,_prev(nullptr)
{}
T _val;
_list_node* _next;
_list_node* _prev;
};
基础框架（迭代器类）
//封装迭代器类
template<class T,class Ref, class Ptr>
struct _list_iterator
{
typedef _list_node<T> node;
typedef _list_iterator<T,Ref,Ptr> self;
_list_iterator(node* pnode)
:_pnode(pnode)
{}
Ref operator*()
{
return _pnode->_val;
}
Ptr operator->()
{
return &_pnode->_val;
}
//前置++
self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
//后置++
//临时对象不能返回引用
self operator++(int)
{
self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
//前置--
self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
//后置--
self operator--(int)
{
self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
bool operator==(const self& it)
{
return _pnode == it._pnode;
}
bool operator!=(const self& it)
{
return _pnode != it._pnode;
}
self& operator+(int x)
{
while (x--)
_pnode = _pnode->_next;
return *this;
}
self& operator-(int x)
{
while (x--)
_pnode = _pnode->_prev;
return *this;
}
node* _pnode;
};
基础框架（链表主体类）
//list主体类
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;
//.................
private:
node* _head;
};
迭代器类使用了三个模板参数，主要为了适配const对象而加上了两个对象。因为如果是const对象，调用operator*（）的时候返回的必须是const T&，使得这个对象只能读不能写。如果像前面那样直接写成函数重载，这里就会有问题了，因为迭代器并不是const类型的所以只有返回值类型不相同的两个函数是不能构成函数重载的。
还有方法，就是再写一个const_iterator类，但是这个类除了除了operator*（）和operator->这两个函数的返回值不同以外，其他的函数都是相同的，所以代码会有很多的冗余。
这就要使用模板，将这两个函数的返回值都写成模板参数，const和非const只需要在模板实例化的时候控制就可以了，实际上还是生成了两个类，但是这是编译器替我们写的，并不需要我们自己动手。
链表主体函数
//迭代器
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
return iterator(_head->_next);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator end() const
{
return const_iterator(_head);
}
//
//构造函数
list()
{
empty_initialize();
}
list(size_t n, const T& val = T())
:_head(nullptr)
{
file_initialize(n, val);
}
list(int n, const T& val = T())
:_head(nullptr)
{
file_initialize(n, val);
}
template<class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_initialize();
InputIterator it = first;
while (it != last)
{
push_back(*it);
++it;
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}
//copy construct
list(const list<T>& lt)
:_head(nullptr)
{
empty_initialize();
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}
list<T>& operator=(list<T> tmp)
{
swap(tmp);
return *this;
}
//析构
~list()
{
clear();
delete _head;
_head = nullptr;
//cout << _head << endl;
}
//自定义类型交换
void push_back(const T& x)
{
node* newnode = new node(x);
node* tail = _head->_prev;
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
void push_front(const T& x)
{
insert(begin(), x);
}
iterator insert(iterator pos, const T& x)
{
node* newnode = new node(x);
node* cur = pos._pnode;
node* prev = (pos._pnode)->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return pos;
}
iterator erase(iterator pos)
{
node* cur = pos._pnode;
node* next = cur->_next;
node* prev = cur->_prev;
prev->_next = next;
next->_prev = prev;
delete cur;
return next;
}
iterator pop_front()
{
return erase(_head->_next);
}
iterator pop_back()
{
return erase(_head->_prev);
}
void clear()
{
node* cur = _head->_next;
while (cur != _head)
{
node* next = cur->_next;
delete cur;
cur = next;
}
_head->_next = _head;
_head->_prev = _head;
}
//
size_t size() const
{
size_t count = 0;
node* cur = _head->_next;
while (cur != _head)
{
count++;
cur = cur->_next;
}
return count;
}
bool empty() const
{
return _head->_next == _head;
}
//
T& front()
{
return _head->_next->_val;
}
T& back()
{
return _head->_prev->_val;
}
void empty_initialize()
{
_head = new node;
_head->_prev = _head;
_head->_next = _head;
}
void file_initialize(size_t n, const T& val)
{
empty_initialize();
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
在编写成员函数的时候要注意重复冗余的代码可以抽离出来实现成为单独的函数，使用的地方进行调用，逻辑相近的代码可以复用，比如写完insert和erase，头插头删尾插尾删都可以复用。这样不仅代码简洁，而且可维护性更好。
下面着重说一下迭代器重载的operator->的作用。
比如这里有一个类date
class date
{
public:
date(int year = 0, int month = 1, int day = 1)
:_year(year)
,_month(month)
,_day(day)
{}
int _year;
int _month;
int _day;
};
如果list里面存放的是date类对象，要输出的时候就会遇到问题，想要只输出year，只能先解引用然后再使用点来访问date里面的数据。
void test5()
{
xzj::list<date> ld;
ld.push_back({ 1900,2,28 });
ld.push_back({ 1901,3,29 });
ld.push_back({ 1902,4,20 });
ld.push_back({ 1903,5,20 });
xzj::list<date>::iterator it = ld.begin();
while (it != ld.end())
{
cout << (*it)._year << endl;
++it;
}
}
指针访问结构体里面的数据都是使用->那么在这里我们也可以使用->只需要重载->操作符
Ptr operator->()
{
return &_pnode->_val;
}
有了上面的重载我们就可以直接使用->来访问date对象内的数据了
void test5()
{
xzj::list<date> ld;
ld.push_back({ 1900,2,28 });
ld.push_back({ 1901,3,29 });
ld.push_back({ 1902,4,20 });
ld.push_back({ 1903,5,20 });
xzj::list<date>::iterator it = ld.begin();
while (it != ld.end())
{
cout << it->_year << endl;
++it;
}
}
但是这里it->实际调用方式是：it . operator->()，这个函数返回了date*这个类型的地址，但是仅有一个地址是不可以的，我们是不是还需要一个->才能访问数据呢？所以一共需要两个->
理论上来讲是这样的，但是这里编译器做了优化，所以这里只需要一个箭头就可以访问了。
