【C++】---STL之list的模拟实现
- 一、list模拟实现思路
- 二、结点类的实现
- 三、list迭代器的实现
- 1、ListIterator类
- 2、构造函数
- 3、operator*运算符重载
- 5、operator->运算符重载
- 6、operator！=运算符重载
- 7、operator==运算符重载
- 8、前置++
- 9、后置++
- 10、前置--
- 11、后置--
- 四、list类的实现
- 1、list类
- 2、构造
- 3、析构
- 4、拷贝构造
- 5、赋值运算符重载
- （1）传统的赋值运算符重载
- （2）现代的赋值运算符重载
- 6、迭代器
- 7、insert()
- 8、erase()
- 9、clear()
- 10、push_front()
- 11、push_back()
- 12、pop_front()
- 13、pop_back()
- 14、empty()
- 15、size()
- 五、完整代码
一、list模拟实现思路
list的模拟实现比 string vector的模拟实现略微复杂一点：
（1）由于链表的每一个结点本身就是一个结构体，里面包括数据和指针，所以在接下来的模拟中，我们会将链表的每一个结点封装为一个类，也就是结点类。
（2）链表中数据的物理储存空间是不连续的，但是string和vector他们的数据储存物理空间是连续的。因此在访问链表的数据的时候，不能用原生的迭代器来进行访问，我们需要自己重载一个迭代器，自己封装一个迭代器的类。
list的模拟的大体思路：
二、结点类的实现
单个结点类的成员变量有三个：
（1）结点值：_val
（2）指向前一个结点的指针：_prev
（3）指向后一个结点的指针：_next
结点无需拷贝构造、赋值运算符重载，由于没有额外申请空间，因此也不需要析构
// 1.单个的结点类：
template<class T>
struct Listnode
{
T _val;
Listnode<T>* _next;
Listnode<T>* _prev;
// 构造:
Listnode(const T& x = T())
:_val(x)
, _next(nullptr)
, _prev(nullptr)
{
}
};
三、list迭代器的实现
1、ListIterator类
（1）我们为什么要对链表的迭代器进行一个单独的封装？
因为之前普通的迭代器++都是连续，可以直接进行访问数据。
但是链表不一样，物理空间连续所以说我要把这个迭代器进行一个类的封装，然后在里面对他运算符重载（例如：++）我们就可以掌控这个迭代器的行为！
当原生的迭代器或者运算符不合我们所需要的预期的话，就可以把它进行一个封装，我们自己来重载，达到我们所需要的预期
（2）迭代器有两种，一种是普通迭代器，一种是const的迭代器
为了不使代码冗余，我们就会将两个迭代器写在一起，用模板！
对于T&，类模板实例化出两个类，一个是T&类，一个是const T&类，同理，T*也一样。使用 ：
template<class T,class Ref,class Ptr>// Ref==T& Ptr==T*
类模板就会实例化出来两个类，一个是普通的、不带const的T，T&， T*，另一个是带const的T，const T&， const T*，其中Ref是引用，Ptr是指针，该类模板实例化了以下这两个类模板：
template class<T,T&,T*> iterator;
template class<const T, const T& ,const T*> const_iterator;
这样我们就解决了两个类的问题。
2、构造函数
template<class T,class Ref,class Ptr>
struct ListIterator
{
typedef Listnode<T> Node;// 1.(这个是单个结点“类型”的重定义) 不管你是什么类型的结点 我都给你整成Node，因为Listnode<T>是一个结点模版！
typedef ListIterator<T, Ref, Ptr> Self; // 2.(这个是本迭代器指针“类型”的重定义)
// 成员变量：
Node* _node;
// 构造：
ListIterator(const Node* node)
:_node(node)
{
}
};
3、operator*运算符重载
// 重载*(*it)
// Ref==T&
Ref operator*()// 为什么要传引用返回呢？因为有的时候我们可能需要对it进行修改+1,-1等等。
{
return _node->_data;
}
5、operator->运算符重载
// 重载->
//Ptr==T*
Ptr operator->()
{
6、operator！=运算符重载
对于==和!=的重载的时候，我们一定要想清楚到底是对它里面节点的值来判断相不相等，还是说来判断指向这个结点的迭代器指针相不相等。很明显我们这里重载（ = =）和（！=）通过判断结点的迭代器相等不相等来进行重载的。
// !=
bool operator!=(const Self& it)
{
return _node != it._node;
}
7、operator==运算符重载
比较两个迭代器相等不相等的时候一定不能比较所指向节点中的值，万一所有的节点里面值相等都是一样，那你意思就是说：这里面的所有迭代器都是相等吗？不就扯淡吗？！所以说比较迭代器相不相等：就是比较两者是不是指向同一个结点（即：比较指针是否相等！）因为迭代器本质上是指针！
bool operator==(const Self& it)
{
return _node == it._node;
}
8、前置++
//前置++,(++it)
Self& operator++()//因为++对内容进行了修改，所以要传引用返回！
{
_node = _node->_next;
return *this;
}
9、后置++
//后置++，(it++)
Self operator++(int)
{
Self tmp = *this;//因为后置++，要返回的是++之前的值，所以要先保存未++的值在tmp里面！
_node = _node->_next;
return tmp;
}
10、前置–
//前置--,(--it)
Self& operator--()//因为--对内容进行了修改，所以要传引用返回！
{
_node = _node->_prev;
return *this;
}
11、后置–
//后置--，(it)
Self operator--(int)
{
Self tmp = *this;//因为后置--,要返回的是--之前的值，所以要先保存未--的值在tmp里面！
_node = _node->_prev;
return tmp;
}
四、list类的实现
1、list类
list的成员只需要一个头节点，然后通过迭代器来访问后面的其他元素即可。
2、构造
//1、构造：
list()
{
_head = new Node;//会调ListNode的构造函数
_head->_next = _head;//整个链表只有头节点，先构造一个没有实际节点的链表
_head->_prev = _head;//整个链表只有头节点，先构造一个没有实际节点的链表
}
3、析构
// 2、析构
~list()
{
clear();
delete[] _head;
_head = nullptr;
}
4、拷贝构造
//特意写一个，初始化一个哨兵位
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
// 3、拷贝构造
// lt2(lt1)
list(const list<T> lt)
{
empty_init();//先初始化一个头结点
for (auto& e : lt)// 接下来在哨兵位后面 尾插 就可以实现拷贝构造！
{
push_back(e);
}
}
// 需要析构，一般就需要自己写深拷贝
// 不需要析构，一般就不需要自己写深拷贝，默认浅拷贝就可以
};
5、赋值运算符重载
（1）传统的赋值运算符重载
//赋值运算符重载 lt1 = lt 传统写法
list<T> operator=(const list<T>& lt)
{
//链表已存在，只需将节点尾插进去即可
if(this != lt)
{
for (auto& e : lt)
{
push_back(e);
}
}
}
（2）现代的赋值运算符重载
//4、赋值运算符重载(深拷贝)
// lt1=lt2
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
void swap(list<T>& lt)
{
std::(_head, lt._head);
std::(_size, lt._size);
}
6、迭代器
（1）普通迭代器：
iterator begin()
{
//iterator it = _head->_next;// 有名对象 //调用迭代器的构造函数创建一个迭代器it
//return it;
return iterator(_head->_next);// 匿名对象
// return _head->_next; // 不能这样写，因为返回类型是迭代其指针，而你这样返回的是一个结点。
}
iterator end()
{
return iterator(_head);
}
只要你有节点的指针，就可以构造迭代器：
下面这里就是构造了一个迭代器，因为它的返回类型是迭代器，你只要有节点的指针我就可以构造一个迭代器，只不过有两种情况是匿名对象，另外一种是有名对象：
（2）const迭代器：
const_iterator begin() const
{
return const_iterator(_head->_next);//头节点不存数据
}
const_iterator end() const
{
return const_iterator(_head);//尾节点的下一个节点位置即头节点
}
7、insert()
// 3.insert
void insert(iterator pos, const T& val)//在pos位置之前插入val
{
//先用一个指针保存pos的位置！
Node* cur = pos._node;
//创建一个新的节点newnode来接受val的值
Node* newnode = new Node(val);
//再保存pos位置前一个方便newnode插入！
Node* prev = cur->_prev;
//prev newnode cur三者之间的交换
newnode->_prev = prev;
prev->_next = newnode;
newnode->_next = cur;
cur->_prev = newnode;
}
8、erase()
iterator erase(iterator pos)
{
// 1、先保存pos位置的前后！
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
// 2、prev 和 next两者之间进行链接！
prev->_next = next;
next->_prev = prev;
// 3、直接删除cur
delete cur;
// 4、因为是模拟原本库里面的erase函数，返回的就是要删除pos位置的下一个位置的迭代器。
return iterator(next);
}
9、clear()
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
//因为erase会返回要删除结点的下一个位置，所以要用iterator类型的it接受！
}
}
10、push_front()
// 头插
void push_front(const T& x)
{
insert(begin(), x);
}
11、push_back()
// 尾插
void push_back(const T& x)
{
insert(end(), x);
}
12、pop_front()
// 头删
void pop_front()
{
erase(begin());
}
13、pop_back()
// 尾删
void pop_back()
{
erase(--end());
}
14、empty()
bool empty()
{
return (_head->_next == _head);
}
15、size()
size_t size()const
{
size_t count = 0;
Node* cur = _head;
while (cur->_next != _head)
{
cur = cur->_next;
count++;
}
return count;
}
五、完整代码
#pragma once
#include <assert.h>
#include<iostream>
using namespace std;
namespace yjl
{
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迭代器的封装：
//template<class T>
//struct ListIterator
//{
// typedef Listnode<T> Node;// 1.(这个是单个结点“类型”的重定义) 不管你是什么类型的结点 我都给你整成Node，因为Listnode<T>是一个结点模版！
// typedef ListIterator<T> Self; // 2.(这个是本迭代器指针“类型”的重定义)
// Node* _node;
// //构造
// ListIterator(Node* node)
// :_node(node)
// {}
// // 重载*(*it)
// const T& operator*()// 为什么要传引用返回呢？因为有的时候我们可能需要对it进行修改+1,-1等等。
// {
// return _node->_data;
// }
// // 重载->
// const T* operator->()
// {
// return &_node->_data;//得到的是地址：T*
// }
// //前置++,(++it)
// Self& operator++()//因为++对内容进行了修改，所以要传引用返回！
// {
// _node = _node->_next;
// return *this;
// }
// //后置++，(it++)
// Self operator++(int)
// {
// Self tmp = *this;//因为后置++，要返回的是++之前的值，所以要先保存未++的值在tmp里面！
// _node = _node->_next;
// return tmp;
// }
// //前置--,(--it)
// Self& operator--()//因为--对内容进行了修改，所以要传引用返回！
// {
// _node = _node->_prev;
// return *this;
// }
// //后置--，(it)
// Self operator--(int)
// {
// Self tmp = *this;//因为后置--,要返回的是--之前的值，所以要先保存未--的值在tmp里面！
// _node = _node->_prev;
// return tmp;
// }
// bool operator!=(const Self& it)
// {
// return _node != it._node;
// }
// bool operator==(const Self& it)
// {
// return _node == it._node;
// }
//};
// typedef ListIterator<T,T&,T*> iterator;
// typedef ListIterator<T,const T&,const T*> const_iterator;
//list迭代器的封装：
template<class T,class Ref,class Ptr>// Ref==T& Ptr==T*
struct ListIterator
{
typedef Listnode<T> Node;// 1.(这个是单个结点“类型”的重定义) 不管你是什么类型的结点 我都给你整成Node，因为Listnode<T>是一个结点模版！
typedef ListIterator<T,Ref,Ptr> Self; // 2.(这个是本迭代器指针“类型”的重定义)
Node* _node;
//构造
ListIterator(Node* node)
:_node(node)
{}
// 重载*(*it)
// Ref==T&
Ref operator*()// 为什么要传引用返回呢？因为有的时候我们可能需要对it进行修改+1,-1等等。
{
return _node->_data;
}
// 重载->
//Ptr==T*
Ptr operator->()
{
return &_node->_data;//得到的是地址：T*
}
//前置++,(++it)
Self& operator++()//因为++对内容进行了修改，所以要传引用返回！
{
_node = _node->_next;
return *this;
}
//后置++，(it++)
Self operator++(int)
{
Self tmp = *this;//因为后置++，要返回的是++之前的值，所以要先保存未++的值在tmp里面！
_node = _node->_next;
return tmp;
}
//前置--,(--it)
Self& operator--()//因为--对内容进行了修改，所以要传引用返回！
{
_node = _node->_prev;
return *this;
}
//后置--，(it)
Self operator--(int)
{
Self tmp = *this;//因为后置--,要返回的是--之前的值，所以要先保存未--的值在tmp里面！
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
bool operator==(const Self& it)
{
return _node == it._node;
}
};
/// ///
template<class T>
class list
{
typedef Listnode<T> Node;
public:
typedef ListIterator<T,T&,T*> iterator;
typedef ListIterator<T, const T&,const T*> const_iterator;
iterator begin()
{
//iterator it = _head->_next;// 有名对象 //调用迭代器的构造函数创建一个迭代器it
//return it;
return iterator(_head->_next);// 匿名对象
// return _head->_next; // 不能这样写，因为返回类型是迭代其指针，而你这样返回的是一个结点。
}
iterator end()
{
return iterator(_head);
}
// 1.多个节点之间的构造：初始化一个哨兵位
//特意写一个，初始化一个哨兵位
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
// 构造
list()
{
empty_init();
}
// 拷贝构造函数
// lt2(lt1)
list(const list<T>& lt)
{
empty_init();// 先构造一个哨兵位头结点
for (auto& e : lt)// 接下来在哨兵位后面 尾插 就可以实现拷贝构造！
{
push_back(e);
}
}
// 需要析构，一般就需要自己写深拷贝
// 不需要析构，一般就不需要自己写深拷贝，默认浅拷贝就可以
//赋值运算符重载(深拷贝)
// lt1=lt2
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
// 析构
~list()
{
clear();
delete _head;
_head = nullptr;
}
// 2.push_back()
//void push_back(const T& x)
//{
// Node* tmp = new Node(x);
// Node* tail = _head->_prev;// 因为要尾插，所以保存好尾节点！
// tail->_next = tmp;
// tmp->_prev = tail;
// tmp->_next = _head;
// _head->_prev = tmp;
//}
// 头插
void push_front(const T& x)
{
insert(begin(), x);
}
// 尾插
void push_back(const T& x)
{
insert(end(), x);
}
// 头删
void pop_front()
{
erase(begin());
}
// 尾删
void pop_back()
{
erase(--end());
}
// 3.insert
void insert(iterator pos, const T& val)//在pos位置之前插入val
{
//先用一个指针保存pos的位置！
Node* cur = pos._node;
//创建一个新的节点newnode来接受val的值
Node* newnode = new Node(val);
//再保存pos位置前一个方便newnode插入！
Node* prev = cur->_prev;
//prev newnode cur三者之间的交换
newnode->_prev = prev;
prev->_next = newnode;
newnode->_next = cur;
cur->_prev = newnode;
}
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;// 我们delete cur之后，原来的pos迭代器指针也就消失了，但是我们为什么必须要返回一个：迭代器指针？
return iterator(next);// 因为删除的数据是有不确定性的，万一要删除偶数或者后面有其他的用途，我们没有原来pos的位置，我们如何再找到其他的数据呢？
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
//因为erase会返回要删除结点的下一个位置，所以要用iterator类型的it接受！
}
}
//size_t size()const
//{
// size_t count = 0;
// while (_head->_next != _head)
// {
// _head = _head->_next;// 因为_head是不能被修改的！！！，所以要创建一个临时指针来指向_head
// count++;
// }
// return count;
//}
size_t size()const
{
size_t count = 0;
Node* cur = _head;
while (cur->_next != _head)
{
cur = cur->_next;
count++;
}
return count;
}
bool empty()
{
return (_head->_next == _head);
}
private:
Node* _head;
size_t _size;
};
好了，今天的分享就到这里了
如果对你有帮助，记得点赞👍+关注哦！
我的主页还有其他文章，欢迎学习指点。关注我，让我们一起学习，一起成长吧！
