1. 前言
本篇文章立足于上一篇文章:
请先阅读完上一篇文章后再阅读这篇文章!
本章重点:
本章着重讲解list的模拟实现
list模拟实现的重难点是迭代器的实现
和const迭代器的实现
最后总结list和vector的区间对比
注:我将在文章末尾分享list模式实现全部代码
2. list类的大致框架与结构
由于list类是一个带头双向循环链表
所以在写list类之前,应该先定义节点类
在真正的list类中会复用此类:
template<class T> class list_node { public: T _data; list_node<T>* _next; list_node<T>* _prev; list_node(const T& x = T()) :_data(x) , _next(nullptr) , _prev(nullptr) {} };
这个类和用C语言实现链表的定义很像
节点中存储一个T模板类型的值和
上一个节点的地址和下一个节点的地址
在List类中,由于链表都是些链接关系
所以List类中的成员变量只需要定义一个
那就是头节点head,知道head的链接关系
就知道list类对象中存放的内容!
List类基本框架以及无参构造:
template<class T> class List { typedef list_node<T> node; public: List() { _head = new node; _head->_next=_head; _head->_prev=_head; } private: node* _head; }
给头节点head开辟一份空间后
头节点的指向最开始都是指向自身:
3. List类的构造,析构,拷贝构造
无参构造函数以及写过了,我们模仿
STL库中的带参构造写一个用迭代器
区间初始化的构造函数:
void emptyinit()//创建并初始化哨兵位的头节点,方便给构造和拷贝构造复用 { _head = new node; _head->_next = _head; _head->_prev = _head; } template<class InputTterator>//有参的构造 List(InputTterator first, InputTterator last) { emptyinit(); while (first != last) { push_back(*first); first++; } }
注:push_back先用着,后面会实现
在实现析构函数前,我们可以先实现clear函数
因为析构函数实际上可以复用clear函数:
void clear()//清空数据,除了头节点 { iterator it = begin(); while (it != end()) { it = erase(it);//erase会返回下一个节点的迭代器 } } ~List()//_head也要被删除掉 { clear(); delete _head; _head = nullptr; }
注:迭代器相关的函数先用着,后面会实现
拷贝构造函数的实现:(用lt1拷贝lt2)
//lt2(lt1) List(const List<T>& lt)//完成深拷贝 { emptyinit(); List<T> tmp(lt.begin(), lt.end());//用lt1的迭代器区间去构造一下tmp ::swap(_head, tmp._head); }
此拷贝构造函数精妙的地方有两个:
- 它先定义一个临时变量tmp来接受
lt1的所有值,然后再将临时变量tmp
的head和lt2的head交换,这样一来
lt2中的链接关系就和lt1相同了
并且tmp变量是构造函数初始化的
它是深拷贝,所以lt2对于lt1也是深拷贝- tmp是临时变量,除了作用域会销毁
也就是除了此拷贝构造函数后会销毁
销毁时会调用析构函数,然而lt2的head
以及和tmp的head交换了,所以tmp销毁
时实际上是在帮原先的lt2销毁内存!
4. list的迭代器的实现
由于list的迭代器底层不是简单的指针
所以我们不能像实现vector一样直接在
list类定义迭代器和使用迭代器相关函数
要重新写一个迭代器类来实现功能:
template<class T> struct __list_iterator { typedef list_node<T> node; typedef __list_iterator iterator; node* _node; }
这样重新写一个类的作用是将迭代器的
++,- -等操作在此类中实现,因为list中的
++实际上是node=node->next,然而list
中的==符号判断的是node1->data和
node2->data相不相同,如果迭代器和
list写在一个类中,实现此等操作会很麻烦
4.1 list迭代器的若干函数解析
1. 构造函数:
__list_iterator(node* nnode) :_node(nnode) {}
由于初始化列表会调用node的构造函数
所以list迭代器的构造函数可写可不写
2. 前置++/- -和后置++/- -
iterator& operator++()//前置++ { _node = _node->_next; return *this; } iterator& operator++(int)//后置++ { iterator tmp = *this; _node = _node->_next; return tmp; } iterator& operator--()//前置-- { _node = _node->_prev; return *this; } iterator& operator--(int)//后置-- { iterator tmp = *this; _node = _node->_prev; return tmp; }
3. 等于和不等于函数解析:
bool operator!=(const iterator& it)const { return _node != it._node; } bool operator==(const iterator& it)const { return _node == it._node; }
4.2 list迭代器的解引用和箭头操作
迭代器的使用就像指针一样,所以
解引用后应该直接得到节点的数据!
由于结构体变量除了可以用解引用
以外还能使用->,所以需要写两个函数:
//可读可写 T& operator*() { return _node->_data; } //可读可写 T* operator->() { return &(operator*()); }
解引用操作的应该没有问题
重点难点在这个箭头->函数
可以将这个函数一步一步拆分:
return &(_node->_data);
相当于返回了一个结构体指针
然而我们想要的并不是一个结构体指针
而是确切的值,蛋这样写编译器并不会报错
这是因为编译器为了代码的可读性
帮我们省略了一个箭头->
所以只需要一个箭头->就能访问数据!
注:省略的箭头可以将返回的结构体指针解引用
然而此结构体指针解引用后其实就是data
4.3 迭代器类映射到list类
当我们实现完迭代器类后
就可以在list类中复用迭代器类了:
template<class T> class List { typedef list_node<T> node; typedef __list_iterator<T> iterator; private: node* _head;
有了迭代器类的加持后,list类中的
其他函数如begin和end就是歪瓜裂枣了
iterator begin() { //iterator tmp(_head->_next); //return tmp; return iterator(_head->_next);//使用了匿名对象 } iterator end() { //iterator tmp(_head); //return tmp; return iterator(_head); }
注:其他关于迭代器的函数会在最后放出
5. const迭代器实现深度剖析
既然list中的迭代器和vector中的不同
那么const迭代器的实现当然也不同
首先我们要明白一点,list的普通迭代器
和const迭代器的区别到底是什么?
const对象的剖析:
const迭代器是为const对象准备的
然而const对象的特征就是不能修改
那么什么操作会让对象的值变化呢?
答案很明显是解引用操作和箭头->
begin和end函数返回后也有可能被修改注:返回值是T&和T*的函数都要注意
解决方案剖析:
大家可能第一时间想到再重新写一个
const迭代器的类,里面的实现和普通
迭代器都一样,唯一不同的是解引用函数
和箭头->函数的返回值是const对象
5.1 const迭代器实现详解
首先,不用再重新写一个类来实现
接下来的方案不要问为什么
不要问怎么想到的,是天才想到的:
在普通迭代器类中使用三个模板参数
为什么要这样做?
通过观察可以发现,只有两个函数不同
并且这两个函数的类型只有T&和T*
那么就
专门为这两个类型设置两个模板只有在编写这两个函数时用到这两个模板
其余函数还是正常的使用T来当类型
话不多说,上代码
template<class T, class Ref, class Ptr> struct __list_iterator//迭代器不需要析函数 { typedef list_node<T> node; typedef __list_iterator iterator; node* _node; }
模板中的Ref代表的是引用&
模板中的Ptr代表的是指针 *
现在重新来实现一下这两个函数:
//按模板参数来 Ref operator*() { return _node->_data; } Ptr operator->() { return &(operator*()); }
现在你脑子肯定是一篇空白
但是精髓的地方马上就来了,请耐住性子
5.2 const迭代器和list类的复用
当list类复用了此迭代器类后:
template<class T> class List { typedef list_node<T> node; typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; private: node* _head; }
这样写出来后,普通迭代器和const迭代器
就被完美的区别开了,当传入const对象时
系统会把模板参数实例化为const T&
当传入的是普通对象时,系统会把模板参数
实例化为普通的T,T&和T*
begin和end函数的复写:
const_iterator begin()const { return const_iterator(_head->_next); } iterator begin() { return iterator(_head->_next);//使用了匿名对象 } const_iterator end()const { return const_iterator(_head); } iterator end() { return iterator(_head); }
5.3 const迭代器使用实例
现在,我们通过一个实例来感受这一过程:
void print_list(const list<int>& lt) { auto it = lt.begin(); while (it != lt.end()) { //*it = 10; cout << *it << " "; ++it; } cout << endl; }
此时的lt变量是const变量,实例化类时
会实例化为<T,const T&,const T*>
然后回退到迭代器类时,迭代器类的
模板参数Ref就对应:const T&
模板参数Ptr就对应:const T*
此时解引用函数的返回值就是const T&
如果你写:*it=10;那么就会报错!
6. list和vector的对比
详情请看下表:
| 目录 | vector | list |
| 底层结构 | 顺序表,空间连续 | 带头双向循环链表 |
| 随机访问 | 支持随机访问,访问效率为O(1) | 不支持随机访问,访问效率为O(N) |
| 插入和删除 | 任一位置插入删除效率低,还需扩容 | 任一位置插入效率高 |
| 空间利用率 | 空间,缓存利用率高 | 不连续空间,容易造成内存碎片 |
| 迭代器 | 原生态的指针 | 对原生指针的封装 |
| 迭代器失效 | 插入和删除都会导致 | 只有删除会导致 |
| 使用场景 | 高效存储，支持随机访问 | 有大量插入和删除操作，不关心随机访问 |
注:这个表格不能死记硬背,要理解记忆
7. 总结以及代码分享
总的来说,list的底层实现较于vector
来说要复杂一点,这其中的底层原因
就是list的迭代器还需要一层封装,而
vector的迭代器不需要额外封装
C++的强大就在于把复杂的底层
全部封装起来了,而表面的使用上
list和vector并无太大区别,这就是
C++封装的魅力!
list模拟实现全部代码分享:
注:全部代码中包含反向迭代器
目前阶段可以跳过不管
? 下期预告:栈和队列 ?
