深入篇【C++】手搓模拟实现list类(详细剖析底层实现原理）&& 模拟实现正反向迭代器【容器适配器模式】
- Ⅰ.迭代器实现
- 1.一个模板参数
- 2.两个模板参数
- 3.三个模板参数
- Ⅱ.反向迭代器实现
- 1.容器适配器模式
- Ⅲ.list模拟实现
- 1.定义结点
- 2.封装结点
- 3.构造/拷贝
- 4.迭代器
- 5.插入/头尾插
- 6.删除/头尾删
- 7.析构/清理
- Ⅳ.整代码
Ⅰ.迭代器实现
1.一个模板参数
在模拟实现list之前，我们要理解list中的迭代器是如何实现的。
在vector中迭代器可以看成一个指针，指向vector中的数据。它的解引用会访问到具体的数据本身，++会移动到下一个数据位置上去，这些都是因为vector具有天生的优势：空间上是连续的数组，这样指针就是一个天生完美的迭代器。而list与vector不同，list在空间上并不连续，指针解引用访问到的也不是具体的数据，而是结点本身，指针++也不会移动到下一个结点位置，这些问题都说明list的迭代器不能简单是只是原生指针就可以完成。
正确的实现方法是：
将指向结点的原生指针封装起来，构造出一个自定义类型的迭代器。在这个迭代器里我们通过运算符重载，来改变原生指针的一些行为，比如解引用运算符重载，++运算符重载。这样我们就可以构造出一个满足预期的迭代器了。
使用原生指针作为迭代器不符合需求，迭代器的解引用和++都不符合list迭代器的要求
所以这里将原生指针进行封装，然后使用运算符重载达到我们想要的效果
所以list的迭代器是一个自定义类型，这个自定义类型里存着原生指针
template <class T>//将这个迭代器搞成模板，适用于各种类型
struct _list_iterator
{
typedef listNode<T> Node;//因为结点类被搞成了模板，所以名字很长，我们这里将其重命名为Node
_list_iterator( Node* node)//用原生指针初始化
:_node(node)
{}
T& operator*()//重载*运算符因为原生指针中的解引用不符合list迭代要求
{
return _node->val;//要求解引用要访问到结点的的数据，而不是结点
}
_list_iterator<T>& operator++()//重载++运算符
{
_node = _node->next;//要求++要挪动到下一个结点的位置上去
return *this;
}
T* operator->()
{
return &_node->val;
}
bool operator!=(const _list_iterator<T>& it)
{
return _node != it._node;//用原生指针比较即可
}
Node* _node;//底层封装的是原生指针
};
2.两个模板参数
迭代器基本上已经完成，可以正常使用了。不过list中的迭代器实现并没有这么简单，它的模板参数实现给了三个参数，这里我们才有一个参数，接下来我会一一增加上去。第二个模板参数是什么呢？
第二个模板参数是为了实现const迭代器而设计的，const迭代器要求指向的内容不能被修改，而迭代器本身是可以进行修改的。那如何做到呢？
解引用访问到的就是数据本身，而const迭代器要求指向的数据不能被修改，所以直接让解引用运算符重载函数的返回值加上const修饰即可。
template <class T>//将这个迭代器搞成模板，适用于各种类型
struct _list_iterator
{
typedef listNode<T> Node;
_list_iterator( Node* node)//用原生指针初始化
:_node(node)
{}
const T& operator*()//const迭代器访问时，返回的是const修饰的数据无法被修改。
{
return _node->val;
}
_list_iterator<T>& operator++()//重载++运算符
{
_node = _node->next;
return *this;
}
T* operator->()
{
return &_node->val;
}
bool operator!=(const _list_iterator<T>& it)
{
return _node != it._node;
}
Node* _node;//底层封装的是原生指针
};
有的人会选择拷贝一份封装的迭代器，然后其他都相同，就解引用运算符重载函数返回类型不同，普通迭代器，返回值是T&,const迭代器返回类型是constT&.但这样做实在太冗余了，大佬是再添加一个模板参数来控制这里的迭代器返回类型的。
所以第二个模板参数是为了控制解引用运算符重载函数的返回值类型的。
有的人会这样做：直接给迭代器前面加上const，这样的做法是不对的！
我们要求的const迭代器是：1.迭代器指向的内容不能被修改2.迭代器本身可以修改
1.const T* iterator 2.T* const iterator 这两种情况应该是第一种情况满足要求。
typedef const _list_iterator const_iterator;这种情况是第二种情况const修饰的是这个封装的迭代器，说明是这个迭代器不能被修改，而不是它指向的内容不能修改，
template <class T,class Ref>//定义两个模板参数，第二个Ref是为了控制*运算符重载函数的返回值，以达到传使用const迭代器，返回const T& 使用正常迭代器返回T&
struct _list_iterator
{
typedef listNode<T> Node;//将结点重命名
typedef _list_iterator<T, Ref> Self;//将迭代器重命名为Self
//为什么要重命名？因为加上模板后太长了，重命名一个简洁的名字
_list_iterator(Node* node)
:_node(node)
{}
Ref operator*()//将这里的返回值改成模板Ref，这样就可以通过模板参数来控制返回值不同了
{
return _node->val;
}
T* operator->()
{
return &_node->val;
}
Self& operator++()//重载++运算符//这里的Self就是迭代器_list_iterator<T, Ref>
{
_node = _node->next;
return *this;
}
Self& operator++(int)//后置++运算符//这里的Self就是迭代器_list_iterator<T, Ref>
{
Node* temp(this);
_node = _node->next;
return *temp;
}
bool operator!=(const Self& it)//这里的Self就是迭代器_list_iterator<T, Ref>
{
return _node != it._node;
}
Node* _node;//原生指针
};
3.三个模板参数
迭代器的第三个模板参数是什么呢？它又是干什么的呢？我们首先要模拟一个场景，一个类的成员变量是允许我们访问的(公有的)，那迭代器类似一个指针，指针就可以通过->来访问到指针指向的内容。那这样我们就可以通过迭代器的->访问到数据，而不是解引用。
T* operator->()
{
return &_node->val;
}
不过这里的箭头运算符重载就有点奇怪了，it->val 就是等于it.operator->().返回的是T* ,T*是怎么访问到val的呢？这里明显少了一个箭头，正确的写法应该是这样it->->val，但编译器觉得太挫了，将一个箭头省略了，编译器为了简洁好看，会自动忽略这个问题。
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << (it->val) << " ";
++it;
//因为it是自定义类型，自定义类型++就会去调用它的运算符重载
}
cout << endl;
第三个模板参数也是为了应对const迭代器而设计的，只不过这个模板参数控制的是箭头运算符重载函数的返回值类型，因为const迭代器使用->运算符后，返回的应该是const T类型，而正常迭代器使用->运算符后，返回的应该是T。
template <class T, class Ref,class Ptr>//三个模板参数，第二个控制解引用运算符重载函数的返回值类型
//第三个参数用来控制箭头运算符重载函数的返回值类型。这样就可以通过用户传什么类型的迭代器，模板自动生成什么样子的迭代器给他使用。
struct _list_iterator
{
typedef listNode<T> Node;//将结点重命名
typedef _list_iterator<T, Ref,Ptr> Self;//将迭代器重命名，不重命名的话，加上模板，太长了。
_list_iterator(Node* node)
:_node(node)
{}
Ref operator*()//重载*运算符因为原生指针中的解引用不符合list迭代要求
{
return _node->val;
}
Ptr operator->() //const对象使用 返回的应该是const T *， 正常对象使用返回的是T*
{
return &_node->val;
}
Self& operator++()//重载++运算符//Self就是迭代器_list_iterator<T, Ref,Ptr>
{
_node = _node->next;
return *this;
}
Self& operator++(int)//后置++运算符
{
Self* temp(this);
_node = _node->next;
return *temp;
}
Self& operator--()//重载--运算符
{
_node = _node->prev;
return *this;
}
Self& operator--(int)//后置--运算符
{
Self* temp(this);
_node = _node->prev;
return *temp;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
Node* _node;//原生指针
};
Ⅱ.反向迭代器实现
1.容器适配器模式
反向迭代是如何实现的呢？设计的原理就是适配器模式，将正向迭代器封装起来，然后通过函数重载来完成反向迭代器的一系列操作，这个模式牛逼之处就在于你传任何一个类型的正向迭代器，它都会给你适配出它的反向迭代器，就这么牛。反向迭代器的一些操作与正向迭代器相反，比如反向迭代器的++就是调用正向迭代器的–，反向迭代器的–就是调用正向迭代器的++。而解引用应该是一样的，都是访问具体的数据。
不过要注意的是反向迭代器的解引用操作与正向迭代不同，这是因为标准库里采用了一种镜像对称的方案。
什么意思呢？
正常来说，begin()是指向第一个位置的迭代器，end()是指向最后一个数据下一个位置的迭代器。
rbegin()指向的是最后一个数据位置的迭代器，rend()是指向第一个数据前面的位置的迭代器。
而镜像对称就是要让正迭代器和反迭代器的位置是对称的。
这样反向迭代器的rbegin()就可以直接用正向迭代器的end()初始化，rend()就可以直接用正向迭代器begin()初始化。而弄成这样的代价就是让解引用运算符重载函数来承担了，解引用的不是当前位置的数据，而是前一个位置上的数据的，这样就可以让反向迭代器正确的解引用到数据了。
template <class Iterator,class Ref,class Ptr>
struct ReserveIterator
{
typedef ReserveIterator<Iterator, Ref, Ptr> Self;
ReserveIterator(Iterator it)
:_it(it)
{}//用正向迭代器初始化
Ref operator*()//解引用，解的是前一个位置，保持对称
{
Iterator tmp = _it;
return *(--tmp);
//正向迭代器的模板类型是 class<T ,T& ,T*>
}
Self& operator++()
{
--_it;
return *this;
}
Self& operator--()
{
++_it;
return *this;
}
bool operator!=(Self it)
{
return _it != it._it;
}
Iterator _it;//底层封装一个正向迭代器
};
Ⅲ.list模拟实现
首先先搭出一个简易的list类模型，再一步一步完善。
1.定义结点
链表是由一个个的结点连接而成，所以第一步先构造出一个结点类。
这个结点包含前后指针和对应的数据。
template <class T>
struct listNode
{
listNode<T>* next;
listNode<T>* prev;
T val;
listNode(const T& val = T())
:next(nullptr)
, prev(nullptr)
, val(val)
{}
};
2.封装结点
接下来就是将结点封装到list类里面，用一个个结点来实现list的各个功能了。
我们实现的list是一个带头双向循环链表，所以第一步链表的构造就必须是双向循环的模式。
因为封装的结点是一个类模板，所以我们习惯给它用typedef重命名为一个简洁的名字。
3.构造/拷贝
template <class T>
class list//带头双向循环列表
{
public:
typedef listNode<T> Node;
list()//构造函数
{
_head = new Node;
//首先给头结点开辟空间
_head->prev = _head;
//让这个头结点的前后指针都指向自己，构造出一个循环链表
_head->next = _head;
sz = 0;
}
list(const list<T>& lt1)//拷贝构造--->深拷贝
{
_head = new Node;//首先还是构造出一个循环链表模型
_head->prev = _head;
_head->next = _head;
sz = 0;
for (auto e : lt1)//然后将要拷贝的对象的一个个数据全部尾插进来
{
push_back(e);//push_back这里还没有实现，在下面会实现知道原理即可
}
}
void swap( list<T>& lt1)
{
std::swap(_head, lt1._head);
std::swap(sz, lt1.sz);
}
list<T>& operator=( list<T><1)//赋值运算符重载---现代写法
{
swap(lt1);
return *this;
}
private:
Node* _head;//封装的是一个指向结点的指针
//封装的是指向头结点的指针
size_t sz;//大小
};
4.迭代器
迭代器我们上面已经实现完毕，这里就可以直接使用了。
typedef _list_iterator<T, T&,T*> iterator;//普通迭代器
typedef _list_iterator<T, const T&,const T*> const_iterator;//const迭代器
typedef ReserveIterator<iterator, T&, T*> reserve_iterator;//反向迭代器
typedef ReserveIterator<const_iterator, T&, T*> reserve_iterator;//反向const迭代器
reserve_iterator rbegin()//反向迭代器要保持镜像对称，用正向迭代器的end()构造rbegin()
{
return reserve_iterator(end());
}
reserve_iterator rend()//用正向迭代器的begin()构造rend()
{
return reserve_iterator(begin());
}
reserve_iterator rbegin()const
{
return reserve_iterator(end());
}
reserve_iterator rend()const
{
return reserve_iterator(begin());
}
iterator begin()
{
return _head->next;
//return _list_iterator(_head->next)
//单参数的构造支持隐式类型转化
}
iterator end()
{
return _head;
}
const_iterator begin()const
{
return _head->next;
//return _list_iterator(_head->next)
//单参数的构造支持隐式类型转化
}
const_iterator end()const
{
return _head;
}
5.插入/头尾插
iterator insert(iterator pos,const T& x)
{
//最好还是转化成结点的指针，这里访问迭代器不方便,这里就体现了为什么要用struct来定义迭代器让其成员共有
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;
sz++;
return newnode;//返回新插入结点的位置
}
void push_back(const T& x)
{
尾插首先需要找到尾
//Node* tail = _head->prev;
找到尾部后将新结点连接
//Node* newnode = new Node(x);
//tail->next = newnode;
//newnode->prev = tail;
//_head->prev = newnode;
//newnode->next = _head;
insert(end(), x);//可以直接复用insert
}
void push_front(const T& x)
{
insert(begin(),x);//可以直接复用insert
}
6.删除/头尾删
iterator 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;
sz--;
return next;
}
void pop_back()
{
erase(--end());//直接复用erase删除尾部位置
}
void pop_front()//直接复用erase删除第一个数据
{
erase(begin());
}
7.析构/清理
void clear()//清空数据，但不清哨兵位
{
iterator it = begin();
while (it != end())
{
it=erase(it);//删除完后会返回下一个位置的迭代器
}
sz = 0;
}
~list()//析构，全部清除
{
clear();
delete _head;
_head = nullptr;
}
Ⅳ.整代码
#pragma once
#include<iostream>
#include <stdio.h>
#include <assert.h>
#include "ReserveIterator.h"
using namespace std;
namespace tao
{
template <class T>
struct listNode
{
listNode<T>* next;
listNode<T>* prev;
T val;
listNode(const T& val = T())
:next(nullptr)
, prev(nullptr)
, val(val)
{}
};
template <class T, class Ref,class Ptr>
struct _list_iterator
{
typedef listNode<T> Node;
typedef _list_iterator<T, Ref,Ptr> Self;
_list_iterator(Node* node)
:_node(node)
{}
Ref operator*()//重载*运算符因为原生指针中的解引用不符合list迭代要求
{
return _node->val;
}
Ptr operator->() //const对象使用 返回的应该是const T *
{
return &_node->val;
}
Self& operator++()//重载++运算符
{
_node = _node->next;
return *this;
}
Self& operator++(int)//后置++运算符
{
Self* temp(this);
_node = _node->next;
return *temp;
}
Self& operator--()//重载--运算符
{
_node = _node->prev;
return *this;
}
Self& operator--(int)//后置--运算符
{
Self* temp(this);
_node = _node->prev;
return *temp;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
Node* _node;//原生指针
};
template <class Iterator,class Ref,class Ptr>
//反向迭代器
struct ReserveIterator
{
typedef ReserveIterator<Iterator, Ref, Ptr> Self;
ReserveIterator(Iterator it)
:_it(it)
{}//用正向迭代器初始化
Ref operator*()//解引用，解的是前一个位置，保持对称
{
Iterator tmp = _it;
return *(--tmp);
//正向迭代器的模板类型是 class<T ,T& ,T*>
}
Self& operator++()
{
--_it;
return *this;
}
Self& operator--()
{
++_it;
return *this;
}
bool operator!=(Self it)
{
return _it != it._it;
}
Iterator _it;//底层封装一个正向迭代器
};
//容器适配器模式 --->反向迭代器--给我正向迭代器我给你适配出反向迭代器，针对任何容器都可以，只要给我正向迭代器就可以适配出反向迭起
template <class T>
class list//带头双向循环列表
{
public:
typedef listNode<T> Node;
//typedef _list_iterator<T> iterator;//将自定义的迭代器名字统一命名为iterator
//typedef _list_iterator<T,T&> iterator;//普通迭代器
typedef _list_iterator<T, T&,T*> iterator;//普通迭代器
//typedef _list_iterator<T, const T&> const_iterator;//const迭代器
typedef _list_iterator<T, const T&,const T*> const_iterator;//const迭代器
//const迭代器如何设计？
//我们要求的const迭代器是：1.迭代器指向的内容不能被修改2.迭代器本身可以修改
//1.const T* iterator 2.T* const iterator
//typedef const _list_iterator<T> const_iterator;这种情况是第二种情况const修饰的是这个封装的迭代器，说明是这个迭代器不能被修改，而不是它指向的内容不能修改
//正确的做法是，解引用时访问到数据，返回时返回const T&类型的数据，这样返回回来的数据就无法再被修改
//有的人会选择拷贝一份封装的迭代器，然后其他都相同，就解引用运算符重载函数返回类型不同，普通迭代器，返回值是T&,const迭代器返回类型是constT&.
//但这样做实在太冗余了，大佬是再添加一个模板参数来控制这里的迭代器返回类型的。
typedef ReserveIterator<iterator, T&, T*> reserve_iterator;
reserve_iterator rbegin()
{
return reserve_iterator(end());
}
reserve_iterator rend()
{
return reserve_iterator(begin());
}
iterator begin()
{
return _head->next;
//return _list_iterator(_head->next)
//单参数的构造支持隐式类型转化
}
iterator end()
{
return _head;
}
const_iterator begin()const
{
return _head->next;
//return _list_iterator(_head->next)
//单参数的构造支持隐式类型转化
}
const_iterator end()const
{
return _head;
}
list()
{
_head = new Node;
_head->prev = _head;
_head->next = _head;
sz = 0;
}
list(const list<T>& lt1)
{
_head = new Node;
_head->prev = _head;
_head->next = _head;
sz = 0;
for (auto e : lt1)
{
push_back(e);
}
}
void swap( list<T>& lt1)
{
std::swap(_head, lt1._head);
std::swap(sz, lt1.sz);
}
list<T>& operator=( list<T><1)
{
swap(lt1);
return *this;
}
void push_front(const T& x)
{
insert(begin(),x);
}
void pop_front()
{
erase(begin());
}
void push_back(const T& x)
{
尾插首先需要找到尾
//Node* tail = _head->prev;
找到尾部后将新结点连接
//Node* newnode = new Node(x);
//tail->next = newnode;
//newnode->prev = tail;
//_head->prev = newnode;
//newnode->next = _head;
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
iterator insert(iterator pos,const T& x)
{
//最好还是转化成结点的指针，这里访问迭代器不方便,这里就体现了为什么要用struct来定义迭代器让其成员共有
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;
sz++;
return newnode;//返回新插入结点的位置
}
iterator 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;
sz--;
return next;
}
size_t size()
{
return sz;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()//清空数据，但不清哨兵位
{
iterator it = begin();
while (it != end())
{
it=erase(it);
}
sz = 0;
}
private:
Node* _head;//封装的是一个指向结点的指针
size_t sz;
};
};
