list的模拟真的很震撼,第一次学习时给我幼小的心灵留下了极大地冲击
接下来我们一起看看list模拟究竟是怎样一回事
目录
- 节点的封装:
- list类的实现:
- 私有成员变量:
- 构造函数:
- push_back && pop_back:
- 迭代器类的实现:
- begin && end(不可被const对象调用):
- begin && end(可被const对象调用):
- 继续list类的实现:
- insert && erase:
- 带参构造函数:
- 迭代器区间构造:
- 拷贝构造:
- 赋值运算符重载:
- 析构函数:
节点的封装:
我们在之前没用CPP实现list时,是定义了一个struct node的结构体
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;
那我们现在当然也需要定义一个结构体
template<class T>struct list_node{T _val;list_node<T>* _prev;list_node<T>* _next;list_node(const T& data = T()){_val = data;_prev = _next = nullptr;}};
但是要写一个默认构造函数,因为未来我们会new
节点,就像我们在C阶段malloc
的一样。
那么为什么要使用sruct
而不是class
呢,因为我们希望这个节点结构体
有了他的地址可以直接访问成员变量,而设置为class
时除非进行public
否则不是很方便。
list类的实现:
私有成员变量:
由于我们会使用模版,因此在写类型是比较不方便,于是可以define一下typedef list_node<T> node;
private:node* _head;
注意:我们的stl库中的list是有哨兵位的,故私有成员设为_head。
构造函数:
list(){empty_init();}
为什么要先写个空初始化呢?因为后边的成员函数有一些也需要进行初始化,因此写成一个函数进行复用。
void empty_init(){_head = new node();_head->_next = _head;_head->_prev = _head;}
push_back && pop_back:
我们先搭一个架子出来,随后在进行细节的填补。
push_back():
void push_back(const T& val){node* newnode = new node(val);node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}
pop_back:
void pop_back(){node* prev = (it._node)->_prev;node* next = (it._node)->_next;delete it._node;prev->_next = next;next->_prev = prev;}
有了节点之后我们怎样进行访问?
没错就是使用迭代器。
迭代器类的实现:
我们的list的迭代器为什么要封装成一个类?
因为在vector那种底层虚拟地址是连续的,当我们有一个指定位置的指针,直接对指针进行++
、--
、*
…都是没问题的,因为我们的迭代器本质就是一个模仿指针行为的一个东西
但是我们的链表节点
的底层并不是连续的,是一个一个new
出来的,并不能保证底层虚拟地址的连续性,所以要对链表节点的指针
进行封装
,进行重载操作符进而可以模拟指针的行为!!
template<class T>struct list_iterator{typedef list_node<T> node;typedef list_iterator<T> self;node* _node;list_iterator(node* Node){_node = Node;}self& operator++(){_node = _node->_next;return *this;}self operator--(int){self tmp = *this;_node = _node->_prev;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator++(int){self tmp = *this;_node = _node->_next;return tmp;}bool operator!=(self it){return it._node != _node;}T& operator*(){return _node->_val;}};
对需要进行相关运算符重载的都进行一遍。
如此我们一个最简单的list框架就已经搭建成功了。
不要忘记在list类中进行将list_iterator
typedef为iterator
,因为这样我们的代码才具有跨平台性。
同时要在list类中写上begin与end这两个获取迭代器的函数。
begin && end(不可被const对象调用):
iterator begin(){return _head->_next;}iterator end(){return _head;}
我们为啥可以这么写?_head的类型不是node*
?原生的类型显示为list_node<T>*
,可是迭代器的类型是list_iterator ,完全不一样啊,这是因为我们C++支持单参数的构造函数隐式类型转换,直接对_head这个指针利用iterator的构造函数构造成迭代器
但是我们这个list目前对于const对象是很难遍历的,所以当然要实现const迭代器。
我们有两种方式,第一种是将普通迭代器的复制一份改为const迭代器,对*
这个操作符重载返回const对象,这样就不怕const对象被修改了。
但是这样的代码是在是冗余,不要忘记我们还有模版的存在!
我们如果将迭代器的模版参数多设计一个T的引用
,在list类中将这个迭代器类进行typedef
!
typedef list_iterator<T, T&> iterator;
typedef list_iterator<T, const T&> const_iterator;
那么我们这样就可以很好解决当前代码重复度高,比较冗余的缺点。
template<class T, class Ref>//多传递的模版参数struct list_iterator{typedef list_node<T> node;typedef list_iterator<T, Ref> self;node* _node;list_iterator(node* Node){_node = Node;}self& operator++(){_node = _node->_next;return *this;}self operator--(int){self tmp = *this;_node = _node->_prev;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator++(int){self tmp = *this;_node = _node->_next;return tmp;}bool operator!=(self it){return it._node != _node;}Ref operator*(){return _node->_val;}};
这样就可以根据是否为const对象而生成不同的迭代器类了!
begin && end(可被const对象调用):
iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}
继续list类的实现:
有了迭代器我们就可以写insert,erase等等函数,进而对push_back/front…等等函数的复用:
insert && erase:
void insert(iterator pos, const T& val){node* newnode = new node(val);node* prev = pos._node->_prev;node* cur = pos._node;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;}iterator erase(iterator pos){node* prev = pos._node->_prev;node* next = pos._node->_next;delete pos._node;prev->_next = next;next->_prev = prev;return next;}
带参构造函数:
list(int n, const T& val = T()){empty_init();while (n--){push_back(val);}}
直接复用push_back
迭代器区间构造:
template <class Iterator>list(Iterator first, Iterator last){empty_init();while (first != last){push_back(*first);first++;}}
拷贝构造:
list(const list<T>& lt){empty_init();list<T>::const_iterator it = lt.begin();while (it != lt.end()){push_back(*it);it++;}}
赋值运算符重载:
void swap(list<T> lt){std::swap(_head, lt._head);}list<T>& operator=(list<T> lt){swap(lt);return *this;}
析构函数:
~list(){clear();delete _head;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}
由此list类就模拟完毕,如果有不明白的地方可以尽管来找博主