文章目录
- 全部的实现代码放在了文章末尾
- 准备工作
- 包含头文件
- 定义命名空间
- 类的成员变量
- 为什么节点类是用struct而不是class呢?
- 为什么要写get_head_node?
- 迭代器
- 迭代器在list类里的实例化和重命名
- 普通迭代器
- operator->()的作用是什么?
- const迭代器
- 反向迭代器
- 迭代器的获取
- 构造函数
- 默认构造
- 使用n个val构造
- 迭代器区间构造
- 解决迭代器区间构造 和 用n个val构造的冲突
- initializer_list构造
- 拷贝构造
- 析构函数
- swap
- 赋值运算符重载
- erase
- 删除pos迭代器指向的节点
- 为什么要返回next?
- 删除迭代器区间
- insert
- 在迭代器pos之前插入一个节点
- 为什么要返回newnode?
- 在迭代器pos之前插入一个迭代器区间的数据
- push_back
- push_front
- pop_front
- pop_back
- size
- empty
- back
- front
- assign
- resize
- clear
- 全部代码
全部的实现代码放在了文章末尾
准备工作
创建两个文件,一个头文件mylist.hpp
,一个源文件test.cpp
【因为模板的声明和定义不能
分处于不同的文件中,所以把成员函数的声明和定义放在了同一个文件mylist.hpp
中】
mylist.hpp:存放包含的头文件,命名空间的定义,成员函数和命名空间中的函数的定义
test.cpp:存放main函数,以及测试代码
包含头文件
-
iostream:用于输入输出
-
assert.h:用于使用报错函数assert
定义命名空间
在文件mylist.hpp
中定义上一个命名空间mylist
把list类和它的成员函数放进命名空间封装起来,防止与包含的头文件中的函数/变量重名的冲突问题
类的成员变量
参考了stl源码中的list的实现,stl中list的底层链表是双向带头循环链表
【可以看我这篇文章了解双向带头循环链表
的实现:链表的极致——带头双向循环链表】
成员变量只有一个,就是指向双向带头循环链表
的头节点的指针。
节点类:
为什么节点类是用struct而不是class呢?
因为节点类里面的成员变量在实现list的时候需要经常访问,所以需要节点类的成员变量是公有的【使用友元也可以,但是比较麻烦】
struct的默认访问权限就是公有,不用加访问限定符了,stl中实现的节点类也是struct
class的默认访问权限是私有的
list类:
为什么要写get_head_node?
因为插入节点之前必须
要有头节点
所以把创建初始头节点的操作写成了一个函数,用于
所有构造函数插入节点之前进行申请头节点
迭代器
因为list存储数据的方式是创建一个一个的节点存储数据
所以存储数据的空间不是
连续的,所以不能
直接用指针作为迭代器
因为指向一个节点的指针直接++,是不一定能
指向下一个节点的
所以要把迭代器实现成一个类
,这样才可以正确地支持++,- -,*等操作
迭代器在list类里的实例化和重命名
普通迭代器
template<class T, class R, class F>
struct Iterator
{把自己的类型重命名一下typedef Iterator<T, R, F> Self;成员变量的类型是 双向带头循环链表的节点类型listnode<T>* _n;Iterator(listnode<T>*l=nullptr) 构造函数{_n = l;}Self& operator++()前置++{++就是指向下一个节点_n = _n->_next;return *this;}Self operator++(int) 后置++{Self tmp =*this; 先记录一下++之前的值_n = _n->_next; 再++return tmp;}Self& operator--() 前置--{--就是指向上一个节点_n = _n->_prev;return *this;}Self operator--(int) 后置--{Self tmp = *this; 先记录一下--之前的值_n = _n->_prev; 再--return tmp;}R operator*()const{类比指针*就是获取 节点中存储的数据return _n->_data;}F operator->()const{返回 节点中 存储数据的成员变量的 地址return &(_n->_data);}bool operator!=(const Self&obj)const![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/f3d8c3b768b14a04a69d04a69c2d9829.png#pic_center){return _n != obj._n;}bool operator==(const Self& obj){return !(*this != obj);}
};
operator->()的作用是什么?
为了实现:
当节点中存储的数据是自定义类型的变量
时,可以直接使用 迭代器->访问自定义类型中的成员
【原来访问需要调用两次->,为了可读性,省略了一个->
】
例
const迭代器
const迭代器与普通迭代器的区别是什么?
区别就只有==不能
通过const迭代器改变节点中存储的数据==
转换一下就是:
不能
使用迭代器的operator*()
改变节点中存储的数据
,即把operator*()
的返回值改成const T&
就可以了不能
使用迭代器的operator->()
改变节点中存储的数据的成员
,即把operator->()
的返回值改成const T*
就可以了
所以const迭代器与普通迭代器的区别就只有两个函数的返回值类型不同,所以增加两个模板参数:R和F
普通迭代器
实例化时:R就是T&
,F就是T*
const迭代器
实例化:R就是const T&
,F就是const T*
反向迭代器
反向迭代器与普通迭代器的实现上
的区别就是:
普通
迭代器++是指向下一个
节点
反向
迭代器++是指向上一个
节点
普通
迭代器- -是指向上一个
节点
反向
迭代器- -是指向下一个
节点
template<class T, class R, class F>
struct Reverse_iterator
{把自己的类型重命名一下typedef Reverse_iterator<T, R, F> Self;成员变量的类型是 双向带头循环链表的节点类型listnode<T>* _n;Reverse_iterator(listnode<T>* l) 构造函数{_n = l;}Self& operator++(){反向迭代器++,是移动到 前 一个节点_n = _n->_prev;return *this;}Self operator++(int){Self tmp = *this;_n = _n->_prev;return tmp;}Self& operator--(){反向迭代器--,是移动到 后 一个节点_n = _n->_next;return *this;}Self operator--(int){Self tmp = *this;_n = _n->_next;return tmp;}R operator*()const{return _n->_data;}F operator->()const{return &(_n->_data) ;}bool operator!=(const Self& obj)const{return _n!=obj._n;}bool operator==(const Self& obj)const{return !(*this != obj);}
};
迭代器的获取
iterator begin()
{头节点的下一个节点 才是第一个节点return _head->_next;
}const修饰的对象只能调用const修饰的成员函数
const_iterator begin()const
{头节点的下一个节点 才是第一个节点return _head->_next;
}iterator end()
{最后一个节点的下一个节点是 头节点因为是循环链表return _head;
}const修饰的对象只能调用const修饰的成员函数
const_iterator end()const
{return _head;
}reverse_iterator rend()
{反向迭代器的rend返回的是第一个节点的 前一个节点return _head;
}const修饰的对象只能调用const修饰的成员函数
const_reverse_iterator rend()const
{return _head;
}
reverse_iterator rbegin()
{反向迭代器的rbegin()返回的是 最后一个节点最后一个节点是 头节点的前一个因为是循环链表return _head->_prev;
}const_reverse_iterator rbegin()const
{return _head->_prev;
}
构造函数
默认构造
使用n个val构造
迭代器区间构造
解决迭代器区间构造 和 用n个val构造的冲突
当重载了迭代器区间构造
和使用n个val构造
的时候
如果传入的两个参数都是int类型
的话就会报错
为什么?
因为在模板函数构成重载时,编译器会调用更合适的那一个
什么叫更合适?
就是不会
类型转
如果传入的两个参数都是int类型
,那么调用的应该是使用n个值构造
,因为没有int类型的迭代器
但是使用n个值构造
的第一个参数是size_t , int传进去要隐式类型转换
而调用迭代器区间构造
,两个int的实参传进去,就会直接把InputIterator
推导成int,不会
发生类型转换,所以编译器会调用迭代器区间构造
解决方法:
再重载一个使用n个值构造
的函数,把第一个参数改成int,这样根据模板偏特化
,就会在都不类型转换时优先调用第一个参数特化成int的那个构造函数
initializer_list构造
写了这个构造函数,就可以支持直接使用{}初始化了
例
initializer_list
是iostream库里面的自定义类型,它可以直接接收{ }里面的值 进行初始化
,而且有迭代器
所以可以直接使用迭代器循环+尾插进行对list
的构造
拷贝构造
析构函数
swap
只需要交两个list对象的头指针中存储的地址
就可以了
因为两个list对象都有头结点,交换了头指针中存储的地址
,就相当于把这两个对象的头指针的指向交换了,
而链表的所有节点都是由头节点出发去找到的
void swap(list& obj)
{调用库里面的swap,交换头指针std::swap(_head, obj._head);
}
赋值运算符重载
list& operator= (list obj)
{swap(obj);return *this;
}
为什么上面的两句代码就可以完成深拷贝呢?
这是因为:
使用了传值传参,会在传参之前调用拷贝构造,再把拷贝构造出的临时对象作为参数传递进去
赋值运算符的左操作数,*this再与传入的临时对象obj交换,就直接完成了拷贝
在函数结束之后,存储在栈区的obj再函数结束之后,obj生命周期结束
obj调用析构函数,把指向的从*this那里交换来的不需要的空间销毁
erase
删除pos迭代器指向的节点
为什么要返回next?
因为使用了erase之后的迭代器会失效,需要提供更新的方法
为什么使用了erase之后的迭代器会失效?
因为pos指向的节点erase之后,节点被释放了
stl库里面规定erase的返回值是指向删除数据的下一个数据的迭代器
,下一个数据就是next指向的数据,所以返回next【没有接收返回值的迭代器,在检测较严格的编译器中,不管指向的位置是否正确,都会禁止使用,使用了就报错
】
删除迭代器区间
insert
在迭代器pos之前插入一个节点
为什么要返回newnode?
list的迭代器
pos在使用完insert之后其实是不会失效
的
但是为了与其他容器的nsert的返回值进行统一,所以也返回了指向新插入的节点的迭代器
在迭代器pos之前插入一个迭代器区间的数据
push_back
复用insert即可
void push_back(const T&val)
{insert(end(), val);
}
push_front
复用insert即可
void push_front(const T& val)
{insert(begin(), val);
}
pop_front
复用erese即可
void pop_front()
{erase(begin());
}
pop_back
复用erese即可
void pop_back()
{erase(--end());
}
size
empty
back
front
assign
resize
clear
复用erase
全部代码
#include<iostream>
#include<assert.h>using namespace std;namespace mylist
{template<class T>struct listnode//双向带头循环链表的节点类{T _data;//节点存储的数据listnode* _next;//指向下一个节点的指针listnode* _prev;//指向前一个节点的指针};template<class T, class R, class F>struct Iterator{//把自己的类型重命名一下typedef Iterator<T, R, F> Self;//成员变量的类型是 双向带头循环链表的节点类型listnode<T>* _n;Iterator(listnode<T>*l=nullptr)//构造函数{_n = l;}Self& operator++()//前置++{//++就是指向下一个节点_n = _n->_next;return *this;}Self operator++(int)//后置++{Self tmp =*this;//先记录一下++之前的值_n = _n->_next;//再++return tmp;}Self& operator--()//前置--{//--就是指向上一个节点_n = _n->_prev;return *this;}Self operator--(int)//后置--{Self tmp = *this;//先记录一下--之前的值_n = _n->_prev;//再--return tmp;}R operator*()const{//类比指针//*就是获取 节点中存储的数据return _n->_data;}F operator->()const{//返回 节点中 存储数据的成员变量的 地址return &(_n->_data);}bool operator!=(const Self&obj)const{return _n != obj._n;}bool operator==(const Self& obj){return !(*this != obj);}};template<class T, class R, class F>struct Reverse_iterator{//把自己的类型重命名一下typedef Reverse_iterator<T, R, F> Self;//成员变量的类型是 双向带头循环链表的节点类型listnode<T>* _n;Reverse_iterator(listnode<T>* l)//构造函数{_n = l;}Self& operator++(){//反向迭代器++,是移动到 前 一个节点_n = _n->_prev;return *this;}Self operator++(int){Self tmp = *this;_n = _n->_prev;return tmp;}Self& operator--(){//反向迭代器--,是移动到 后 一个节点_n = _n->_next;return *this;}Self operator--(int){Self tmp = *this;_n = _n->_next;return tmp;}R operator*()const{return _n->_data;}F operator->()const{return &(_n->_data) ;}bool operator!=(const Self& obj)const{return _n!=obj._n;}bool operator==(const Self& obj)const{return !(*this != obj);}};template<class T>class list{//把双向带头循环链表的节点类型重命名成nodetypedef listnode<T> node;private:node* _head;//唯一的成员变量//获取初始头结点node* get_head_node(){//申请一个节点大小的空间node* tmp = new node;//最开始的头节点的prev和next都指向自己tmp->_next = tmp;tmp->_prev = tmp;return tmp;}public:typedef Iterator<T, T&, T*> iterator;//普通迭代器typedef Iterator<T, const T&, const T*> const_iterator;//const迭代器typedef Reverse_iterator<T, T&, T*> reverse_iterator;//反向迭代器typedef Reverse_iterator<T, const T&, const T*> const_reverse_iterator;//const反向迭代器list(){//获取头结点//为之后的插入操作做准备_head=get_head_node();}list(size_t n, const T& val=T()){//必须先获取头节点,才能进行插入数据_head = get_head_node();for (int i = 0; i < n; i++){push_back(val);//尾插n次}}template <class InputIterator>list(InputIterator first, InputIterator last){//必须先获取头节点,才能进行插入数据_head = get_head_node();while (first != last){//把解引用之后的值,一个一个尾插进去push_back(*first);first++;}}list(int n, const T& val = T()){//必须先获取头节点,才能进行插入数据_head = get_head_node();for (int i = 0; i < n; i++){push_back(val);}}list(initializer_list<T> il){//必须先获取头节点,才能进行插入数据_head = get_head_node();auto it = il.begin();while (it != il.end()){//把解引用之后的值,一个一个尾插进去push_back(*it);it++;}}list(const list& obj){//必须先获取头节点,才能进行插入数据_head = get_head_node();//使用const迭代器接收 const修饰的对象的迭代器const_iterator it = obj.begin();while (it != obj.end()){//把解引用之后的获得的值,一个一个尾插进去push_back(*it);it++;}}~list(){//先把list里面除了头结点//以外的节点全部删除clear();//再把头结点申请的空间释放delete _head;_head = nullptr;}list& operator= (list obj){swap(obj);return *this;}void swap(list& obj){//调用库里面的swap,交换头指针std::swap(_head, obj._head);}iterator begin(){//头节点的下一个节点 才是第一个节点return _head->_next;}//const修饰的对象只能调用const修饰的成员函数const_iterator begin()const{//头节点的下一个节点 才是第一个节点return _head->_next;}iterator end(){//最后一个节点的下一个节点是 头节点//因为是循环链表return _head;}//const修饰的对象只能调用const修饰的成员函数const_iterator end()const{return _head;}reverse_iterator rend(){//反向迭代器的rend返回的是第一个节点的 前一个节点return _head;}//const修饰的对象只能调用const修饰的成员函数const_reverse_iterator rend()const{return _head;}reverse_iterator rbegin(){//反向迭代器的rbegin()返回的是 最后一个节点//最后一个节点是 头节点的前一个//因为是循环链表return _head->_prev;}const_reverse_iterator rbegin()const{return _head->_prev;}void push_back(const T&val){/*node* tail = _head->_prev;node* newnode = new node;newnode->_data = val;newnode->_next = _head;newnode->_prev = tail;tail->_next = newnode;_head->_prev = newnode;*/insert(end(), val);}iterator erase(iterator pos){//不能 把 头节点 给删了assert(pos!=end());//记录pos的前一个节点(prev) // 和后一个节点(next)node* prev = pos._n->_prev;node* next = pos._n->_next;//让prev的下一个节点变成nextprev->_next = next;//让prev的上一个节点变成nextnext->_prev = prev;//释放pos指向的节点delete pos._n;//返回被删除的节点的下一个节点//用于更新迭代器return next;}iterator erase(iterator first, iterator last){iterator it = first;while (it != last){//删除it指向的节点//删除后让it接收返回值,进行更新it = erase(it);}//返回被删除的 最后一个节点 的下一个节点//用于更新迭代器return last;}bool empty() const{//size==0就 是空 返回true//size!=0就 不是空 返回falsereturn size() ==0 ;}size_t size()const {//用count记录节点个数size_t count = 0;//使用const迭代器接收 const修饰的对象的迭代器const_iterator it = begin();//遍历链表while (it != end()){count++;++it;}return count;}T& back(){//list不能为空,为空就报错assert(!empty());//end()返回的迭代器指向 头结点//头结点的上一个节点就是,最后一个节点//因为是循环链表return *(--end());}//const修饰的成员,只能调用const修饰的成员函数const T& back() const{assert(!empty());return *(--end());}T& front(){//list不能为空,为空就报错assert(!empty());//begin()返回的迭代器 就指向第一个节点return *begin();}//const修饰的成员,只能调用const修饰的成员函数const T& front()const{assert(!empty());return *begin();}template <class InputIterator>void assign(InputIterator first, InputIterator last){//先把数据现有的节点(除了头结点)都删除clear();//再循环把数据一个一个尾插进去while (first != last){//尾插push_back(*first);first++;}}void assign(size_t n, const T& val){clear();for (int i = 0; i < n; i++){push_back(val);}}void assign(int n, const T& val){clear();for (int i = 0; i < n; i++){push_back(val);}}iterator insert(iterator pos, const T& val){//记录指向 pos 前一个节点的指针node* prev = pos._n->_prev;//申请新节点的空间node* newnode = new node;//存储数据newnode->_data = val;newnode->_next = pos._n;newnode->_prev = prev;prev->_next = newnode;pos._n->_prev = newnode;//返回指向新插入的节点的迭代器//用于更新迭代器return newnode;}template <class InputIterator>void insert(iterator pos, InputIterator first, InputIterator last){while (first!=last){//循环插入即可//因为list的迭代器使用完insert之后 不会失效//所以不用接收返回值 也可以insert(pos,*first);first++;}}void push_front(const T& val){insert(begin(), val);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}void resize(size_t n, const T& val = T()){//获取一下size,加快后续比较效率//因为获取size()的时间复杂度为 O(N)size_t size = this->size();if (n > size){//缺失的数据用val填上//填到size()==n为止while (size < n){push_back(val);++size;}}else {//把多出来的数据(节点)删除//删除到n==size()为止while (n < size){pop_back();n++;}}}void clear(){//[begin(),end())之间的数据//就是所有的有效数据(节点)//复用erase删除即可erase(begin(), end());}};
}