一：框架
①：由stl的源码可知，list内部 其实就是带哨兵位循环双向链表
②：用三个类实现，分别是：节点类，迭代器类，链表类
本文实现的是三个类在同一个域中
解释：
Q：为什么list的迭代器是一个类，而string和vector中的迭代器是指针？
A：string和vector中的迭代器是指针是因为，在string和vector中，它们的物理地址都是连续的，因此可以直接使用指针来表示迭代器，此时的指针++ 和 *解引用等，均可以得到想要的结果；
但在list中，其物理地址并不连续，单纯的指针++和*解引用等，达不到我们想要的结果，所以我们吧这个指针封装成一个类，在类中重载++和*解引用等操作符，让其达到我们想要的效果
二：三个类的成员变量
①：节点类
//节点类
template<class T>
struct ListNode
{
ListNode<T>* _next;//指向下一个节点的指针
ListNode<T>* _prev;//指向上一个节点的指针
T _data;//该节点的数据
};解释：节点类的成员变量应该有
节点的值_data
一个_prev指针指向前一个节点
一个_next指针指向后一个节点
②：迭代器类
//迭代器类
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef ListNode<T> Node;//节点类的typedef
Node* _node;//唯一的一个成员变量(对内置类型封装成自定义类型)
};解释：迭代器类既然是对一个结构体指针的封装，那么成员变量就只有一个结构体指针
③：链表类
//链表类
template<class T>
class list
{
typedef ListNode<T> Node;//节点类的typedef
private:
Node* _head;//list类的唯一一个成员变量 头结点
};解释： 链表类中成员变量为一个头结点，因为双向循环带头链表，初始状态就是一个头结点
Q：为什么前两个类是struct，最后一个是class？
A：
1. ListNode 和 __list_iterator 的设计考虑
ListNode：这是一个简单的节点类，通常用于表示链表中的一个节点。它的成员变量（_next、_prev、_data）通常需要被外部直接访问，尤其是在链表中节点的连接和删除操作中。因此，使用struct可以让这些成员变量默认是public的，方便外部直接访问和操作。
__list_iterator：这是一个迭代器类，通常用于遍历链表。它的成员变量（_node）也需要被外部直接访问，尤其是在迭代器的操作中，需要对迭代器类的对象进行++ -- * 等操作。使用struct可以让这些成员变量默认是public的，方便外部直接访问和操作。
2. list 的设计考虑
list：这是一个链表类。它的成员变量（_head）头结点不应该被外部直接访问，而是通过类的成员函数来操作各个节点的状态。因此，使用class可以让成员变量（_head）默认是private的，确保封装性，防止外部直接修改链表的内部状态。
三：三个类的成员函数、
①：节点类
//节点类
template<class T>
struct ListNode
{
ListNode<T>* _next;//指向下一个节点的指针
ListNode<T>* _prev;//指向上一个节点的指针
T _data;//该节点的数据
ListNode(const T& x = T())//构造函数
:_next(nullptr)//置空
, _prev(nullptr)//置空
, _data(x)//x赋值
{}
};解释：
a：节点类只需要一个成员函数，那就是构造函数，因为该类的作用在于在list类需要插入节点的时候，会new一个节点类的对象，所以我们只需要对new出来的对象进行初始化就行
b：_data接收的是传过来的值，插入可肯定要先有值，其余两个指针先置空，连接指向的操作在list链表类的push_back函数中
c：成员函数被使用的场景：
Node* newnode = new Node(x);//用x创建一个新节点
②：迭代器类
//迭代器类
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef ListNode<T> Node;//节点类的typedef
typedef __list_iterator<T, Ref, Ptr> self;//返回值的typedef
Node* _node;//唯一的一个成员变量(对内置类型封装成自定义类型)
__list_iterator(Node* x)//构造函数 接收一个节点指针 赋值给成员变量
:_node(x)
{}
// ++it
self& operator++()
{
_node = _node->_next;
return *this;
}
// it++
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;//返回的是tmp 但是*this本身已经++
}
//--it
self& operator--()
{
_node = _node->_prev;
return *this;
}
//it--
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
//*it
Ref operator*()
{
return _node->_data;
}
//list类中的元素是一个自定义对象
Ptr operator->()
{
return &_node->_data;//返回的是该自定义对象的地址
}
bool operator!=(const self& s)
{
return _node != s._node;//地址对比
}
bool operator==(const self& s)
{
return _node == s._node;//地址对比
}
};解释：
a：构造函数：
__list_iterator(Node* x)//构造函数 接收一个节点指针 赋值给成员变量
:_node(x)
{}其实本质就是把Node*这种类型的指针赋值给了成员变量，间接的把一个Node*指针封装成了一个类，x就是无法满足迭代器要求的Node*指针
b：三参数模版的意义先暂时不管
c：其余函数就是重载操作符，让其++ -- *等之后，能的到我们想要的效果
d：self 即我们调用函数之后都要返回一个当前的迭代器，过长所以typedef
e：重载->的意义：如果list的元素是一个结构体，也就是一个类，此时我们又要取它的每一个成员变量，需要用到->
比如是一个日期类，假设我们没有实现其流插入，我们自己访问
struct Date {
int _year;
int _month;
int _day;
Date(int year = 1, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
};
void test_list3() {
list<Date> L;
L.push_back(Date(2022, 5, 1));
L.push_back(Date(2022, 5, 2));
L.push_back(Date(2022, 5, 3));
list<Date>::iterator it = L.begin();
while (it != L.end()) {
// cout << *it << " "; 假设我们没有实现流插入，我们自己访问
cout << (*it)._year << "/" << (*it)._month << "/" << (*it)._day << endl;
it++;
}
cout << endl;
}
我们发现，在我们没有实现日期类的流提取运算符的前提下，想去迭代链表 L，
我们就需要 *(it)._xxx 去访问，而大多数主流习惯应该是用 -> 去访问的：
（诚然，用 *. 去访问完全没有问题）
所以我们这里可以去实现一下箭头操作符 ->
总结：所有类型重载 operator-> 时都会省略一个箭头。
③：链表类
//链表类
template<class T>
class list
{
typedef ListNode<T> Node;//节点类的typedef
public:
typedef __list_iterator<T, T&, T*> iterator;//将迭代器类typedef为统一的名字
typedef __list_iterator<T, const T&, const T*> const_iterator;//将迭代器类typedef为统一的名字
//二者的不同在于list这个类的对象是否为const
iterator begin()
{
return _head->_next;//单参构造函数的隐式转换
}
iterator end()
{
return _head;//单参构造函数的隐式转换
}
const_iterator begin() const
{
return _head->_next;//单参构造函数的隐式转换
}
const_iterator end() const
{
return _head;//单参构造函数的隐式转换
}
void empty_init()//初始化函数
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
//创建一个头结点，自己指向自己
}
list()//构造函数复用初始化函数
{
empty_init();
}
void clear()//清理函数 清理除了头结点以外的所有节点
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
~list()//复用清理函数 最后再对头结点进行释放置空
{
clear();
delete _head;
_head = nullptr;
}
list(const list<T>& lt)//拷贝构造函数 被拷贝的对象不应该被修改所以用const
{
empty_init();//先对*this进行初始化（给一个头结点）
for (const auto& e : lt)//从it（被拷贝的对象）中范围for边读取边push到*this中
{
push_back(e);
}
}
void swap(list<T>& tmp)//交换函数 交换头结点即可
{
std::swap(_head, tmp._head);
}
//赋值函数
list<T>& operator=(list<T> lt)//参数用传值 触发拷贝构造生成it
{
swap(lt);//再把it和*this交换
return *this;
}
//尾插
void push_back(const T& x)
{
insert(end(), x);
}
//头插
void push_front(const T& x)
{
insert(begin(), x);
}
//尾删
void pop_back()
{
erase(--end());
}
//头删
void pop_front()
{
erase(begin());
}
// vector insert会导致迭代器失效
// list会不会？不会 因为无扩容
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;//保存pos位置的节点
Node* prev = cur->_prev;//保存pos位置的前一个节点
Node* newnode = new Node(x);//用x创建一个新节点
// prev newnode cur 缝合三者
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return newnode;//单参构造的隐式转换 这样也符合统一标准
}
//清理函数 只保留头结点
iterator erase(iterator pos)
{
assert(pos != end());//end()为头结点 不能erase
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;//缝合
delete cur;//释放
return next;//返回pos位置的下一个节点
}
private:
Node* _head;//list类的唯一一个成员变量 头结点
};
}解释：
a：typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
是否const的对象，调用的迭代器不同，所以我们这里对两种迭代器进行了正确的明确，因为我们迭代器的名字就是iterator 和 const_iterator
b：begin函数和end函数 分别写两种，因为要被正常对象和const对象分别调用
c：构造函数，链表的构造就是给一个头结点，然后该节点的_prev和_next都指向自己
d：赋值函数是一种现代写法，如list1 = list2 ，此时参数用传值，触发拷贝构造生成list2的拷贝之后的lt，然后交换二者即可
四：三个类的模版的串联
用一个例子来讲解，当我们进行以下操作的时候，各个类之间的模版是怎么相互影响的？
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
//*it += 10;
cout << *it << " ";
++it;
}解释：
1. list<int> lt 的实例化
当我们定义 list<int> lt 时：
list<int> 的模板参数 T 被替换为 int。
此时，list<int> 内部的类型定义会被展开为：
typedef ListNode<int> Node; // 节点类
typedef __list_iterator<int, int&, int*> iterator; // 普通迭代器
typedef __list_iterator<int, const int&, const int*> const_iterator; // const迭代器2. lt.push_back(1) 的调用
push_back 是 list 的成员函数，用于在链表尾部插入一个元素。当我们调用 lt.push_back(1) 时：
push_back 的参数类型是 T，即 int。
push_back 内部会创建一个 ListNode<int> 节点，并将 1 存储到节点的 _data 成员中。
新节点会被链接到链表的尾部。
3. list<int>::iterator it = lt.begin() 的调用
begin() 是 list 的成员函数，用于返回指向链表第一个元素的迭代器。当我们调用 lt.begin() 时：
begin() 的返回类型是 iterator，即 __list_iterator<int, int&, int*>。
iterator 是一个迭代器类，它的模板参数展开为：
struct __list_iterator<int, int&, int*> {
typedef ListNode<int> Node; // 节点类的typedef
Node* _node; // 指向 ListNode<int> 的指针
};begin() 返回的迭代器会指向链表的第一个节点（即 _head->_next）。
4. *it 的解引用操作
*it 是迭代器的解引用操作，用于获取当前节点的数据。当我们调用 *it 时：
*it 的实现会调用 __list_iterator<int, int&, int*> 的 operator* 函数。
operator* 的实现通常是：
Ref operator*() const {
return _node->_data; // 返回当前节点的数据
} 在这里，Ref 是 int&，因此 *it 返回的是 int&，即当前节点的 _data 的引用。
5. ++it 的迭代操作
++it 是迭代器的自增操作，用于将迭代器移动到下一个节点。当我们调用 ++it 时：
++it 的实现会调用 __list_iterator<int, int&, int*> 的 operator++ 函数。
operator++ 的实现通常是：
iterator& operator++() {
_node = _node->_next; // 移动到下一个节点
return *this;
}6. it != lt.end() 的比较操作
it != lt.end() 是迭代器的比较操作，用于判断迭代器是否到达链表末尾。当我们调用 it != lt.end() 时：
end() 的返回类型是 iterator，即 __list_iterator<int, int&, int*>。
end() 返回的迭代器会指向链表的哨兵节点（即 _head）。
!= 的实现会调用 __list_iterator<int, int&, int*> 的 operator!= 函数。
operator!= 的实现通常是：
bool operator!=(const iterator& other) const {
return _node != other._node; // 比较两个迭代器是否指向同一个节点
}7. 模板参数的互相影响总结
在整个过程中，模板参数的互相影响如下：
a：list<int>：
模板参数 T 被替换为 int。
内部类型 Node 被展开为 ListNode<int>。
内部类型 iterator 被展开为 __list_iterator<int, int&, int*>。
b：ListNode<int>：
存储 int 类型的数据。
提供指向前后节点的指针（_next 和 _prev）。
c：__list_iterator<int, int&, int*>：
模板参数 T 被替换为 int。
模板参数 Ref 被替换为 int&，表示解引用操作返回 int&。
模板参数 Ptr 被替换为 int*，表示指针操作返回 int*。
d：push_back：
参数类型是 int。
内部创建 ListNode<int> 节点并链接到链表尾部。
e：begin() 和 end()：
返回类型是 iterator，即 __list_iterator<int, int&, int*>。
begin() 返回指向第一个节点的迭代器。
end() 返回指向哨兵节点的迭代器。
f：*it 和 ++it：
*it 返回当前节点的 _data（int&）。
++it 将迭代器移动到下一个节点。
五：源码
#include<assert.h>
namespace bit
{
//节点类
template<class T>
struct ListNode
{
ListNode<T>* _next;//指向下一个节点的指针
ListNode<T>* _prev;//指向上一个节点的指针
T _data;//该节点的数据
ListNode(const T& x = T())//构造函数
:_next(nullptr)//置空
, _prev(nullptr)//置空
, _data(x)//x赋值
{}
};
//迭代器类
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef ListNode<T> Node;//节点类的typedef
typedef __list_iterator<T, Ref, Ptr> self;//返回值的typedef
Node* _node;//唯一的一个成员变量(对内置类型封装成自定义类型)
__list_iterator(Node* x)//构造函数 接收一个节点指针 赋值给成员变量
:_node(x)
{}
// ++it
self& operator++()
{
_node = _node->_next;
return *this;
}
// it++
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;//返回的是tmp 但是*this本身已经++
}
//--it
self& operator--()
{
_node = _node->_prev;
return *this;
}
//it--
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
//*it
Ref operator*()
{
return _node->_data;
}
//list类中的元素是一个自定义对象
Ptr operator->()
{
return &_node->_data;//返回的是该自定义对象的地址
}
bool operator!=(const self& s)
{
return _node != s._node;//地址对比
}
bool operator==(const self& s)
{
return _node == s._node;//地址对比
}
};
//链表类
template<class T>
class list
{
typedef ListNode<T> Node;//节点类的typedef
public:
typedef __list_iterator<T, T&, T*> iterator;//将迭代器类typedef为统一的名字
typedef __list_iterator<T, const T&, const T*> const_iterator;//将迭代器类typedef为统一的名字
//二者的不同在于list这个类的对象是否为const
iterator begin()
{
return _head->_next;//单参构造函数的隐式转换
}
iterator end()
{
return _head;//单参构造函数的隐式转换
}
const_iterator begin() const
{
return _head->_next;//单参构造函数的隐式转换
}
const_iterator end() const
{
return _head;//单参构造函数的隐式转换
}
void empty_init()//初始化一个链表
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
//创建一个头结点，自己指向自己
}
list()//构造函数复用初始化函数
{
empty_init();
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
list(const list<T>& lt)//拷贝构造 被拷贝的对象不应该被修改
{
empty_init();//先对*this进行初始化
for (const auto& e : lt)//从it中范围for边读取边push到*this中
{
push_back(e);
}
}
void swap(list<T>& tmp)//交换函数 交换头结点即可
{
std::swap(_head, tmp._head);
}
//赋值函数
list<T>& operator=(list<T> lt)//参数用传值 触发拷贝构造生成it
{
swap(lt);//再把it和*this交换
return *this;
}
//尾插
void push_back(const T& x)
{
insert(end(), x);
}
//头插
void push_front(const T& x)
{
insert(begin(), x);
}
//尾删
void pop_back()
{
erase(--end());
}
//头删
void pop_front()
{
erase(begin());
}
// vector insert会导致迭代器失效
// list会不会？不会 因为无扩容
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;//保存pos位置的节点
Node* prev = cur->_prev;//保存pos位置的前一个节点
Node* newnode = new Node(x);//用x创建一个新节点
// prev newnode cur 缝合三者
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return newnode;//单参构造的隐式转换 这样也符合统一标准
}
//清理函数 只保留头结点
iterator erase(iterator pos)
{
assert(pos != end());//end()为头结点 不能erase
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;//缝合
delete cur;//释放
return next;//返回pos位置的下一个节点
}
private:
Node* _head;//list类的唯一一个成员变量 头结点
};
}