目录
????????如下是list的示意图，我们将根据这幅图来模拟实现list类。(本文代码均在win10系统的vs2019中验证)
1.list类模拟实现的分析
? (1)模块分析
????????根据list类的图可以分析一下模拟实现list类都要准备什么。
? ? ? ? 存储元素需要结点--->结点类
? ? ? ? 使用迭代器访问结点--->迭代器类
? ? ? ? 总体--->list类
? (2)作用分析
????????来说说这三部分各自的作用：
? ? [1]结点类
????????存储list类的元素，因为list里面要存储各种类型的元素，所以结点类需要定义成模版。结点类中的成员变量则是有三个，分别是：指向前一个结点的prev指针，指向后一个结点的next指针，存储结点元素的value变量。
? ? [2]迭代器类
????????在模拟实现vector类时，我们是直接用结点指针作为迭代器来使用的，并没有自己实现迭代器类。list中为什么需要单独实现迭代器类？
????????原因：如上图所示。vector类是数组，它的空间是连续的，所以结点指针完全可以通过自增的方式来指向下一个结点。可是list是链表，它的空间并不连续，自然不可能直接通过结点指针的自增来指向下一个链表结点，所以我们才需要自己实现迭代器类，并且重载自增与自减运算符，这样就可以通过迭代器的自增或自减来指向前后结点了。
? ? [3]list类
????????这自然不用多说，我们只需要实现它最常用的一些函数即可，这里的重点是重载->，后面会用代码示例来帮助理解。
2.结点类模拟实现
????????根据list的示意图：结点类中应包括三个成员变量：指向前一个结点的prev指针，指向下一个结点的next指针，保存元素的value。因为list可以存储各种元素，所以结点类是模版类。
template<typename T>
struct ListNode {
ListNode<T>* prev;//指向前一个结点
ListNode<T>* next;//指向后一个结点
T value;//该结点的值域，里面可能保存内置类型的元素
//也可能保存自定义类型的对象，如日期类对象
ListNode(const T& _value = T())
:prev(nullptr)
,next(nullptr)
,value(_value)
{}
};3.迭代器类模拟实现
? (1)迭代器分析
????????list类中的迭代器有正向迭代器和反向迭代器之分，所以迭代器类也要定义两个。因为结点类是模板，在结点中会保存多种类型的元素，所以每种类型的结点相应的迭代器也是不同的，因此迭代器类也是模板。
????????迭代器类中我们需要重载多种运算符，比如：*，->，++，--，!=，==。
????????重载它们的原因：
? 重载*：可以直接通过解引用迭代器来得到结点中value变量保存的值。
? 重载->：通过->来得到节点中value变量保存的值的地址。(这个后面要详细说)
? 重载++：通过迭代器的自增来指向下一个结点。
? 重载--：通过迭代器的自减来指向前一个结点。
? 重载!=和==：直接比较两个迭代器是否指向同一个结点。
? (2)正向迭代器模拟实现
? ? [1]成员变量和模板参数
? ? ? ?我们为迭代器类设置了三个模板参数，原因会在后面的逐步实现中体会到。
? ? ? ? 因为结点类和迭代器类自身的类型名太长，写起来太麻烦，所以我们用typedef关键字给这两个类型取了别名。
? ? ? ? 我们为结点类的类型取的别名是Node，为迭代器类取的别名是Self。
? ? ? ? 迭代器类中的成员变量只有一个，那就是结点类类型的指针pNode，因为迭代器的本质就是指针。
template<typename T, typename Ref, typename Ptr>
struct ListIterator {
typedef ListNode<T> Node;//为结点类取别名
typedef ListIterator<T, Ref, Ptr> Self;//为正向迭代器类取别名
//成员变量
Node* pNode;//指向结点的指针
}? ? [2]构造函数
? ? ? ? 迭代器类的构造函数，如果显示给出参数，那么就用给出的指针变量来给pNode指针变量赋值；如果没有显示给出，就让pNode指针指向空。
//正向迭代器构造函数
ListIterator(Node* _pNode = nullptr)
:pNode(_pNode)
{}
? ? [3]重载*
? ? ? ? 返回迭代器指向的结点的value变量，这样就可以很方便的访问结点的值域。
? ? ? ? 注意这里的返回值是Ref，是不是模板参数在这里派上用场。
//重载*
//返回迭代器指向的结点的值域
Ref operator*() {
return pNode->value;
}
? ? [4]重载->
? ? ? ? 返回迭代器指向的结点的value变量的地址，这里先知道需要这么定义，原因在后面。
? ? ? ? 这里的返回值是Ptr，可以看出来，此时的Ptr其实是指针类型，是指向结点的value变量的指针类型。
//重载->
//返回迭代器指向的结点值域的地址
Ptr operator->() {
return &(operator*());
}
? ? [5]重载++
? ? ? ? 自增运算符的重载是迭代器类的核心。前置++重载中，要让当前迭代器指向下一个结点后，再把迭代器返回。后置++中是把当前迭代器用临时变量保存一份，再把迭代器指向下一个结点，然后返回临时变量。注意：重载后置++或后置--时，必须在函数参数列表加一个int变量，这是语法规定。
????????重载前置++和后置++时的返回值有所不同，前置++返回值类型是迭代器类型的引用，而后置++返回值类型是迭代器类型。
????????因为前置++中，返回的是对this的解引用，this并不是局部变量，函数结束后依然存在，所以可以返回它的引用，减少值拷贝次数。
????????后置++中，返回的temp是函数中创建的局部对象，在函数结束后会被销毁，所以返回值类型不可以是引用。这里就必须通过值拷贝来返回值。
//重载前置++
//返回迭代器对象自身的引用
//因为对象自身并不是该函数中的局部对象
Self& operator++() {
pNode = pNode->next;
return *this;
}
//重载后置++
//此时需要返回temp对象，而不是引用
//因为temp对象是局部的对象
//函数结束后就被释放
Self operator++(int a) {
Self temp(*this);
pNode = pNode->next;
return temp;
}
? ? [6]重载--
????????前置--和后置--关于函数的返回类型跟重载++类似，这里就不再赘述。
//重载前置--
Self& operator--() {
pNode = pNode->prev;
return *this;
}
//重载后置--
Self operator--(int a) {
Self temp(*this);
pNode = pNode->prev;
return temp;
}
? ? [7]重载!=和==
????????这里只需要比较pNode是否相同即可，因为pNode本身就是指向结点的指针，保存着结点的地址，只要地址相同，那自然就是同一个结点了。
//重载!=
bool operator!=(const Self& s)const {
return pNode != s.pNode;
}
//重载==
bool operator==(const Self& s)const {
return pNode == s.pNode;
}
? (3)反向迭代器模拟实现
????????反向迭代器除了命名和自增自减运算符的重载与正向迭代器有差别外，其余都相同。所以反向迭代器就不详细的解释了。
? ? [1]成员变量和模板参数
template<typename T, typename Ref, typename Ptr>
struct RListIterator {
typedef ListNode<T> Node;
typedef RListIterator<T, Ref, Ptr> Self;
Node* pNode;
}? ? [2]构造函数
//反向迭代器构造函数
RListIterator(Node* _pNode = nullptr)
:pNode(_pNode)
{}
? ? [3]重载*
//重载*
Ref operator*() {
return pNode->value;
}
? ? [4]重载->
//重载->
Ptr operator->() {
return &(operator*());
}
? ? [5]重载++
????????注意，反向迭代器的自增方向跟正向迭代器的自增是相反的，反向迭代器自增其实就是让迭代器指向当前结点的prev指针所指向的结点。其它的注意事项跟正向迭代器是相同的。
//重载前置++
//反向迭代器的自增其实是反方向的自增
//所以迭代器其实是向该节点的prev指针域滚动
Self& operator++() {
pNode = pNode->prev;
return *this;
}
//重载后置++
Self operator++(int a) {
Self temp(*this);
pNode = pNode->prev;
return temp;
}
? ? [6]重载--
????????反向迭代器的自减和正向迭代器的自减是相反的，反向迭代器的自减是让迭代器指向当前结点的next指针所指向的结点。其他注意事项和正向迭代器是相同的。
//重载前置--
//反向迭代器的自减
//其实就是正向迭代器的自增
Self& operator--() {
pNode = pNode->next;
return *this;
}
//重载后置--
Self operator--(int a) {
Self temp(*this);
pNode = pNode->next;
return temp;
}
? ? [7]重载!=和==
//重载!=
bool operator!=(const Self& s)const {
return pNode != s.pNode;
}
//重载==
bool operator==(const Self& s)const {
return pNode == s.pNode;
}
? (4)重载->的原因(重要！！!)
????????这里来讲解一下迭代器类中重载->的问题。
????????如果结点中的value变量存储的元素是内置类型，如：int。这个 -> 是不是显得很鸡肋啊。因为这个箭头返回的是value变量的地址，也就返回的是int变量的地址，感觉没啥用啊。我们一般来说都是只需要int变量的值，貌似没有啥时候还需要它的地址。
????????但是，当结点中的value变量存储的元素类型是内置类型呢？比如之前就实现过的：日期类。
? ? ? ? 日期类代码如下：这里的日期类很简略，主要是讲解->的重载。
struct Date {
int year;
int month;
Date() {}
Date(int _year,int _month)
:year(_year)
, month(_month)
{}
Date(const Date& d1)
:year(d1.year)
, month(d1.month)
{}
};????????日期类访问它的元素是怎么访问？
? ? ? ? 可以用类名.成员变量名的方式，也可以用指针->成员变量名的方式。
Date d1(2021, 1);
cout << d1.year << endl;
Date* pd1 = &d1;
cout << pd1->year << endl;
? ? ? ? 如果list中存储的元素类型是上面的日期类，那么结点中的value变量保存的就是一个个的日期类对象。如果迭代器使用重载后的->，就会返回日期类对象的地址，也就是Date类型的指针。
? ? ? ? 那么我们是不是就可以用返回的这个指针来访问日期类对象中的成员变量？
? ? ? ? 看到这里是不是已经清楚了重载->的意义，但是它的使用上还有一点要注意。
? ? ? ? 假设List中存储日期类对象，it是迭代器，想要通过p访问日期类的year变量，按道理是不是要这样：第一个->调用迭代器重载后的->，得到日期类对象的地址(指针)，第二个->则是用日期类的指针去访问year变量。
const Date d1(2012, 12);
const Date d2(2013, 13);
List<Date> L1;
L1.Push_back(d1);
L1.Push_back(d2);
ListIterator<Date, Date&, Date*> it = L1.Begin();
cout << it->->year << endl;
? ? ? ? 但是编译器会优化，所以我们应该使用下面这种方式去访问：
const Date d1(2012, 12);
const Date d2(2013, 1);
List<Date> L1;
L1.Push_back(d1);
L1.Push_back(d2);
ListIterator<Date, Date&, Date*> it = L1.Begin();
//简单写法 auto it = L1.Begin();
cout << it->year << endl;
? (5)迭代器总体代码
//正向迭代器类
template<typename T, typename Ref, typename Ptr>
struct ListIterator {
typedef ListNode<T> Node;//为结点类取别名
typedef ListIterator<T, Ref, Ptr> Self;//为正向迭代器类取别名
Node* pNode;//指向结点的指针
//正向迭代器构造函数
ListIterator(Node* _pNode = nullptr)
:pNode(_pNode)
{}
//重载*
//返回迭代器指向的结点的值域
Ref operator*() {
return pNode->value;
}
//重载->
//返回迭代器指向的结点值域的地址
Ptr operator->() {
return &(operator*());
}
//重载前置++
//返回迭代器对象自身的引用
//因为对象自身并不是该函数中的局部对象
Self& operator++() {
pNode = pNode->next;
return *this;
}
//重载后置++
//此时需要返回temp对象，而不是引用
//因为temp对象是局部的对象
//函数结束后就被释放
Self operator++(int a) {
Self temp(*this);
pNode = pNode->next;
return temp;
}
//重载前置--
Self& operator--() {
pNode = pNode->prev;
return *this;
}
//重载后置--
Self operator--(int a) {
Self temp(*this);
pNode = pNode->prev;
return temp;
}
//重载!=
bool operator!=(const Self& s)const {
return pNode != s.pNode;
}
//重载==
bool operator==(const Self& s)const {
return pNode == s.pNode;
}
};
//反向迭代器类
template<typename T, typename Ref, typename Ptr>
struct RListIterator {
typedef ListNode<T> Node;
typedef RListIterator<T, Ref, Ptr> Self;
Node* pNode;
//反向迭代器构造函数
RListIterator(Node* _pNode = nullptr)
:pNode(_pNode)
{}
//重载*
Ref operator*() {
return pNode->value;
}
//重载->
Ptr operator->() {
return &(operator*());
}
//重载前置++
//反向迭代器的自增其实是反方向的自增
//所以迭代器其实是向该节点的prev指针域滚动
Self& operator++() {
pNode = pNode->prev;
return *this;
}
//重载后置++
Self operator++(int a) {
Self temp(*this);
pNode = pNode->prev;
return temp;
}
//重载前置--
//反向迭代器的自减
//其实就是正向迭代器的自增
Self& operator--() {
pNode = pNode->next;
return *this;
}
//重载后置--
Self operator--(int a) {
Self temp(*this);
pNode = pNode->next;
return temp;
}
//重载!=
bool operator!=(const Self& s)const {
return pNode != s.pNode;
}
//重载==
bool operator==(const Self& s)const {
return pNode == s.pNode;
}
};4.list类模拟实现
? (1)成员变量和模板参数
? ? ? ? 因为list可以存储各种类型的元素，因此list类要设置为模板，T就是存储的元素的类型。
? ? ? ? 因为结点类和迭代器类的类名太长，所以用typedef关键为它们取了别名。这里迭代器的三个参数之所以设置为<T , T& , T*>，是因为list类只给出了一个模板参数，而迭代器类应该有三个，因此用T&和T*作为另外两个参数。
? ? ? ? 在这里还需要定义创建头结点的函数，并且让头结点的两个指针都指向自己，因为此时list对象中并没有元素。
//带头结点的双向链表
template<typename T>
class List {
typedef ListNode<T> Node;
typedef ListIterator<T, T&, T*> Iterator;//正向迭代器
typedef RListIterator<T, T&, T*> RIterator;//反向迭代器
private:
Node* Head;//指向头结点的指针
//为list对象创建头结点的函数
void CreateHead() {
Head = new Node();
Head->next = Head;
Head->prev = Head;
}
}? (2)构造模块
? ? ? ? 下表是该模块需要实现的函数。
| 函数名称 | 功能说明 |
| List() | 无参构造 |
| List(int n, const T& _value = T()) | 用n个_value构造List对象 |
| List(iterator first, iterator last) | 区间构造 |
| List(List<T>& L) | 拷贝构造 |
| operator=(const List<T> L) | 赋值运算符重载 |
| ~List() | 析构函数 |
? ? [1]无参构造
? ? ? ? 调用CreateHead函数来创建一个头结点。
//无参构造
List() {
CreateHead();
}
? ? [2]n个相同元素构造
? ? ? ? 创建头结点后，将n个元素逐个尾插，尾插函数后面会实现的。
//n个相同元素构造
List(int n, const T& _value = T()) {
CreateHead();
for (int i = 0; i < n; i++) {
Push_back(_value);
}
}
? ? [3]区间构造
????????由于list可以存储各种类型的元素，所以区间构造时自然也会用到各种类型的迭代器，因此区间构造也应该定义为模版，需要给出模版参数列表。具体实现和上一个函数是差不多的。
//区间构造
//这里需要用到函数模板
//因为list可以存储各种类型的元素
template <typename iterator>
List(iterator first, iterator last) {
CreateHead();
while (first != last) {
Push_back(*first);
first++;
}
}
? ? [4]拷贝构造
? ? ? ? 拷贝构造需要复用尾插函数，同时也会用到迭代器。
//拷贝构造
List(List<T>& L) {
CreateHead();
auto it = L.Begin();
while (it != L.Head) {
Push_back(*it);
it++;
}
}
? ? [5]赋值运算符重载
? ? ? ? 将赋值运算符重载的参数定义为list类型的对象而不是对象的引用，传参时会发生值拷贝。
????????因此我们可以把list对象的this指针和拷贝出来的参数L指向头结点的指针交换，这样this指针就直接指向了拷贝出来的L的头结点。L则指向了list对象的头结点，在函数结束后，作为局部对象的L将被销毁，它指向的空间也会被释放。
//赋值运算符重载
//此处的参数是值传递
//所以只需要this指针和参数对象的指针交换指向的空间即可
//当函数结束后，参数对象也会被销毁
List<T>& operator=(const List<T> L) {
std::swap(this->Head, L.Head);
return *this;
}
? ? [6]析构函数
? ? ? ? 直接复用Clear函数清空有效结点，然后释放头结点即可。
//析构函数
~List() {
Clear();
delete Head;
Head = nullptr;
}
? (3)迭代器模块
????????下表是该模块需要实现的函数。
| 函数名称 | 功能说明 |
| Iterator Begin() | 正向迭代器，返回正方向第一个有效元素的迭代器 |
| Iterator End() | 正向迭代器，返回正方向最后一个有效元素的下一个元素的迭代器(也就是返回头结点的迭代器) |
| Iterator Rbegin() | 反向迭代器，返回反方向第一个有效元素的迭代器 |
| Iterator Rend() | 反向迭代器，返回反方向最后一个有效元素的下一个元素的迭代器(也就是返回头结点的迭代器) |
? ? [1]正向迭代器
? ? ? ? Begin迭代器指向的是正方向第一个有效结点，也就是头结点的下一个结点。
? ? ? ? End迭代器指向的是正方向最后一个有效结点的下一个结点，也就是头结点。
//正向迭代器
Iterator Begin() const {
return Iterator(Head->next);
}
Iterator End() const {
return Iterator(Head);
}
? ? [2]反向迭代器
? ? ? ? Rbegin迭代器指向的是反方向第一个有效结点，也就是头结点的前一个结点。
? ? ? ? Rend迭代器指向的是反方向最后一个有效结点的下一个结点，也就是头结点。
//反向迭代器
RIterator Rbegin() const {
return RIterator(Head->prev);
}
RIterator Rend() const {
return RIterator(Head);
}
? (4)容量模块
? ? ? ? 下表是该模块需要实现的函数。
| 函数名称 | 功能说明 |
| size_t Size() | 返回List对象中有效元素个数 |
| bool Empty() | 判空，当List对象不是空返回true |
| void Resize(size_t newSize, const T& _value = T()) | 设置List对象有效元素个数。当newSize大于旧的元素个数，用_value填充多余位置；当newSize小于旧的元素个数，直接将多余元素尾删 |
? ? [1]容量函数
? ? ? ? 通过循环来计算有效结点的个数。
//容量函数
size_t Size()const {
size_t count = 0;
auto it = Begin();
while (it != End()) {
count++;
it++;
}
return count;
}
? ? [2]判空函数
? ? ? ? 当头结点的下一个结点仍旧是头结点时，自然是空的。
//判空函数
//因为头结点申请时
//next指针域指向头结点
//此时list是空的
bool Empty()const {
return Head->next == Head;
}
? ? [3]设置有效元素个数
? ? ? ? 在此函数中，需要考虑newSize和oldSize的大小关系，根据不同的大小关系来进行不同的操作。
????????newSize <= oldSize ：缩减有效元素个数，通过循环进行尾删即可。
????????newSize >?oldSize ：增加有效元素个数，并用_value给增加的结点的value变量赋值。
//设置有效元素个数
void Resize(size_t newSize, const T& _value = T()) {
size_t oldSize = Size();
//新的元素个数小于旧的元素个数
//即：缩减list的有效元素个数
//将多余的元素尾删
if (newSize <= oldSize) {
for (int i = 0; i < oldSize - newSize; i++)
Pop_back();
}
//新的元素个数大于旧元素个数
//将多余空间尾插value元素
else {
for (size_t i = oldSize; i < newSize; i++) {
Push_back(_value);
}
}
}
? (5)增删改查模块
? ? ? ? 下列表格是该模块需要模拟实现的函数。
| 函数名称 | 功能说明 |
| Iterator Insert(Iterator it, const T& value) | 在it迭代器的位置插入value，并返回新插入结点的迭代器 |
| Iterator Erase(Iterator it) | 删除it迭代器指向的结点，并返回该结点下一个结点的迭代器 |
| void Push_back(const T& value) | 尾插value元素 |
| void Pop_back() | 尾删 |
| void Push_front(const T& value) | 头插value元素 |
| void Pop_front() | 头删 |
| void Clear() | 清空list对象的元素 |
| Front() | 返回第一个有效元素的引用 |
| Back() | 返回最后一个有效元素的引用 |
? ? [1]任意位置插入
????????根据下图来理解插入函数的代码。
????????这个函数的作用是：在it迭代器指向的结点的前面插入一个新结点，新结点中保存的元素是参数value。
????????插入新结点时，需要创建pPos结点保存迭代器指向的结点，为将要插入的元素创建pNewNode结点。插入时需要先让新结点的两个指针指向该指向的两个结点，然后才可以让那两个结点指向新结点。
? ? ? ? 最后则是返回新结点的迭代器。
//任意位置的插入
//将value元素插在it迭代器对象的位置
//此处的 Iterator 是迭代器类
//it 是迭代器对象
Iterator Insert(Iterator it, const T& value) {
//用pPos指针保存迭代器对象中的结点地址
Node* pPos = it.pNode;
//用value创建一个结点对象
//用pNewNode指向该结点对象
Node* pNewNode = new Node(value);
//新结点的指针域指向它的前后两个结点
pNewNode->next = pPos;
pNewNode->prev = pPos->prev;
//新结点前后两个结点的指针域指向新结点
pPos->prev->next = pNewNode;
pPos->prev = pNewNode;
return pNewNode;
}
? ? [2]任意位置删除
????????根据下图来理解删除的步骤：
? ? ? ? 这个函数的作用是：删除it迭代器指向的结点，并返回该结点下一个结点的迭代器。
? ? ? ? 我们知道，在删除了一个结点A后，A结点的前一个结点的next指针将会指向A结点的下一个结点，A结点的下一个结点的prev指针将会指向A结点的前一个结点。
? ? ? ? 我们可以根据结点删除后的情况来逐步写出删除函数的代码。
//任意位置的删除
//返回被删除结点下一个结点的迭代器
Iterator Erase(Iterator it) {
//判断迭代器指向的位置
if (it == End())
return End();
//创建两个新结点指针指向被删除结点和被删除结点的下一个结点
Node* pPos = it.pNode;
Node* pTemp = pPos->next;
//让被删除结点的前一个结点的next指针指向被删除结点的下一个结点
pPos->prev->next = pTemp;
//让被删除结点的下一个结点的prev指针指向被删除结点的前一个结点
pTemp->prev = pPos->prev;
//最后要释放被删除结点的资源
delete pPos;
return pTemp;
}
? ? [3]尾插
? ? ? ? End迭代器指向最后一个有效元素的下一个结点。
? ? ? ? 尾插也就是在End迭代器指向的结点之前插入一个新结点，所以我们可以复用Insert函数。
//尾插
//也就是在End迭代器的位置插入value
//所以可以直接复用Insert函数
void Push_back(const T& value) {
Insert(End(), value);
}
? ? [4]尾删
? ? ? ? 尾删则是删除End迭代器指向结点的前一个结点。
? ? ? ? --End() : 这一个整体就是End迭代器指向结点的前一个结点，我们也可以复用Erase函数。
//尾删
void Pop_back() {
Erase(--End());
}
? ? [5]头插
? ? ? ? 头插就是在第一个有效结点的前面插入新结点，而Begin迭代器就指向第一个有效结点，因此可以直接复用Insert函数。
//头插
//即在Begin迭代器的位置插入value
void Push_front(const T& value) {
Insert(Begin(), value);
}
? ? [6]头删
????????头删就是删除第一个有效结点，Begin迭代器就指向第一个有效结点，因此可以复用Erase函数。
//头删
void Pop_front() {
Erase(Begin());
}
? ? [7]清空有效元素
????????这里需要注意迭代器失效的问题，关于迭代器失效在list的使用中也讲解过。
????????在利用迭代器循环删除结点时，需要在删除后给it迭代器重新赋值，让it迭代器指向被删除结点的下一个结点，避免迭代器失效。
//清空
void Clear() {
auto it = Begin();
while (it != End()) {
it = Erase(it);
}
}
? ? [8]Front函数
? ? ? ? 返回的是第一个结点的value变量中保存的元素，这里的*运算符调用的是迭代器类中被重载后的*，因此返回的是结点中的value变量，而value变量就是T类型的，所以这里的返回值类型可以定义为引用类型。
//获取首元素
T& Front() const {
return *Begin();
}
? ? [9]Back函数
? ? ? ? 返回最后一个有效元素，也就是End迭代器的前一个元素。其余原理同上。
//获取尾部元素
T& Back()const {
return *(--End());
}
5.总体代码
#include "iostream"
using namespace std;
//结点类
template<typename T>
struct ListNode {
ListNode<T>* prev;//指向前一个结点
ListNode<T>* next;//指向后一个结点
T value;//该结点的值域，里面可能保存内置类型的元素
//也可能保存自定义类型的对象，如日期类对象
ListNode(const T& _value = T())
:prev(nullptr)
,next(nullptr)
,value(_value)
{}
};
//=======================================================
// 迭代器模块
//正向迭代器类
template<typename T, typename Ref, typename Ptr>
struct ListIterator {
typedef ListNode<T> Node;//为结点类取别名
typedef ListIterator<T, Ref, Ptr> Self;//为正向迭代器类取别名
Node* pNode;//指向结点的指针
//正向迭代器构造函数
ListIterator(Node* _pNode = nullptr)
:pNode(_pNode)
{}
//重载*
//返回迭代器指向的结点的值域
Ref operator*() {
return pNode->value;
}
//重载->
//返回迭代器指向的结点值域的地址
Ptr operator->() {
return &(operator*());
}
//重载前置++
//返回迭代器对象自身的引用
//因为对象自身并不是该函数中的局部对象
Self& operator++() {
pNode = pNode->next;
return *this;
}
//重载后置++
//此时需要返回temp对象，而不是引用
//因为temp对象是局部的对象
//函数结束后就被释放
Self operator++(int a) {
Self temp(*this);
pNode = pNode->next;
return temp;
}
//重载前置--
Self& operator--() {
pNode = pNode->prev;
return *this;
}
//重载后置--
Self operator--(int a) {
Self temp(*this);
pNode = pNode->prev;
return temp;
}
//重载!=
bool operator!=(const Self& s)const {
return pNode != s.pNode;
}
//重载==
bool operator==(const Self& s)const {
return pNode == s.pNode;
}
};
//反向迭代器类
template<typename T, typename Ref, typename Ptr>
struct RListIterator {
typedef ListNode<T> Node;
typedef RListIterator<T, Ref, Ptr> Self;
Node* pNode;
//反向迭代器构造函数
RListIterator(Node* _pNode = nullptr)
:pNode(_pNode)
{}
//重载*
Ref operator*() {
return pNode->value;
}
//重载->
Ptr operator->() {
return &(operator*());
}
//重载前置++
//反向迭代器的自增其实是反方向的自增
//所以迭代器其实是向该节点的prev指针域滚动
Self& operator++() {
pNode = pNode->prev;
return *this;
}
//重载后置++
Self operator++(int a) {
Self temp(*this);
pNode = pNode->prev;
return temp;
}
//重载前置--
//反向迭代器的自减
//其实就是正向迭代器的自增
Self& operator--() {
pNode = pNode->next;
return *this;
}
//重载后置--
Self operator--(int a) {
Self temp(*this);
pNode = pNode->next;
return temp;
}
//重载!=
bool operator!=(const Self& s)const {
return pNode != s.pNode;
}
//重载==
bool operator==(const Self& s)const {
return pNode == s.pNode;
}
};
//带头结点的双向链表
template<typename T>
class List {
typedef ListNode<T> Node;
typedef ListIterator<T, T&, T*> Iterator;//正向迭代器
typedef RListIterator<T, T&, T*> RIterator;//反向迭代器
private:
Node* Head;//指向头结点的指针
//为list对象创建头结点的函数
void CreateHead() {
Head = new Node();
Head->next = Head;
Head->prev = Head;
}
public:
//============================================
//构造模块
//无参构造
List() {
CreateHead();
}
//n个相同元素构造
List(int n, const T& _value = T()) {
CreateHead();
for (int i = 0; i < n; i++) {
Push_back(_value);
}
}
//区间构造
//这里需要用到函数模板
//因为list可以存储各种类型的元素
template <typename iterator>
List(iterator first, iterator last) {
CreateHead();
while (first != last) {
Push_back(*first);
first++;
}
}
//拷贝构造
List(List<T>& L) {
CreateHead();
auto it = L.Begin();
while (it != L.Head) {
Push_back(*it);
it++;
}
}
//赋值运算符重载
//此处的参数是值传递
//所以只需要this指针和参数对象的指针交换指向的空间即可
//当函数结束后，参数对象也会被销毁
List<T>& operator=(const List<T> L) {
std::swap(this->Head, L.Head);
return *this;
}
//析构函数
~List() {
Clear();
delete Head;
Head = nullptr;
}
//===============================================
//容量模块
//容量函数
size_t Size()const {
size_t count = 0;
auto it = Begin();
while (it != End()) {
count++;
it++;
}
return count;
}
//判空函数
//因为头结点申请时
//next指针域指向头结点
//此时list是空的
bool Empty()const {
return Head->next == Head;
}
//设置有效元素个数
void Resize(size_t newSize, const T& _value = T()) {
size_t oldSize = Size();
//新的元素个数小于旧的元素个数
//即：缩减list的有效元素个数
//将多余的元素尾删
if (newSize <= oldSize) {
for (int i = 0; i < oldSize - newSize; i++)
Pop_back();
}
//新的元素个数大于旧元素个数
//将多余空间尾插value元素
else {
for (size_t i = oldSize; i < newSize; i++) {
Push_back(_value);
}
}
}
//===============================================
//迭代器模块
//正向迭代器
Iterator Begin() const {
return Iterator(Head->next);
}
Iterator End() const {
return Iterator(Head);
}
//反向迭代器
RIterator Rbegin() const {
return RIterator(Head->prev);
}
RIterator Rend() const {
return RIterator(Head);
}
//===============================================
//增删改查模块
//任意位置的插入
//将value元素插在it迭代器对象的位置
//此处的 Iterator 是迭代器类
//it 是迭代器对象
Iterator Insert(Iterator it, const T& value) {
//用pPos指针保存迭代器对象中的结点地址
Node* pPos = it.pNode;
//用value创建一个结点对象
//用pNewNode指向该结点对象
Node* pNewNode = new Node(value);
pNewNode->next = pPos;
pNewNode->prev = pPos->prev;
pPos->prev->next = pNewNode;
pPos->prev = pNewNode;
return pNewNode;
}
//任意位置的删除
//返回被删除结点下一个结点的迭代器
Iterator Erase(Iterator it) {
if (it == End())
return End();
Node* pPos = it.pNode;
Node* pTemp = pPos->next;
pPos->prev->next = pTemp;
pTemp->prev = pPos->prev;
delete pPos;
return pTemp;
}
//尾插
//也就是在End迭代器的位置插入value
//所以可以直接复用Insert函数
void Push_back(const T& value) {
Insert(End(), value);
}
//头插
//即在Begin迭代器的位置插入value
void Push_front(const T& value) {
Insert(Begin(), value);
}
//尾删
void Pop_back() {
Erase(--End());
}
//头删
void Pop_front() {
Erase(Begin());
}
//清空
void Clear() {
auto it = Begin();
while (it != End()) {
it = Erase(it);
}
}
//获取首元素
T& Front() const {
return *Begin();
}
//获取尾部元素
T& Back()const {
return *(--End());
}
};
int main() {}