目录
一、前言
STL 中的 list 是一个带头双向循环链表，作为链表的终极形态，各项操作性能都很优秀，尤其是 list 中迭代器的设计更是让人拍案叫绝，如此优秀的容器究竟是如何实现的呢？本文将会带大家一起从0~1 去模拟实现STL库中的 list 容器，以便于让大家更好的巩固之前学习过的 缺省参数、封装、类的6大默认函数等。
如果大家还有不太了解 list 容器的可以先看看两篇文章：
1️⃣：带头双向循环链表详解
2️⃣：list 容器最全解析
二、 list 容器的模拟实现思
模块分析
根据 list 容器图可以分析一下 模拟实现 list容器 都要准备什么？
- 存储元素需要结点--->结点类
- 使用迭代器访问结点--->迭代器类
- 总体--->list类
作用分析
1️⃣：节点类
作用：存储 list容器 的元素，因为list里面要存储各种类型的元素，所以结点类需要定义成模版。结点类中的成员变量则是有三个，分别是：指向前一个结点的_prev指针，指向后一个结点的_next指针，存储结点元素的_data变量。
2️⃣: 迭代器类
- 此时大家可以思考这样一个问题，在模拟实现vector类时，我们是直接用结点指针作为迭代器来使用的，并没有自己实现迭代器类。list中为什么需要单独实现迭代器类？
原因：如上图所示。vector容器是数组，它的空间是连续的，所以结点指针完全可以通过自增的方式来指向下一个结点。可是list容器是链表，它的空间并不连续，自然不可能直接通过结点指针的自增来指向下一个链表结点，所以我们才需要自己实现迭代器类，并且重载自增与自减运算符，这样就可以通过迭代器的自增或自减来指向前后结点了。
3️⃣ ：list类
作用：实现链表各项功能的类，为主要部分
三、list的节点类设计
list本身 和 list的结点 是两个不同的结构，需要分开设计。以下是list的节点结构：
/*ListNode.h*/
namespace xas_list
{
template<class T>
struct ListNode
{
ListNode<T>* _prev; //节点的前指针
ListNode<T>* _next; //节点的后指针
T _data; //节点的数据
ListNode(const T& x= T())//初始化列表进行初始化
:_prev(nullptr)
,_next(nullptr)
,_data(x)
{}
};
}首先，我们在自己的命名空间内模拟实现 list（为了防止与库冲突），上面的代码就是list节点的结构。在这里是用并没有使用 class，因为 struct 默认访问权限是 public，又因为节点是需要经常访问的，所以使用struct更好。
我们将这个类加上 template<class T> 后，就能够实现节点存储不同类型的数据，这也是C++模板的好处。
四、list 的迭代器类设计
⭐ 迭代器类--存在的意义
之前 模拟实现 string 和 vector 时都没有说要实现一个迭代器类，为什么实现list的时候就需要实现一个迭代器类了呢？
- 因为 string 和 vector 对象都将其数据存储在了一块连续的内存空间，我们通过指针进行自增、自减以及解引用等操作，就可以对相应位置的数据进行一系列操作，因此string和vector当中的迭代器就是原生指针。
- 但是对于 list 来说，其各个结点在内存当中的位置是随机的，并不是连续的，我们不能仅通过结点指针的自增、自减以及解引用等操作对相应结点的数据进行操作。
- 而迭代器的意义就是，让使用者可以不必关心容器的底层实现，可以用简单统一的方式对容器内的数据进行访问。
- 既然 list 的结点指针的行为不满足迭代器定义，那么我们可以对这个结点指针进行封装，对结点指针的各种运算符操作进行重载，使得我们可以用和string和vector当中的迭代器一样的方式使用list当中的迭代器。例如，当你使用 list 当中的迭代器进行自增操作时，实际上执行了p = p->next语句，只是你不知道而已。
总结：list迭代器类，实际上就是对结点指针进行了封装，对其各种运算符进行了重载，使得结点指针的各种行为看起来和普通指针一样。（例如，对结点指针自增就能指向下一个结点）
⭐ 迭代器类--模拟实现
模板参数 和 成员变量
- 我们为 迭代器类 设置了 三个模板参数，为什么有三个模板参数？
template<class T, class Ref, class Ptr>- 在 list 的模拟实现当中，我们 typedef 了两个迭代器类型，普通迭代器 和 const迭代器。
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
- 这里我们就可以看出，迭代器类 的模板参数列表当中的 Ref 和 Ptr 分别代表的是 引用类型（T&） 和 指针类型（T *）。
- 当我们使用 普通迭代器 时，编译器就会实例化出一个 普通迭代器 对象；当我们使用 const迭代器时，编译器就会实例化出一个 const迭代器对象。
- 若该迭代器类不设计三个模板参数，那么就不能很好的区分-- 普通迭代器 和-- const迭代器。
- 因为 结点类 和 迭代器类 自身的类型名太长，写起来太麻烦，所以我们用 typedef关键字 给这两个类型取了别名。
- 我们为 结点类 的类型取的别名是 Node，为 迭代器类 取的别名是 Self。
- 迭代器类 中的成员变量只有一个，那就是 结点类类型的指针 _node，因为 迭代器的本质就是指针。
template<typename T, typename Ref, typename Ptr>
struct _list_iterator
{
typedef ListNode<T> Node; //为结点类取别名
typedef _list_iterator<T, Ref, Ptr> self; //为正向迭代器类取别名
//成员变量
Node* _node; //指向结点的指针
}构造函数
迭代器类 实际上就是对 结点指针进行了封装，其成员变量就只有一个，那就是结点指针，其构造函数直接根据所给结点指针构造一个迭代器对象即可。
//正向迭代器构造函数
_list_iterator(Node* node = nullptr) // 默认构造函数
:_node(node)
{}++运算符的重载
自增运算符的 重载 是迭代器类的核心。前置++重载中，要让当前迭代器指向下一个结点后，再把迭代器返回。后置++中是把当前迭代器用临时变量保存一份，再把迭代器指向下一个结点，然后返回临时变量。注意：重载后置++或后置--时，必须在函数参数列表加一个int变量，这是语法规定。
- 重载前置++ 和 后置++ 时的返回值有所不同，前置++返回值类型是--------迭代器类型的引用，而后置++返回值类型是------ 迭代器类型。
- 前置++中，返回的是对 this 的解引用，this并不是局部变量，函数结束后依然存在，所以可以返回它的引用，减少值拷贝次数。
- 后置++中，返回的 temp 是函数中创建的局部对象，在函数结束后会被销毁，所以返回值类型不可以是引用。这里就必须通过值拷贝来返回值。
//重载前置++
//返回迭代器对象自身的引用
//因为对象自身并不是该函数中的局部对象
self& operator++()
{
_node = _node->_next;
return *this;
}
//重载后置++
//此时需要返回temp对象，而不是引用
//因为temp对象是局部的对象
//函数结束后就被释放
self operator++(int a)
{
self temp(*this);
_node = _node->_next;
return temp;
}-- 运算符的重载
前置--和后置--关于函数的返回类型跟重载++类似，这里就不再赘述。
//重载前置--
self& operator--()
{
_node = _node->_prev;
return *this;
}//重载后置--
self operator--(int a)
{
self temp(*this);
_node = _node->_prev;
return temp;
}重载 != 和 ==
这里只需要比较_node是否相同即可，因为_node本身就是指向结点的指针，保存着结点的地址，只要地址相同，那自然就是同一个结点了
//重载!=
bool operator!=(const self& s)const
{
return _node != s._node;
}
//重载==
bool operator==(const self& s)const
{
return _node == s._node;
}* 运算符的重载
当我们使用 解引用操作符 时，是想得到该位置的数据内容。因此，我们直接返回当前结点指针所指结点的数据即可，但是这里需要使用引用返回，因为解引用后可能需要对数据进行修改。
//重载*
//返回迭代器指向的结点的值域
// T& operator*()
Ref operator*()
{
return _node->_data;
}-> 运算符的重载
有时候，实例化的模板参数是自定义类型，我们想要像 指针 一样访问访问自定义类型力的成员变量，这样显得更通俗易懂，所以就要重载 -> 运算符，它的返回值是 T*
想想如下场景：
当 list容器 当中的每个结点存储的不是内置类型，而是自定义类型，例如数据存储类，那么当我们拿到一个位置的迭代器时，我们可能会使用 ->运算符访问 Data 的成员：
struct Data
{
Data(int a = int(), double b = double(), char c = char())
:_a(a)
, _b(b)
, _c(c)
{}
int _a;
double _b;
char _c;
};
void TestList()
{
list<Data> lt;
lt.push_back(Data(1, 2.2, 'A'));
auto it = lt.begin();
cout << (*it)._a << endl; //不使用 operator->() 比较别扭
cout << it.operator->()->_b << endl; //这种写法是真实调用情况
cout << it->_c << endl; //编译器直接优化为 it->
}
int main()
{
TestList();
return 0;
}
operator->()存在的意义：使得迭代器访问自定义类型中的成员时更加方便- 如果没有这个函数，只能通过
(*迭代器).成员的方式进行成员访问，很不方便
注意： 编译器将
迭代器.operator->()->成员直接优化为迭代器->成员
- 对于 -> 运算符的重载 ，我们直接返回结点当中所存储数据的地址即可。
// 重载 -> 操作符 ---实现指针访问元素
// T* operator->()
Ptr operator->()
{
return &_node->date;
}迭代器类 总体代码
namespace xas_list
{
template<class T,class Ref,class Ptr>
struct _list_iterator
{
typedef ListNode<T> Node;
typedef _list_iterator<T, Ref, Ptr> self;
Node* _node;
//迭代器构造函数
_list_iterator(Node* x)
:_node(x)
{}
//重载*号 —— 实现解引用操作
Ref operator*()
{
return _node->_data;
}
//重载->操作符 —— 实现指针访问元素
Ptr operator->()
{
return &_node->_data;
}
//++it 重载前置++ —— 让链表能够像数组一样去++操作，访问元素
self& operator++()
{
_node = _node->_next;//前置++返回的是++之后的值，直接让当前位置的结点指向下一个节点
return *this;
}
//it++ 重载后置++ —— （这里需要加上int作为一个站位符，与前置++区分）
self operator++(int)
{
self tmp(*this);
_node = _node->_next;//后置++返回的是++之前的值，需要保存当前节点，再指向下一个节点
return tmp;
}
//--it 重载前置-- —— 让链表能够像数组一样去--操作，访问元素
self& operator--()
{
_node = _node->_prev;//前置--返回的是--之后的值，直接让当前位置的结点指向前一个节点
return *this;
}
//it-- 重载后置-- ——（这里需要加上int作为一个站位符，与前置--区分）
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;//后置--返回的是--之前的值，需要保存当前节点，再指向下一个节点
return tmp;
}
//重载==
bool operator==(const self& it)const
{
return _node == it._node;
}
//重载!=
bool operator!=(const self& it)const
{
return _node != it._node;
}
};
}五、list 结构的完善
上面我们对 节点结构、正向迭代器实现原理及注意点一一做了介绍，最后一步也是最重要的一步，那就是将list结构完善起来，实现list的功能。
成员变量和模板参数
- 因为 list 可以存储各种类型的元素，因此 list 类要设置为模板，T就是存储的元素的类型。
- 因为 结点类 和 迭代器类 的类名太长，所以用 typedef 关键为它们取了别名。这里迭代器的三个参数之所以设置为<T , T& , T*>，是因为list类只给出了一个模板参数，而迭代器类应该有三个，因此用 T& 和 T* 作为另外两个参数。
//带头结点的双向链表
template<class T>
class list
{
typedef ListNode<T> Node;
public:
typedef _list_iterator<T, T&, T*> Iterator; //正向迭代器
typedef _list_iterator<T, const T&, const T*> const_iterator;
private:
Node* _head; //指向头结点的指针
}默认成员函数
构造函数
list 的成员变量是 一个节点类，在构造头节点时，需要将这单个头节点构造成一个双向循环链表；
//构造函数
list()
{
_head = new Node; //new一个节点出来
_head->_prev = _head;
_head->_next = _head; //_prev 和 _next 同时指向了头结点，形成了双向循链表
}拷贝构造
拷贝构造是用一个已有对象去构造出另一个对象，首先将待构造对象进行初始化，然后利用迭代器区间去构造一个和 lt1 一样的临时的 tmp 对象，再进行数据的交换，达到深拷贝的目的。
//拷贝构造 --- 现代写法 lt2(lt1)
list(const list<T>& lt)
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
list<T> tmp(lt.begin(), lt.end());
std::swap(_head, tmp._head);
}
迭代器区间构造
由于list可以存储各种类型的元素，所以区间构造时自然也会用到各种类型的迭代器，因此区间构造也应该定义为模版，需要给出模版参数列表。具体实现和上一个函数是差不多的。
//迭代器区间构造
template<class iterator>
list(iterator first, iterator last)
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
while (first != last)
{
push_back(*first);//尾插数据，会根据不同类型的迭代器进行调用
++first;
}
}n个相同元素构造
通过用 n 个 val 来对对象进行初始化，需要注意这里的 T( )是一个匿名对象，作为 val 的缺省参数，因为我们并不知道传给val的是一个对象还是一个整形（或其他），给缺省参数的好处在于，对于自定义类型编译器会去调用自定义类型的构造函数来对val进行初始化，如果是内置类型，它也是有自己的构造函数
//用n个val个构造
list(int n, const T& val = T())
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
for (int i = 0; i < n; i++)
{
push_back(val);
}
}赋值重载
将赋值运算符重载的参数定义为 list 类型的对象而不是对象的引用，传参时会发生值拷贝。
因此我们可以把 list对象 的 this指针 和 拷贝出来的参数 L 指向头结点的指针交换，这样 this指针 就直接指向了拷贝出来的L的头结点。L则指向了list对象的头结点，在函数结束后，作为局部对象的L将被销毁，它指向的空间也会被释放。
//传统写法
list<T>& operator=(const list<T>& lt)
{
if (this != <) //避免自己给自己赋值
{
clear(); //清空容器
for (const auto& e : lt)
{
push_back(e); //将容器lt当中的数据一个个尾插到链表后面
}
}
return *this; //支持连续赋值
}
析构函数
对对象进行析构时，首先调用clear函数清理容器当中的数据，然后将头结点释放，最后将头指针置空即可。
//析构函数
~list()
{
clear(); //清理容器
delete _head; //释放头结点
_head = nullptr; //头指针置空
}
迭代器相关函数
begin 和 end
首先我们应该明确的是：begin 函数返回的是第一个有效数据的迭代器，end函数返回的是最后一个有效数据的下一个位置的迭代器。
对于 list 这个 带头双向循环链表 来说，其第一个有效数据的迭代器就是使用头结点后一个结点的地址构造出来的迭代器，而其最后一个有效数据的下一个位置的迭代器就是使用头结点的地址构造出来的迭代器。（最后一个结点的下一个结点就是头结点）
iterator begin()
{
//返回使用头结点后一个结点的地址构造出来的普通迭代器
return iterator(_head->_next);
}
iterator end()
{
//返回使用头结点的地址构造出来的普通迭代器
return iterator(_head);
}
- 当然，还需要重载一对用于 const对象 的 begin函数 和 end函数。
const_iterator begin() const
{
//返回使用头结点后一个结点的地址构造出来的const迭代器
return const_iterator(_head->_next);
}
const_iterator end() const
{
//返回使用头结点的地址构造出来的普通const迭代器
return const_iterator(_head);
}
访问容器相关函数
fron 和 back
front 和 back 函数分别用于获取第一个有效数据和最后一个有效数据，因此，实现front和back函数时，直接返回第一个有效数据和最后一个有效数据的引用即可。
T& front()
{
return *begin(); //返回第一个有效数据的引用
}
T& back()
{
return *(--end()); //返回最后一个有效数据的引用
}
- 当然，这也需要重载一对用于const对象 的front函数 和 back函数，因为 const对象 调用front和back函数后所得到的数据不能被修改。
const T& front() const
{
return *begin(); //返回第一个有效数据的const引用
}
const T& back() const
{
return *(--end()); //返回最后一个有效数据的const引用
}
增删改查相关函数
insert -- 插入
insert函数可以在所给迭代器之前插入一个新结点。
- 先根据所给迭代器得到该位置处的结点指针cur，然后通过cur指针找到前一个位置的结点指针prev，接着根据所给数据x构造一个待插入结点，之后再建立新结点与cur之间的双向关系，最后建立新结点与prev之间的双向关系即可。
//插入函数
void insert(iterator pos, const T& x)
{
assert(pos._node); //检测pos的合法性
node* cur = pos._node; //迭代器pos处的结点指针
node* prev = cur->_prev; //迭代器pos前一个位置的结点指针
node* newnode = new Node(x); //根据所给数据x构造一个待插入结点
//建立newnode与cur之间的双向关系
newnode->_next = cur;
cur->_prev = newnode;
//建立newnode与prev之间的双向关系
newnode->_prev = prev;
prev->_next = newnode;
}
erase
先根据所给迭代器得到该位置处的结点指针cur，然后通过cur指针找到前一个位置的结点指针prev，以及后一个位置的结点指针next，紧接着释放cur结点，最后建立prev和next之间的双向关系即可。
//删除函数
iterator erase(iterator pos)
{
assert(pos._node); //检测pos的合法性
assert(pos != end()); //删除的结点不能是头结点
node* cur = pos._node; //迭代器pos处的结点指针
node* prev = cur->_prev; //迭代器pos前一个位置的结点指针
node* next = cur->_next; //迭代器pos后一个位置的结点指针
delete cur; //释放cur结点
//建立prev与next之间的双向关系
prev->_next = next;
next->_prev = prev;
return iterator(next); //返回所给迭代器pos的下一个迭代器
}
push_back 和 pop_back
push_back函数就是在头结点前插入结点，而pop_back就是删除头结点的前一个结点。
//尾插
void push_back(const T& x)
{
insert(end(), x); //在头结点前插入结点
}
//尾删
void pop_back()
{
erase(--end()); //删除头结点的前一个结点
}
push_front 和 pop_front
push_front函数就是在第一个有效结点前插入结点，而pop_front就是删除第一个有效结点。
//头插
void push_front(const T& x)
{
insert(begin(), x); //在第一个有效结点前插入结点
}
//头删
void pop_front()
{
erase(begin()); //删除第一个有效结点
}
容量相关函数
size
size函数用于获取当前容器当中的有效数据个数，因为list是链表，所以只能通过遍历的方式逐个统计有效数据的个数。
size_t size() const
{
size_t sz = 0; //统计有效数据个数
const_iterator it = begin(); //获取第一个有效数据的迭代器
while (it != end()) //通过遍历统计有效数据个数
{
sz++;
it++;
}
return sz; //返回有效数据个数
}
empty
empty函数用于判断容器是否为空，我们直接判断该容器的begin函数和end函数所返回的迭代器，是否是同一个位置的迭代器即可。（此时说明容器当中只有一个头结点）
bool empty() const
{
return begin() == end(); //判断是否只有头结点
}
resize
resize函数的规则：
- 若当前容器的size小于所给n，则尾插结点，直到size等于n为止。
- 若当前容器的size大于所给n，则只保留前n个有效数据。
- 实现resize函数时，不要直接调用size函数获取当前容器的有效数据个数，因为当你调用size函数后就已经遍历了一次容器了，而如果结果是size大于n，那么还需要遍历容器，找到第n个有效结点并释放之后的结点。
void resize(size_t n, const T& val = T())
{
iterator i = begin(); //获取第一个有效数据的迭代器
size_t len = 0; //记录当前所遍历的数据个数
while (len < n&&i != end())
{
len++;
i++;
}
if (len == n) //说明容器当中的有效数据个数大于或是等于n
{
while (i != end()) //只保留前n个有效数据
{
i = erase(i); //每次删除后接收下一个数据的迭代器
}
}
else //说明容器当中的有效数据个数小于n
{
while (len < n) //尾插数据为val的结点，直到容器当中的有效数据个数为n
{
push_back(val);
len++;
}
}
}
clear
clear函数用于清空容器，我们通过遍历的方式，逐个删除结点，只保留头结点即可。
void clear()
{
iterator it = begin();
while (it != end()) //逐个删除结点，只保留头结点
{
it = erase(it);
}
}
六、list 容器的模拟实现整体代码
list.h
#pragma once
#include <iostream>
#include <string>
#include <assert.h>
using std::ostream;
using std::istream;
using std::cin;
using std::cout;
using std::endl;
// 为了避免和库里的 list 产生冲突，在自己的命名空间内实现 list
// 带头---双向---循环---链表
namespace xas_list
{
// 通过模板能够实现不同类型的数据存储
template<class T>
// 链表节点的构造
struct ListNode
{
ListNode<T>* _next; // 指向后面节点的指针
ListNode<T>* _prev; // 指向前面节点的指针
T _data; // 一个节点中的数据
// 构造函数
ListNode(const T& x = T())
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{}
};
// 模拟实现迭代器
template<class T, class Ref, class Ptr>
// 模式一个迭代器 类型
struct _list_iterator
{
typedef ListNode<T> Node; // 为节点类 取别名
//只要用自己的类型，就对其typedef成self，方便后续使用
typedef _list_iterator<T, Ref, Ptr> self; // 为正向迭代器类 取别名
// 成员变量
Node* _node; // _node 表示一个节点
_list_iterator(Node* node = nullptr) // 默认构造函数
:_node(node)
{}
// ++it 重载前置++ —— 让链表能够像数组一样去++操作，访问元素
// 注意：这里的 this 不是局部变量，函数结束不会被销毁，可以使用引用返回，减少拷贝次数
self& operator++()
{
//前置++返回的是++之后的值，直接让当前位置的结点指向下一个节点
_node = _node->_next;
return *this;
}
//重载后置++
//此时需要返回temp对象，而不是引用
//因为temp对象是局部的对象
//函数结束后就被释放
//it++ 重载后置++ —— （这里需要加上int作为一个站位符，与前置++区分）
self operator++(int a)
{
self temp(*this);
_node = _node->_next; //后置++返回的是++之前的值，需要保存当前节点，再指向下一个节点
return temp;
}
//重载前置--
self& operator--()
{
_node = _node->_prev;
return *this;
}
//重载后置--
self operator--(int a)
{
self temp(*this);
_node = _node->_prev;
return temp;
}
// 赋值重载重载 *
//返回迭代器指向的结点的值域
Ref operator*()
{
return _node->_data;
}
// 重载 -> 操作符 ---实现指针访问元素
Ptr operator->()
{
return &_node->date;
}
// 赋值重载 !=
bool operator!=(const self& s) const
{
return _node != s._node;
}
// 赋值重载 ==
bool operator==(const self& s) const
{
return _node == s._node;
}
};
template<class T>
// 创建一个 list 类
class list
{
typedef ListNode<T> Node; // 重新命名节点(结构体)的名称
public:
typedef _list_iterator<T, T&, T*> iterator; // 为 迭代器类型取 别名
typedef _list_iterator<T, const T&, const T*> const_iterator;
// 正向迭代器 和 正向 const 迭代器
iterator begin();
iterator end();
const_iterator begin()const;
const_iterator end()const;
// 默认成员函数
list(); // 构造函数 --- 无参构造
list(int n, const T& val = T()); // 用 n个val 构造
template<class iterator>
list(iterator first, iterator last) // 迭代器区间构造
{
empty_init();
while (first != last)
{
push_back(*first);
++first;
}
}
~list(); // 析构函数
list(list<T>& lt); // 拷贝构造
void empty_init(); // 初始化一个循环链表
list<T>& operator=(list<T> lt); // 赋值运算符符重载
// 容量相关的函数
size_t size() const; // 计算节点的有效个数
bool Empty()const; // 判空 不为空时，返回 true
void clear(); // 清空数据
void resize(size_t n, const T& val = T()); // 设置list对象的有效元素个数
// 访问容器相关函数
T& front(); // 返回第一个有效数据
T& back(); // 返回最后一个有效数据
const T& front() const;
const T& back() const;
// 修改容器内容的相关函数
void push_back(const T& x); // 尾插
iterator insert(iterator pos, const T& x); // 插入
void push_front(const T& x); // 头插
iterator erase(iterator pos); // 删除
void pop_back(); // 尾删
void pop_front(); // 头删
void swap(list<T>& temp); // 交换函数
private:
Node* _head;
};
// 打印函数
void printf_list(const list<int>& lt);
}list.cpp
#include "list.h"
template<class T>
xas_list::list<T>::list() // 构造函数 --- 无参构造
{
_head = new Node; //申请创建一个新的节点 --- 双向循环
_head->_next = _head;
_head->_prev = _head;
}
template<class T> // 用 n个val 进行构造
xas_list::list<T>::list(int n, const T& val)
{
// 创建一个空节点
_head = new Node;
// 形成一个带头双向循环链表
_head->_prev = _head;
_head->_next = _head;
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
template<class T>
xas_list::list<T>::~list() // 析构函数
{
clear();
delete _head;
_head = nullptr;
}
// 初始化一个循环链表
template<class T>
void xas_list::list<T>::empty_init()
{
//申请创建一个新的节点 --- 双向循环
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
template<class T>
xas_list::list<T>::list( list<T>& lt)
{
//申请创建一个新的节点 --- 双向循环
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
template<class T>
void xas_list::list<T>::swap(list<T>& temp)
{
std::swap(_head, temp._head);
}
// lt1 = lt2; --- 赋值重载
template<class T>
xas_list::list<T>& xas_list::list<T>::operator=(list<T> lt)
{
//if (this != <) // 判断一下是否有给自己赋值
//{
// // 将lt1 先清空，再将lt2 插入到 lt1中
// // 注意 this 指针
// clear();
// for (const auto& e : lt)
// {
// push_back(e);
// }
//}
swap(lt);
return *this;
}
template<class T>
void xas_list::list<T>::clear() // 清空数据
{
//复用erase
iterator it = begin();
while (it != end())
{
it = erase(it);//用it接收删除后的下一个结点的位置
}
}
// 正向迭代器
// begin迭代器指向的是正方向第一个有效结点，也就是头结点的下一个结点。
// 因为有 哨兵位的存在
template<class T>
typename xas_list::list<T>::iterator xas_list::list<T>::begin()
{
return iterator(_head->_next);
}
// end迭代器指向的是正方向最后一个有效结点的下一个结点，也就是头结点。
template<class T>
typename xas_list::list<T>::iterator xas_list::list<T>::end()
{
return iterator(_head);
}
template<class T>
typename xas_list::list<T>::const_iterator xas_list::list<T>::begin()const
{
return const_iterator(_head->_next);
}
template<class T>
typename xas_list::list<T>::const_iterator xas_list::list<T>::end()const
{
return const_iterator(_head);
}
template<class T>
// ListNode(const T& x = T()) 这里的 T() 的给一个缺省值
void xas_list::list<T>::push_back(const T& x) // 尾插
{
// 创建一个新的节点 ---- Node
//Node* newnode = new Node(x);
//Node* tail = _head->_prev; // 找尾节点--------头节点的前一个节点
进行尾插
//tail->_next = newnode;
//newnode->_prev = tail;
//newnode->_next = _head;
//_head->_prev = newnode;
insert(end(), x);
}
// 头插
template<class T>
void xas_list::list<T>::push_front(const T& x)
{
insert(begin(), x);
}
// 插入
template<class T>
typename xas_list::list<T>::iterator xas_list::list<T>::insert(iterator pos, const T& x)
{
// 保存当前节点
Node* cur = pos._node;
Node* prev = cur->_prev;
// 创建一个新的节点
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return iterator(newnode);
}
// 删除
template<class T>
typename xas_list::list<T>::iterator xas_list::list<T>::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;
return iterator(next);
}
// 尾删
template<class T>
void xas_list::list<T>::pop_back()
{
erase(--end());
}
// 头删
template<class T>
void xas_list::list<T>::pop_front()
{
erase(begin());
}
// 判断 list 的有效链表个数
template<class T>
size_t xas_list::list<T>::size() const
{
size_t count = 0;
list<T>::const_iterator it = begin();
while (it != end())
{
count++;
it++;
}
return count;
}
// 判断 list 是否为空
template<class T>
bool xas_list::list<T>::Empty() const
{
return _head->_next == _head;
}
template<class T>
void xas_list::list<T>::resize(size_t n, const T& val)
{
list<T>::iterator it = begin(); //获取第一个有效数据的迭代器
size_t len = 0; //记录当前所遍历的数据个数
while (len < n && it != end())
{
len++;
it++;
}
if (len == n) //说明容器当中的有效数据个数大于或是等于n
{
while (it != end()) //只保留前n个有效数据
{
it = erase(it); //每次删除后接收下一个数据的迭代器
}
}
else //说明容器当中的有效数据个数小于n
{
while (len < n) //尾插数据为val的结点，直到容器当中的有效数据个数为n
{
push_back(val);
len++;
}
}
}
template<class T>
T& xas_list::list<T>::front()
{
return *begin();
}
template<class T>
T& xas_list::list<T>::back()
{
return *(--end());
}
template<class T>
const T& xas_list::list<T>::front() const
{
return *begin();
}
template<class T>
const T& xas_list::list<T>::back() const
{
return *(--end());
}
// 打印对应的链表
void xas_list::printf_list(const list<int>& lt)
{
list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
// 遍历的测试
void test1()
{
xas_list::list<int> lt(5,6);
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_front(0);
// 头删
lt.pop_back();
// 尾删
lt.pop_front();
// -------------迭代器测试------------------//
cout << "迭代器的测试" << endl;
xas_list::list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
cout << "范围for的测试" << endl;
// -------------范围 for 测试------------------//
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
cout << "清空数据" << endl;
// 清空数据
lt.clear();
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
void test2()
{
xas_list::list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
cout << "拷贝构造" << endl;
xas_list::list<int> copy(lt);
for (auto e : copy)
{
cout << e << " ";
}
cout << endl;
cout << "赋值重载" << endl;
xas_list::list<int> lt1;
lt1.push_back(10);
lt1.push_back(20);
lt1.push_back(33);
lt = lt1;
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
// const 迭代器
void test3()
{
xas_list::list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
xas_list::list<int> l3(arr, arr + 10); //迭代器区间构造
cout << l3.size() << endl;
cout << l3.Empty() << endl;
l3.resize(12,2);
cout << l3.back() << endl;
cout << l3.front() << endl;
printf_list(l3);
}
int main()
{
test3();
return 0;
}七、共勉
以下就是我对 list容器 的模拟实现 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对 C++stack 的理解，请持续关注我哦！！！
本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！
转载请注明出处： 免费源码网-免费的源码资源网站 » 【C++】list 容器的增删改查---模拟实现（图例超详细解析！！！）
发表评论 取消回复