【C++】—— list 模拟实现
1 list 基础结构
l
i
s
t
list
list 的底层就是我们之前学过的
双向链表
，它由一个哨兵位头结点
_pHead
和记录链表长度的
_size
组成。
而链表中的每个节点都是由
两个自身类型指针
和
一个存储数据的变量组成
的。因此，我们不仅要定义链表的类，还要定义节点的类
下面是
l
i
s
t
list
list 的成员变量和
整体框架
namespace my_list
{template<classT>structListNode{
ListNode* _prev;
ListNode* _next;
T _val;//默认构造ListNode(const T& val =T()):_prev(nullptr),_next(nullptr),_val(val){}};template<classT>classlist{typedef ListNode<T> Node;//给节点重命名//成员函数···private:
Node* _pHead;//哨兵位头结点指针
size_t _size;}}
因为我们要频繁访问节点，因此我们直接用
s
t
r
u
c
t
struct
struct 定义节点，其
成员变量默认全公有
。
2 默认构造
我们先写一个简单的无参默认构造出来。
默认构造可以直接这样写吗？
list():_pHead(nullptr),_size(0){}
不可以的，因为双向链表有个
哨兵位
。即使链表中没有任何数据，头节点指针也是指向哨兵位，而不是空，所以我们应创建哨兵位，并将其初始化
而哨兵位的前驱指针 _
p
r
e
v
prev
prev 和后继指针 _
n
e
x
t
next
next，因为整个链表只有它自己，它的前一个和后一个节点都是自己，因此 _
p
r
e
v
prev
prev 和 _
n
e
x
t
next
next 都是指向哨兵位自己
list(){
_pHead =new Node;
_pHead->_next = _pHead;
_pHead->_prev = _pHead;
_size =0；
}
其是不仅仅是无参的构造，所有的构造函数第一步都是
初始化哨兵位
，因此我们不妨单独写一个函数出来
list(){CreateHead()；
}voidCreateHead(){
_pHead =new Node;
_pHead->_next = _pHead;
_pHead->_prev = _pHead;
_size =0;}
这里有个问题就是
CreateHead()
是非
c
o
n
s
t
const
const 成员函数，那定义
c
o
n
s
t
const
const 成员是否还能来调用呢？答案自然是可以的，**因为
c
o
n
s
t
const
const 变量在定义的时候是不具有
c
o
n
s
t
const
const 属性的**，定义完成之后才有。比如说：
//如果在定义之前就具有const属性，那么n就无法赋值//const变量只有在定义时可以被赋值constint n =10;const list<int> l1;
3 迭代器
要模拟实现
l
i
s
t
list
list ，
迭代器的实现
是其中的重中之重。
前面我们模拟实现
s
t
r
i
n
g
string
string 和
v
e
c
t
o
r
vector
vector，他们的迭代器都是原生指针，他们的原生指针完美符合迭代器的所有要求。
其本质是因为他们底层物理空间是连续的。
但
l
i
s
t
list
list 不像
s
t
r
i
n
g
string
string 和
v
e
c
t
o
r
vector
vector 那样天生丽质，它的底层结构是一个一个节点，并不连续，无法满足迭代器的要求（比如 ++，我们希望的是迭代器跳到下一个节点，如果使用原生指针，因为不是连续的物理空间，当前节点 ++ 大概率是个野指针）。
但没关系，
l
i
s
t
list
list 可以通过封装，通过运算符重载，来满足迭代器的要求。
3.1 整体框架
迭代器其本身就是
模拟指针的行为
，既然节点的原生指针无法满足迭代器的要求，我们对节点指针进行封装，通过运算符重载让其满足迭代器的需求
template<classT>structListIterator{typedef ListIterator<T> Self;//给自身类(迭代器)重命名，短一点方便typedef ListNode<T> Node;//节点重命名//成员变量：节点的指针
Node* pNode;//成员函数//··· };
因为待会链表中要大量访问成员变量，我们直接用默认全公有的
s
t
r
u
c
t
struct
struct
到现在，我们一共实现了三个类，为什么要实现三个类呢？我们先把每个类的作用过一遍：
class list：链表这个类是链表的基本结构，指向哨兵位的头结点，管理这整个链表struct ListNode：节点这个类是因为链表中每个节点都是自定义类型，每个数据都是存在一个独立的结构体里面struct ListIterator：迭代器这个类，遍历整个链表本来是用节点的指针，但是节点的指针是不符合我们的预期，我们希望有一个迭代器统一的方式进行遍历，因此我们用一个结构去封装节点的指针，封装以后通过重载运算符使节点的指针能达到迭代器那样的行为
3.2 成员函数
有了迭代器这个类，我们就可以运用运算符重载满足迭代器的行为啦
template<classT>structListIterator{typedef ListIterator<T> Self;typedef ListNode<T> Node;//成员变量
Node* pNode;//解引用
T&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;}//不等于booloperator!=(const Self& x){return pNode != x.pNode;}//等于booloperator==(const Self& x){return pNode == x.pNode;}}
3.3 begin() 与 end() 的实现
迭代器的基本行为实现了，我们也可以在
list类
中实现
begin()
、
end()
等函数了
begin()
函数是返回第一个迭代器，我们要构造第一个位置的迭代器，那怎么构造呢？我们用第一个节点的指针，即
_pHead->_next
，就能构造第一个迭代器，但现在
ListIterator类
中还缺少一个构造函数：
//默认构造ListIterator(Node* p =nullptr):pNode(p){}//拷贝构造ListIterator(const ListIterator& x){
pNode = x.pNode;}
其实上述拷贝构造可以不用实现，编译器会自己生成一个拷贝构造，完成浅拷贝，指向链表的节点。
这里不要认为有指针指向资源就要自己实现深拷贝，而是看指针所指向的资源是不是属于自己的。像
s
t
r
i
n
g
string
string、
v
e
c
t
o
r
vector
vector 那些就需要自己实现深拷贝，但**迭代器指向的是链表的资源，并不是迭代器自己的**，并且迭代器本身的目标就是指向链表的节点，以此来访问遍历链表，因此
浅拷贝
即可。
所以赋值重载和析构与不需要写
现在，万事具备只欠东风，我们还要在
list类
中将
ListIterator类
t
y
p
e
d
e
f
typedef
typedef 成
i
t
e
r
a
t
o
r
iterator
iterator
template<classT>classlist{typedef ListNode<T> Node;typedef ListIterator<T> iterator;//重命名为iterator//成员函数···private:
Node* _pHead;
size_t _size;}
下面是
begin()
的实现
iterator begin(){
iterator it(_pHead->_next);return it;}
上述是有名对象的写法，我们可以用匿名对象的写法
iterator begin(){returniterator(_pHead->_next);}
甚至我们可以用
隐式类型转换
，直接传指针就好啦
迭代器本身就是节点的指针，指针节点指针本身不满足迭代器的那些需求，所以我们才用一个类把他封装一层，用重载运算符使其达到迭代器的要求。
iterator begin(){return _pHead->_next;}
end()
是最后一个数据的下一个位置，就是哨兵位的头结点
iterator end(){return _pHead;}
3.4 operator-> 的实现
既然迭代器模拟的是指针的行为，那它还要实现
operator->
什么情况下用到
->
运算符呢？
现在我们定义一个类型 AA，链表中存储的数据是 AA 类型，我们想依次遍历链表，打印每个节点 AA 中的两个成员变量
structAA{int _a1 =1;int _a2 =2;}voidtest1(){
list<AA> lta;
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());
list<AA>::iterator it = lta.begin();while(it != lta.end()){
cout <<(*it)._a1 <<" "<<(*it)._a2 << endl;
cout << it->_a1 <<" "<< it->_a2 << endl;}}
上述
(*it)._a1
与
it->_a1
的写法是等价的，但现在还没重载
->
运算符
下面是
operator->
的实现方式
T*operator->(){return&(pNode->_val);}
operator->
的实现方式非常奇怪，返回的是
T*
其实这里省略了一个 ->，因为太难看了，为了可读性省略了一个 ->
cout << it->_a1 <<" "<< it->_a2 << endl;//本质是这样的
cout << it->->_a1 <<" "<< it->->_a2 << endl;
第一个->是运算符重载出来的，第二个则是普通的->
本质是这样的:
cout << it.operator->()->_a1 <<" "<< it.operator->()->_a2 << endl;
cout <<&(pNode->_val)->_a1 <<" "<<&(pNode->_val)->_a2 << endl;
3.5 const 迭代器
3.5.1 const 迭代器为什么命名 const_iterator
首先问大家一个问题：
c
o
n
s
t
const
const 迭代器为什么是
const_iterator
，而不是
const iterator
呢
c
o
n
s
t
const
const 迭代器是
自身不能修改
还是
指向的内容不能修改
呢？
就和指针一样，指针的
c
o
n
s
t
const
const 有两个，一个在 * 之前，一个在 * 之后
T*const ptr1//指针本身不能修改const T* ptr2//指向的内容不能修改
如果是
const iterator
，const 直接修饰一个变量，就是这个变量本身不能修改，即迭代器本身不能修改，而我们
c
o
n
s
t
const
const 迭代器是要指向的内容不能修改，所以
const_iterator
更合适
3.5.2 const 迭代器的实现
那我们如何让迭代器指向的内容不能修改呢？
迭代器修改我们指向的内容是怎么修改的？通过
operator*
和
operator->
，那我们**在其返回值上加上
c
o
n
s
t
const
const 就不能修改了**
const T&operator*(){return pNode->_val;}const T*operator->(){return&(pNode->_val);}
那我们就再自己实现一个
c
o
n
s
t
const
const 迭代器的封装吧
template<classT>structconst_ListIterator{typedef const_ListIterator<T> Self;typedef ListNode<T> Node;
Node* pNode;const_ListIterator(Node* p =nullptr):pNode(p){}const T&operator*(){return pNode->_val;}const T*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;}booloperator!=(const Self& x){return pNode != x.pNode;}booloperator==(const Self& x){return pNode == x.pNode;}};
3.5.3 合并两个迭代器
上面我们再重新封装了一个
const_iterator
，基本满足了需求，但是代码太冗余了，除了
operator*
和
operator->
的返回值类型不一样，其他代码全是一样的，有什么办法将他们合二为一呢？
我们来看一下库中是怎么实现的
库中的
__list_iterator类
，用了三个模板参数，新增了
Ref
与
Ptr
两个参数。
在
l
i
s
t
list
list 类中，将
__list_iterator<T, T&, T*>
t
y
p
e
d
e
f
typedef
typedef 成
i
t
e
r
a
t
o
r
iterator
iterator，将
__list_iterator<T, const T&, const T*>
t
y
p
e
d
e
f
typedef
typedef 成
c
o
n
s
t
const
const_
i
t
e
r
a
t
o
r
iterator
iterator。
也就是说
i
t
e
r
a
t
o
r
iterator
iterator 的
R
e
f
Ref
Ref 参数即 T&，
P
t
r
Ptr
Ptr 即参数 T*，
c
o
n
s
t
const
const_
i
t
e
r
a
t
o
r
iterator
iterator 的
R
e
f
Ref
Ref参数即
c
o
n
s
t
const
const T&，
P
t
r
Ptr
Ptr 参数即
c
o
n
s
t
const
const T*
以
operator*
举例：
T& 传给Ref，Ref 即reference，
operator*
的返回值是reference，替换过来
operator*
的返回值就是 T&
对
c
o
n
s
t
const
const_
i
t
e
r
a
t
o
r
iterator
iterator
c
o
n
s
t
const
const T& 传给
R
e
f
Ref
Ref，替换过来
operator*
的返回值就是
c
o
n
s
t
const
const T&
其实，这种写法与上面我们自己实现两个类模板并没有本质区别，他们实例化出来都是两个不同的类。不同的是第一种写法是我们自己写了两个不同的类，而第二种是我们通过控制模板参数让编译器实例化出两个不同的类，把我们干的活交给了编译器
代码如下：
template<classT,classRef,classPtr>structListIterator{typedef ListIterator<T, Ref, Ptr> Self;typedef ListNode<T> Node;
Node* pNode;ListIterator(Node* p =nullptr):pNode(p){}
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;}booloperator!=(const Self& x){return pNode != x.pNode;}booloperator==(const Self& x){return pNode == x.pNode;}};
4 源码
对于
l
i
s
t
list
list 的其他成员函数，与前面的
s
t
r
i
n
g
string
string、
v
e
c
t
o
r
vector
vector 实现起来都大同小异，这里就不再赘述了，我们直接看源码
#pragmaonce#include<iostream>#include<assert.h>usingnamespace std;namespace my_list
{template<classT>structListNode{
ListNode* _prev;
ListNode* _next;
T _val;ListNode(const T& val =T()):_prev(nullptr),_next(nullptr),_val(val){}};template<classT,classRef,classPtr>structListIterator{typedef ListIterator<T, Ref, Ptr> Self;typedef ListNode<T> Node;
Node* pNode;ListIterator(Node* p =nullptr):pNode(p){}
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;}booloperator!=(const Self& x){return pNode != x.pNode;}booloperator==(const Self& x){return pNode == x.pNode;}};template<classT>classlist{typedef ListNode<T> Node;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T,const T&,const T*> const_iterator;list():_pHead(nullptr),_size(0){CreateHead();}list(int n,const T& value =T()){CreateHead();while(n--){push_back(value);}}template<classIterator>list(Iterator first, Iterator last){CreateHead();
Iterator it = first;while(it != last){push_back(*it);++it;}}list(const list<T>& l){CreateHead();
const_iterator it = l.begin();while(it != l.end()){push_back(*it);++it;}}
list<T>&operator=(list<T> l){swap(l);return*this;}~list(){clear();delete _pHead;
_pHead =nullptr;}
iterator begin(){return _pHead->_next;}
iterator end(){return _pHead;}
const_iterator begin()const{return _pHead->_next;}
const_iterator end()const{return _pHead;}
size_t size()const{return _size;}boolempty()const{return _size ==0;}
T&front(){return _pHead->_next->_val;}
T&back(){return _pHead->_prev->_val;}const T&front()const{return _pHead->_next->_val;}const T&back()const{return _pHead->_prev->_val;}voidpush_back(const T& val){
Node* p =newNode(val);
p->_next = _pHead;
_pHead->_prev->_next = p;
p->_prev = _pHead->_prev;
_pHead->_prev = p;++_size;}voidpop_back(){
Node* p = _pHead->_prev;
p->_prev->_next = _pHead;
_pHead->_prev = p->_prev;delete p;--_size;}voidpush_front(const T& val){
Node* p =newNode(val);
p->_next = _pHead->_next;
p->_prev = _pHead;
_pHead->_next = p;
p->_next->_prev = p;++_size;}voidpop_front(){
Node* p = _pHead->_next;
_pHead->_next = p->_next;
p->_next->_prev = _pHead;delete p;--_size;}
iterator insert(iterator pos,const T& val){
Node* p =newNode(val);
p->_next = pos.pNode;
p->_prev = pos.pNode->_prev;
pos.pNode->_prev->_next = p;
pos.pNode->_prev = p;++_size;return pos;}
iterator erase(iterator pos){assert(pos !=end());
iterator ret = pos.pNode->_next;
pos.pNode->_prev->_next = pos.pNode->_next;
pos.pNode->_next->_prev = pos.pNode->_prev;delete pos.pNode;--_size;return ret;}voidclear(){
iterator it =begin();while(it !=end()){
iterator cur = it++;delete cur.pNode;}
_pHead->_next = _pHead;
_pHead->_prev = _pHead;
_size =0;}voidswap(list<T>& l){
std::swap(_pHead, l._pHead);
std::swap(_size, l._size);}private:
Node* _pHead;
size_t _size;voidCreateHead(){
_pHead =new Node;
_pHead->_next = _pHead;
_pHead->_prev = _pHead;
_size =0;}};}template<classContainer>voidprint_container(const Container& v){auto it = v.begin();while(it != v.end()){
cout <<*it <<" ";++it;}
cout << endl;}
*好啦，本期关于
l
i
s
t
list
list 的知识就介绍到这里啦，希望本期博客能对你有所帮助。同时，如果有错误的地方请多多指正，让我们在 C++ 的学习路上一起进步！*
本文转载自: https://blog.csdn.net/yusjushd/article/details/141992390
版权归原作者 9毫米的幻想 所有， 如有侵权，请联系我们删除。
版权归原作者 9毫米的幻想 所有， 如有侵权，请联系我们删除。