热门标签
热门文章
- 1【PX4仿真】使用PX4+Gazebo+MAVROS+ROS进行无人机仿真中提高IMU消息频率的方法
- 243.Python从入门到精通—创建数据库 创建一个数据库 判断数据库是否已存在 创建集合 增、删、改、查等操作
- 3ITMS-90683: Missing Purpose String in Info.plist的解决方法
- 4python如何调用另一个.py文件中的类和函数_python怎么调用另外一个python文件里的函数
- 507oracle之多表（关联）查询、表连接（内外全）、子查询、TOP-N分析法_oracle子查询的执行顺序总是先于外部查询
- 6【CSS基础】10.过度动画transition和动画animation
- 7汽车车灯用肖特基二极管，选什么型号好？
- 8基于YOLOv8深度学习的安全帽目标检测系统【python源码+Pyqt5界面+数据集+训练代码】目标检测、深度学习实战_基于机器学习的安全帽佩戴自动识别系统
- 9codegeex和通义灵码辅助编程——以及通义灵码无法登陆的bug解决_codegeex和通义灵码对比
- 10Android应用启动过程浅析_android app启动过程
当前位置: article > 正文
【C++】STL---list的模拟实现_仿照stl模板库中的list容器,制作一个属于自己的基本链表容器,实现以下功能
作者：小蓝xlanll | 2024-04-15 07:39:53
赞
踩
仿照stl模板库中的list容器,制作一个属于自己的基本链表容器,实现以下功能
前言
上次模拟实现了一个vector容器，那么我们这次来实现一个list(链表)容器，链表在实际的开发中并不常见。但是也是一种很重要的数据结构，下面给大家介绍一下链表(list) 和 vector(顺序表)的区别。
一、list和vector的区别
list 和 vector 一样，是一个存储容器。不同的是vector在内存中是连续存储的，而list每个节点所在的内存区域是不连续的。那我们用vector还是用list呢？vector和list的优劣势有以下几点。
vector优点:
1.支持下标随机访问。
2.cpu命中缓存率高
vector缺点:
1.存在一定的程度的空间浪费。
2.扩容代价大。
3.中间和前面元素的删除与插入，代价大。
list优点:
1.按需申请空间，不存在空间浪费。
2.任意位置的插入与删除，时间复杂度都是O(1)。
list缺点:
1.不支持随机访问，以至于查找，排序等操作代价太大。
2.cpu命中缓存率低。
综上所述，我们可以看到list和vector是完全互补的两个容器。vector的优点就是list的缺点，vector的缺点就是list的优点。所以，如果查找多，用vector，如果增删操作多，用list，了解了list之后，接下来我们就可以模拟实现一下它。
二、节点的定义
我们要实现的是一个带头双向循环的链表。
所以节点有三个参数，一个的prve指向前一个节点，一个是date存储数据，还有一个是next指向下一个节点。当然，我们还需要有个构造函数，来给date赋值。
代码:
//节点结构体 template<class T> struct ListNode { typedef ListNode<T> Node; Node* _prve; Node* _next; T _data; //构造函数 ListNode():_prve(nullptr),_next(nullptr),_data(0){} ListNode(const T& val) :_prve(nullptr) ,_next(nullptr) { _data = val; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
三、list类定义
list定义很简单，因为要存任意类型的参数，我们用模板即可。
而私有成员只有一个，那就是头节点。
代码:
template<class T> class list { typedef ListNode<T> Node; public: //构造函数 list() { //开辟空间 _head = new Node; //自己指向自己 _head->_prve = _head; _head->_next = _head; } private: Node* _head; };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
四、push_back函数
push_back函数也就是尾部插入，我们可以通过头节点的prev找到最后一个节点，随后链接即可。
代码:
void push_back(const T& val)
{
//创建一个新节点
Node* newNode = new Node(val);
//找到尾节点
Node* tail = _head->_prve;
//尾节点和创建的节点链接
tail->_next = newNode;
newNode->_prve = tail;
_head->_prve = newNode;
newNode->_next = _head;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
五、push_front函数
就是头插，很简单，直接保存节点的下一个节点，然后创建一个新节点。把这俩节点链接起来。
代码:
void push_front(const T& val)
{
//创建一个新节点
Node* newNode = new Node(val);
//保存头节点的下一个节点
Node* next = _head->_next;
//链接
_head->_next = newNode;
newNode->_prve = _head;
next->_prve = newNode;
newNode->_next = next;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
六、迭代器
因为是链表容器，链表在内存中的存储不是连续的，所以迭代器+1是无法找到下一个节点的。所以我们要单独弄一个结构体来封装list的迭代器。
代码:
template<class T>
struct_list_iterator
{
Node* _it;
typedef ListNode<T> Node;
// 构造函数
_list_iterator(Node* node)
:_it(node)
{
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
七、begin和end函数
我们的链表是带头的，也就是头节点是不存放有效值的，所以头节点的_next指向的节点就是链表的第一个节点。而最后一个节点的下一个节点又恰好是头节点。所以迭代器开始位置是在头节点的下一个位置，结束位置是头节点。不过再此之前，我们需要把迭代器typedef一下。
代码:
//迭代器 typedef _list_iterator<T> iterator; typedef _list_iterator<const T> const_iterator; //迭代器获取 iterator begin() { return iterator(_head->_next); } const_iterator begin()const { return const_iterator(_head->_next); } iterator end() { return iterator(_head); } const_iterator end()const { return const_iterator(_head); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
八、迭代器区间初始化
有了迭代器之后，我们可以用迭代器区间来进行初始化。
代码:
template<class InputIterator>
list(InputIterator first, InputIterator last)
{
//创建头节点
_head = new Node();
_head->_prve = _head;
_head->_next = _head;
while (first != last)
{
pusb_back(*first);
++first;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
九、迭代器的操作符重载
接下来我们来完善迭代器的一些操作。
操作符++重载
迭代器++，就是指向下一个元素。
typedef _list_iterator<T> self;
//前置++重载
self& operator++()
{
_it = _it->_next;
return *this;
}
//后置++重载
self operator++(int)
{
self tmp(*this);
_it = _it->_next;
return tmp;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
操作符- -重载
和++类似，不过- -是到前一个节点。
//前置--重载
self& operator--()
{
_it = _it->_prve;
return *this;
}
//后置--重载
self operator--(int)
{
self tmp(*this);
_it = _it->_prve;
return tmp;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
操作符！=重载
直接比较地址即可。
// !=重载
bool operator!=(const self& it)const
{
return _it != it._it;
}
- 1
- 2
- 3
- 4
- 5
操作符==重载
直接比较地址即可。
// ==重载
bool operator==(const self& it)const
{
return _it == it._it;
}
- 1
- 2
- 3
- 4
- 5
操作符*重载
*就是解引用，所以我们返回节点的值即可。
T& operator*()
{
return _it->_data;
}
- 1
- 2
- 3
- 4
但是这个代码有个缺陷，那就是当容器是const的时候，依旧可以解引用修改它的值，这也就意味着const迭代器根本就不具有常属性，要想const迭代具备常属性，我们必须增加模板参数。
当容器是const的时候，返回的const迭代器必须具有常属性。所以我们要加一个模板参数作为返回值。
然后list里面typedef的类型也修改一下。
然后我们解引用时，返回Ref这个模板参数
这样，我们就让const的迭代器具备了常属性
迭代器结构体的所有代码:
//迭代器 template<class T,class Ref> struct _list_iterator { typedef ListNode<T> Node; typedef _list_iterator<T,Ref> self; Node* _it; // 构造函数 _list_iterator(Node* node) :_it(node){} //前置++重载 self& operator++() { _it = _it->_next; return *this; } //后置++重载 self operator++(int) { self tmp(*this); _it = _it->_next; return tmp; } //前置--重载 self& operator--() { _it = _it->_prve; return *this; } //后置--重载 self operator--(int) { self tmp(*this); _it = _it->_prve; return tmp; } // *重载 Ref operator*() { return _it->_data; } // !=重载 bool operator!=(const self& it)const { return _it != it._it; } // ==重载 bool operator==(const self& it)const { return _it == it._it; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
十、insert函数
insert函数是在指定位置插入一个节点，那么我们可以用迭代器来接收这个要插入的位置。
//插入节点 iterator insert(iterator pos, const T& val) { assert(pos._it); //保存pos的前一个位置 Node* cru = pos._it; Node* prve = cru->_prve; //创建节点 Node* newNode = new Node(val); //链接 prve->_next = newNode; newNode->_prve = prve; newNode->_next = cru; cru->_prve = newNode; return pos; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
十一、erase函数
指定位置删除节点，删除节点会影响迭代器失效，所以要返回一个有效的迭代器。删除操作也十分简单，保存前一个节点的地址和后一个地址的节点，然后链接这2个节点，之后释放pos节点。
iterator erase(iterator pos)
{
assert(pos._it);
Node* cru = pos._it;
Node* prve = cru->_prve;
Node* next = cru->_next;
//链接
prve->_next = next;
next->_prve = prve;
//释放cru
delete cru;
return next;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
十二、pop_back函数
就是尾删，我们可以直接复用erase
void pop_back()
{
erase(end());
}
- 1
- 2
- 3
- 4
当然，push_back也可以复用inset
十三、pop_front
就是头删，还是复用erase。头插也可以复用insert
void pop_front()
{
erase(begin());
}
- 1
- 2
- 3
- 4
十四、析构函数
链表的基本功能已经实现完了，但是当我们链表不用的时候，申请的空间必须销毁。而自带的析构函数不会销毁动态申请的空间，需要我们自己写析构函数销毁。
代码:
//析构函数 ~list() { //清空链表 clear(); //释放头节点 delete _head; _head = nullptr; } void clear() { //除了头节点外，其他都释放。 iterator it = begin(); while (it != end()) { //保存下一个位置的地址 iterator next = it++; delete next._it; } //释放完之后，头节点指向的是个野指针，所以我们让它指向自己 _head->_next = _head; _head->_prve = _head; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
十五、拷贝构造函数
那么我们想拷贝链表呢？我们可以直接用迭代器区间去创建一个新的对象，然后把新对象的头节点成员和旧对象进行交换。出了函数创建的对象会自动调用析构函数释放空间。
//拷贝构造
list(const list<T>& l1)
{
//创建头节点
_head = new Node();
_head->_prve = _head;
_head->_next = _head;
//创建新对象，利用迭代器区间
list<T> tmp(l1.begin(), l1.end());
//随后交换新对象和旧对象的成员
swap(_head, tmp._head);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
十六、赋值操作符重载
我们可以利用拷贝构造创建一个新对象，然后交换头节点。函数结束，创建的对象自动析构。
代码:
list<T>& operator=(const list<T>& l1)
{
list<T> tmp(l1);
swap(_head, tmp._head);
return *this;
}
- 1
- 2
- 3
- 4
- 5
- 6
十七、迭代器优化
我们的迭代器还不够完美，因为如果list装的是自定义类型的话，我们还需要让迭代器支持 ->访问。期望它返回一个对象的指针回来，然后该对象的指针可以->直接访问成员。所以我们还需要增加模板参数。
增加一个指针参数
链表里的迭代器调整。
然后重载 迭代器的->操作符
Ptr operator->()
{
//返回对象的指针
return &(_it->_data);
}
- 1
- 2
- 3
- 4
- 5
可以直接支持->访问
十七、反向迭代器
之前在vector实现的时候，我们实现过反向迭代器。vector实现链接。所以我们可以复用这个反向迭代器。
首先，包上反向迭代器的头文件名。
其次，我们typedef 2个反向迭代器
随后用rbegin函数和rend函数获取迭代器的开始和结束位置。
begin返回的是从头节点的下一个节点，所以rend就是返回头节点的下一个位置。
end返回的是头节点，所以rbegin返回头节点。
代码:
//反向迭代器获取 reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rbegin()const { return reverse_const_iterator(end()); } const_reverse_iterator rend()const { return reverse_const_iterator(begin()); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
全部代码:
list.h代码
#pragma once #include "reverse_iterator.h" namespace wyl { //节点结构体 template<class T> struct ListNode { typedef ListNode<T> Node; Node* _prve; Node* _next; T _data; //构造函数 ListNode():_prve(nullptr),_next(nullptr),_data(0){} ListNode(const T& val) :_prve(nullptr) ,_next(nullptr) { _data = val; } }; //迭代器 template<class T,class Ref,class Ptr> struct _list_iterator { typedef ListNode<T> Node; typedef _list_iterator<T,Ref,Ptr> self; Node* _it; // 构造函数 _list_iterator(Node* node) :_it(node){} //前置++重载 self& operator++() { _it = _it->_next; return *this; } //后置++重载 self operator++(int) { self tmp(*this); _it = _it->_next; return tmp; } //前置--重载 self& operator--() { _it = _it->_prve; return *this; } //后置--重载 self operator--(int) { self tmp(*this); _it = _it->_prve; return tmp; } // *重载 Ref operator*() { return _it->_data; } // !=重载 bool operator!=(const self& it)const { return _it != it._it; } // ==重载 bool operator==(const self& it)const { return _it == it._it; } Ptr operator->() { //返回对象的指针 return &(_it->_data); } }; template<class T> class list { typedef ListNode<T> Node; public: //迭代器 typedef _list_iterator<T,T&,T*> iterator; typedef _list_iterator<T,const T&,const T*> const_iterator; //反向迭代器 typedef _reverse_iterator<iterator, T&, T*> reverse_iterator; typedef _reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator; //构造函数 list() { //开辟空间 _head = new Node(); //自己指向自己 _head->_prve = _head; _head->_next = _head; } //迭代器区间初始化 template<class InputIterator> list(InputIterator first, InputIterator last) { //创建头节点 _head = new Node(); _head->_prve = _head; _head->_next = _head; while (first != last) { push_back(*first); ++first; } } //拷贝构造 list(const list<T>& l1) { //创建头节点 _head = new Node(); _head->_prve = _head; _head->_next = _head; //创建新对象，利用迭代器区间 list<T> tmp(l1.begin(), l1.end()); //随后交换新对象和旧对象的成员 swap(_head, tmp._head); } list<T>& operator=(const list<T>& l1) { list<T> tmp(l1); swap(_head, tmp._head); return *this; } //析构函数 ~list() { //清空链表 clear(); //释放头节点 delete _head; _head = nullptr; } void clear() { //除了头节点外，其他都释放。 iterator it = begin(); while (it != end()) { //保存下一个位置的地址 iterator next = it++; delete next._it; } //释放完之后，头节点指向的是个野指针，所以我们让它指向自己 _head->_next = _head; _head->_prve = _head; } void push_back(const T& val) { //创建一个新节点 Node* newNode = new Node(val); //找到尾节点 Node* tail = _head->_prve; //尾节点和创建的节点链接 tail->_next = newNode; newNode->_prve = tail; _head->_prve = newNode; newNode->_next = _head; } void push_front(const T& val) { //创建一个新节点 Node* newNode = new Node(val); //保存头节点的下一个节点 Node* next = _head->_next; //链接 _head->_next = newNode; newNode->_prve = _head; next->_prve = newNode; newNode->_next = next; } //迭代器获取 iterator begin() { return iterator(_head->_next); } const_iterator begin()const { return const_iterator(_head->_next); } iterator end() { return iterator(_head); } const_iterator end()const { return const_iterator(_head); } //反向迭代器获取 reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rbegin()const { return const_reverse_iterator(end()); } const_reverse_iterator rend()const { return const_reverse_iterator(begin()); } //插入节点 iterator insert(iterator pos, const T& val) { assert(pos._it); //保存pos的前一个位置 Node* cru = pos._it; Node* prve = cru->_prve; //创建节点 Node* newNode = new Node(val); //链接 prve->_next = newNode; newNode->_prve = prve; newNode->_next = cru; cru->_prve = newNode; return pos; } iterator erase(iterator pos) { assert(pos._it); Node* cru = pos._it; Node* prve = cru->_prve; Node* next = cru->_next; //链接 prve->_next = next; next->_prve = prve; //释放cru delete cru; return next; } void pop_back() { erase(end()); } void pop_front() { erase(begin()); } private: Node* _head; }; //-------------------------------------------------------------------------------------------- //以下是测试内容 void listTest1() { list<int> l; l.push_back(1); l.push_back(2); l.push_back(3); l.push_front(30); l.push_front(20); l.push_front(10); } void a(const list<int>& l) { list<int>::const_iterator it = l.begin(); while (it != l.end()) { //*it = 5; cout << *it << " "; it++; } } void listTest2() { list<int> l; l.push_back(1); l.push_back(2); l.push_back(3); list<int>::iterator it = l.begin(); while (it != l.end()) { *it = 55; cout << *it << " "; ++it; } //a(l); } void listTest3() { list<int> l; l.push_back(1); l.push_back(2); l.push_back(4); l.push_back(5); l.insert(l.begin(),100); l.insert(l.end(), 10); list<int>::iterator it = l.begin(); while (it != l.end()) { if (*it % 2 == 0) { it = l.erase(it); } else ++it; } it = l.begin(); while (it != l.end()) { cout << *it << " "; ++it; } } void listTest4() { list<int> l; l.push_back(1); l.push_back(2); l.push_back(4); l.push_back(5); l.clear(); l.push_back(1); l.push_back(2); l.push_back(4); l.push_back(5); list<int> l2 = l; list<int>::iterator it = l2.begin(); while (it != l2.end()) { cout << *it << " "; ++it; } } void listTest5() { list<Date> l; l.push_back(Date(2022, 1, 3)); l.push_back(Date(2022, 1, 4)); l.push_back(Date(2022, 1, 5)); list<Date>::iterator it = l.begin(); while (it != l.end()) { cout << it->_year << "/"<<it->_month<<"/"<<it->_day<<endl; ++it; } } void listTest6() { list<Date> l; l.push_back(Date(2022, 1, 3)); l.push_back(Date(2022, 1, 4)); l.push_back(Date(2022, 1, 5)); list<Date>::reverse_iterator it = l.rbegin(); while (it != l.rend()) { cout << it->_year << "/" << it->_month << "/" << it->_day << endl; ++it; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
- 309
- 310
- 311
- 312
- 313
- 314
- 315
- 316
- 317
- 318
- 319
- 320
- 321
- 322
- 323
- 324
- 325
- 326
- 327
- 328
- 329
- 330
- 331
- 332
- 333
- 334
- 335
- 336
- 337
- 338
- 339
- 340
- 341
- 342
- 343
- 344
- 345
- 346
- 347
- 348
- 349
- 350
- 351
- 352
- 353
- 354
- 355
- 356
- 357
- 358
- 359
- 360
- 361
- 362
- 363
- 364
- 365
- 366
- 367
- 368
- 369
- 370
- 371
- 372
- 373
- 374
- 375
- 376
- 377
- 378
- 379
- 380
- 381
- 382
- 383
- 384
- 385
- 386
- 387
- 388
- 389
- 390
- 391
- 392
- 393
- 394
- 395
- 396
- 397
- 398
- 399
- 400
- 401
- 402
- 403
- 404
- 405
- 406
- 407
- 408
- 409
- 410
- 411
- 412
反向迭代器代码:
reverse_iterator.h
#pragma once template<class iterator,class Ref,class Ptr> class _reverse_iterator { typedef _reverse_iterator<iterator, Ref, Ptr> self; public: _reverse_iterator(iterator it) :_it(it) {} //前置++ self& operator++() { --_it; return *this; } //后置++ self operator++(int) { self tmp(*this); --_it; return tmp; } //前置-- self& operator--() { ++_it; return *this; } //后置-- self operator--(int) { self tmp(*this); ++_it; return tmp; } Ref operator*() { iterator tmp = (*this)._it; return *(--tmp); } Ptr operator->() { return &operator*(); } bool operator!=(const self& it) { return _it != it._it; } bool operator!=(const self& it)const { return _it != it._it; } bool operator==(const self& it) { return _it == it._it; } bool operator==(const self& it)const { return _it == it._it; } private: iterator _it; };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
主程序代码:
#include"list.h" void listTest() { //wyl::listTest2(); //wyl::listTest3(); //wyl::listTest4(); //wyl::listTest5(); wyl::listTest6(); } int main() { listTest(); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
总结:
list的实现，其实最主要的部分还是迭代器。list的迭代器是比较特殊的，因为list在内存中不是连续存储的。以上代码都是我边打，边测试，没问题了才会发出来。如果有什么没测试到的错误，欢迎大家指出。以后会持续为大家更新STL的内容，以及数据结构，C语言，linux等方面的内容。感谢大家的支持，如果感觉写的还不错，麻烦给个三连嘛。我会多多努力的！
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/426555
推荐阅读
相关标签
