-
STL容器——list
前言：list是带头节点的双向循环链表，本文意在了解list的基本使用，并且模拟实现list。
1.list的基本框架
list是由一个一个的节点，形成的双向带头链表，所以必须实现节点这一结构。
template<class T> struct ListNode { //节点的构造函数 ListNode(const T& val = T()) :_pNext(nullptr), _pPre(nullptr), _val(val) { } //指向前面节点的指针 ListNode<T>* _pPre; //指向后面节点的指针 ListNode<T>* _pNext; //节点的数据 T _val; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
有了节点，再对节点进行链接，就形成了链表。链表中只需要有头节点就可以通过头节点找到其他的节点。class list { typedef ListNode<T> Node; typedef Node* PNode; private: PNode _pHead; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
实现构造函数，只创造头节点，至于后面的节点插入就好了
list() { _pHead = new Node; _pHead->_pNext = _pHead; _pHead->_pPre = _pHead; }- 1
- 2
- 3
- 4
- 5
- 6
实现push_back()，插入数据
void push_back(const T& val) { //创建新的节点 PNode newnode = new Node(val); //保存尾节点 PNode tail = _pHead->_pPre; //进行链接 _pHead->_pPre = newnode; tail->_pNext = newnode; newnode->_pNext = _pHead; newnode->_pPre = tail; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
这就是最简易的list实现。
namespace ly { //list的节点 template<class T> struct ListNode { //节点的构造函数 ListNode(const T& val = T()) :_pNext(nullptr), _pPre(nullptr), _val(val) { } //指向前面节点的指针 ListNode<T>* _pPre; //指向后面节点的指针 ListNode<T>* _pNext; //节点的数据 T _val; }; template<class T> class list { typedef ListNode<T> Node; typedef Node* PNode; public: //构造函数 list() { _pHead = new Node; _pHead->_pNext = _pHead; _pHead->_pPre = _pHead; } //插入节点 void push_back(const T& val) { //创建新的节点 PNode newnode = new Node(val); //保存尾节点 PNode tail = _pHead->_pPre; //进行链接 _pHead->_pPre = newnode; tail->_pNext = newnode; newnode->_pNext = _pHead; newnode->_pPre = tail; } private: PNode _pHead; } }- 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
2.list的具体模拟实现
上述的list功能和STL中的list相差甚远，所以我们需要进一步的完善我们的list。
2.1 list的迭代器实现
vector和string的迭代器是封装的指针，因为它俩是顺序储存，物理地址挨着，所以迭代器的实现和操作都非常的简单。但是list的迭代器呢？它由于物理空间不连续，用指针，将链表串联起来，不支持随机访问。该如何实现它的迭代器呢？这个迭代器如何进行++，解引用等操作呢？
答案是：我们可以创建一个迭代器类，在类中实现迭代器的功能，我们可以重载运算符，对吧？2.1.1 简易迭代器实现
实现一个简易的迭代器，完成++到下一个节点的功能，以及解引用。
template<class T> class ListIterator { typedef ListNode<T>* PNode; typedef ListIterator<T> Self; public: //迭代器 PNode _pNode; //迭代器构造 ListIterator(PNode pNode = nullptr) :_pNode(pNode) { } //迭代器++，-- //前置++ Self& operator++() { _pNode = _pNode->_pNext; return *this; } //后置++ Self operator++(int) { Self tmp(*this); _pNode = _pNode->_pNext; return tmp; } Self& operator--() { _pNode = _pNode->_pPre; return *this; } Self operator--(int) { Self tmp(*this); _pNode = _pNode->_pPre; return tmp; } //迭代器解引用 Ref operator*() { return _pNode->_val; } };- 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
2.1.2 如何支持const版本的迭代器
但是上述的迭代器，如果想要支持const版本的，该如何实现呢？
可能有人说，这不难，我直接再写一个迭代器就好了，里面全换成支持const调用的版本就好了，这个方法可以，但是不要忘了模板参数这个东东。template<class T，class Ref> class ListIterator { typedef ListNode<T>* PNode; typedef ListIterator<T,Ref> Self; public: //迭代器 PNode _pNode; //迭代器构造 ListIterator(PNode pNode = nullptr) :_pNode(pNode) { } //迭代器++，-- //前置++ Self& operator++() { _pNode = _pNode->_pNext; return *this; } //后置++ Self operator++(int) { Self tmp(*this); _pNode = _pNode->_pNext; return tmp; } Self& operator--() { _pNode = _pNode->_pPre; return *this; } Self operator--(int) { Self tmp(*this); _pNode = _pNode->_pPre; return tmp; } //迭代器解引用 Ref operator*() { return _pNode->_val; } };- 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
昂这样就可以了？就改个模板参数？答案是：就是这样，改模板参数，具体使用时，直接对应推导即可。
比如：typedef ListIterator<T, T&> iterator; typedef ListIterator<T, const T&> const_iterator;- 1
- 2
这样就已经，完成了两个版本。
2.1.3 完整的迭代器
迭代器也是支持
->，同样也得支持const版本，所以再添加一个模板参数。总共就是三个参数，查看STL源码时，当然也是三个模板参数。typedef ListIterator<T, T&,T*> iterator; typedef ListIterator<T, const T&,const T*> const_iterator;- 1
- 2
template<class T, class Ref, class Ptr> class ListIterator { typedef ListNode<T>* PNode; typedef ListIterator<T, Ref, Ptr> Self; public: ListIterator(PNode pNode = nullptr) :_pNode(pNode) { } Ref operator*() { return _pNode->_val; } Ptr operator->() { return &_pNode->_val; } Self& operator++() { _pNode = _pNode->_pNext; return *this; } Self operator++(int) { Self tmp(*this); _pNode = _pNode->_pNext; return tmp; } Self& operator--() { _pNode = _pNode->_pPre; return *this; } Self operator--(int) { Self tmp(*this); _pNode = _pNode->_pPre; return tmp; } bool operator!=(const Self& it) { return _pNode != it._pNode; } bool operator==(const Self& it) { return _pNode == it._pNode; } PNode _pNode; };- 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
关于以上对
->重载，大家可能有疑惑？为什么返回的是一个T*，或者是一个const T*。
也就是说我们调用 iterator it->，返回的是一个指针，所以还得加一个->才能达到我们想要的结果，但是由于这样的可读性比较差，所以编译器做了优化，并不需要额外添加->。
2.2 list的构造函数
每个list都有一个哨兵位头节点，所以我们写一个创造头节点的函数
void CreateHead() { _pHead = new Node(); _pHead->_pNext = _pHead; _pHead->_pPre = _pHead; }- 1
- 2
- 3
- 4
- 5
- 6
2.2.1 list构造函数
//无参的构造，只创造头节点 //这里直接复用CreatHead()也可以 list() { _pHead = new Node; _pHead->_pNext = _pHead; _pHead->_pPre = _pHead; } //构造list含有n个节点且节点的val为value list(int n, const T& value = T()) { //创造头节点 CreateHead(); for (int i = 0; i < n; i++) { push_back(value); } } //根据迭代器的区间，初始化list template <class Iterator> list(Iterator first, Iterator last) { CreateHead(); while (first != last) { push_back(*first); ++first; } }- 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
2.2.2 list的拷贝构造以及
=的重载list(const list<T>& it) { CreateHead(); list<T> tmp(it.begin(), it.end()); std::swap(_pHead, tmp._pHead); } list<T>& operator=(list<T> it) { std::swap(_pHead, it._pHead); return *this; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
拷贝构造的话，直接创建一个临时的list tmp去拷贝 it 的所有节点值，再和this交换头节点就可以了。
赋值重载，用的传值传参，所以直接交换 it 的头节点即可。
2.2.3 迭代器功能实现
typedef ListIterator<T, T&,T*> iterator; typedef ListIterator<T, const T&,const T*> const_iterator; iterator begin() { return iterator(_pHead->_pNext); } iterator end() { return iterator(_pHead); } const_iterator begin() const { return const_iterator(_pHead->_pNext); } const_iterator end() const { return const_iterator(_pHead); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
2.2.4 插入和删除操作
// 在pos位置前插入值为val的节点 iterator insert(iterator pos, const T& val) { PNode newnode = new Node(val); PNode cur = pos._pNode; PNode pre = cur->_pPre; cur->_pPre = newnode; newnode->_pNext = cur; pre->_pNext = newnode; newnode->_pPre = pre; return iterator(newnode); } 删除pos位置的节点，返回该节点的下一个位置 iterator erase(iterator pos) { PNode next = pos._pNode->_pNext; PNode pre = pos._pNode->_pPre; pre->_pNext = next; next->_pPre = pre; delete pos._pNode; return iterator(next); } 全部复用上面的即可 //尾插 void push_back(const T& val) { /*PNode newnode = new Node(val); PNode tail = _pHead->_pPre; _pHead->_pPre = newnode; tail->_pNext = newnode; newnode->_pNext = _pHead; newnode->_pPre = tail;*/ insert(end(), val); } //尾删 void pop_back() { erase(end()); } //头插 void push_front(const T& val) { insert(begin(), val); } //头删 void pop_front() { erase(begin()); }- 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
上面的所有功能都可以复用insert和erase，从这里直观的看出list的插入删除非常高效，只需要改变一下节点的指向关系，就能完成插入，删除，灰常强势。
2.2.5 析构函数
清理资源的话，我们希望实现两种：一种可以清除除了头节点的所有其它节点，另一种则是完成的释放list的所有节点。
//不清除头节点 void clear() { iterator it = begin(); while (it != end()) { erase(it++); } } //析构函数 void clear() { iterator it = begin(); while (it != end()) { erase(it++); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
2.2.6 其他功能
size_t size() const { size_t i = 0; const_iterator it = begin(); while (it != end()) { i++; it++; } return i; } bool empty()const { return _pHead->_pNext == _pHead->_pPre; } T& front() { return * begin(); } const T& front()const { return *begin(); } T& back() { return *(--end()); } const T& back()const { return *(--end()); } void Print() { for (auto it : *this) { std::cout << it << ' '; } std::cout << std::endl; }- 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
3. list模拟实现代码
#includenamespace ly { // List的节点类 template<class T> struct ListNode { ListNode(const T& val = T()) :_pNext(nullptr), _pPre(nullptr), _val(val) { } ListNode<T>* _pPre; ListNode<T>* _pNext; T _val; }; //List的迭代器类 template<class T, class Ref, class Ptr> class ListIterator { typedef ListNode<T>* PNode; typedef ListIterator<T, Ref, Ptr> Self; public: ListIterator(PNode pNode = nullptr) :_pNode(pNode) { } Ref operator*() { return _pNode->_val; } Ptr operator->() { return &_pNode->_val; } Self& operator++() { _pNode = _pNode->_pNext; return *this; } Self operator++(int) { Self tmp(*this); _pNode = _pNode->_pNext; return tmp; } Self& operator--() { _pNode = _pNode->_pPre; return *this; } Self operator--(int) { Self tmp(*this); _pNode = _pNode->_pPre; return tmp; } bool operator!=(const Self& it) { return _pNode != it._pNode; } bool operator==(const Self& it) { return _pNode == it._pNode; } PNode _pNode; }; //list类 template<class T> class list { typedef ListNode<T> Node; typedef Node* PNode; public: typedef ListIterator<T, T&, T*> iterator; typedef ListIterator<T, const T&, const T&> const_iterator; public: /// // List的构造 list() { _pHead = new Node; _pHead->_pNext = _pHead; _pHead->_pPre = _pHead; } list(int n, const T& value = T()) { CreateHead(); for (int i = 0; i < n; i++) { push_back(value); } } template <class Iterator> list(Iterator first, Iterator last) { CreateHead(); while (first != last) { push_back(*first); ++first; } } list(const list<T>& it) { CreateHead(); list<T> tmp(it.begin(), it.end()); std::swap(_pHead, tmp._pHead); } list<T>& operator=(list<T> it) { std::swap(_pHead, it._pHead); return *this; } void clear() { iterator it = begin(); while (it != end()) { erase(it++); } } /// // List Iterator iterator begin() { return iterator(_pHead->_pNext); } iterator end() { return iterator(_pHead); } const_iterator begin() const { return const_iterator(_pHead->_pNext); } const_iterator end() const { return const_iterator(_pHead); } / List Capacity size_t size() const { size_t i = 0; const_iterator it = begin(); while (it != end()) { i++; it++; } return i; } bool empty()const { return _pHead->_pNext == _pHead->_pPre; } // List Access T& front() { return * begin(); } const T& front()const { return *begin(); } T& back() { return *(--end()); } const T& back()const { return *(--end()); } // List Modify void push_back(const T& val) { /*PNode newnode = new Node(val); PNode tail = _pHead->_pPre; _pHead->_pPre = newnode; tail->_pNext = newnode; newnode->_pNext = _pHead; newnode->_pPre = tail;*/ insert(end(), val); } void pop_back() { erase(end()); } void push_front(const T& val) { insert(begin(), val); } void pop_front() { erase(begin()); } // 在pos位置前插入值为val的节点 iterator insert(iterator pos, const T& val) { PNode newnode = new Node(val); PNode cur = pos._pNode; PNode pre = cur->_pPre; cur->_pPre = newnode; newnode->_pNext = cur; pre->_pNext = newnode; newnode->_pPre = pre; return iterator(newnode); } 删除pos位置的节点，返回该节点的下一个位置 iterator erase(iterator pos) { PNode next = pos._pNode->_pNext; PNode pre = pos._pNode->_pPre; pre->_pNext = next; next->_pPre = pre; delete pos._pNode; return iterator(next); } void clear() { iterator it = begin(); while (it != end()) { erase(it++); } } void swap(list<T>& it) { PNode tmp = it._pHead; it._pHead = _pHead; _pHead = tmp; } void Print() { for (auto it : *this) { std::cout << it << ' '; } std::cout << std::endl; } private: void CreateHead() { _pHead = new Node(); _pHead->_pNext = _pHead; _pHead->_pPre = _pHead; } PNode _pHead; }; }; - 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
**结尾语：**以上就是list的模拟实现。
-
相关阅读:
解读数仓中的数据对象及相关关系
Windows11 VMware-Ubuntu-Android12 源码下载和编译
三、Midway 接口安全认证
GetHashCode与Equals
redis多节点部署实施指引
UNIAPP实战项目笔记42 购物车页面新增收货地址
大一学生WEB前端静态网页——唯品会1页 包含hover效果
美篇作文网教学资源源码-自带作文数据
集简云平台助力无代码开发，实现平安银行与电商平台、CRM系统的快速连接
【最佳实践】CentOS7.9 下绿色安装最新版本的 Tomcat-10.1.2 以及最新的 Java19
- 原文地址：https://blog.csdn.net/lyzzs222/article/details/126720169
