-
【C++】---STL之list的模拟实现
【C++】---STL之list的模拟实现
一、list模拟实现思路
list的模拟实现比 string vector的模拟实现略微复杂一点：
（1）由于链表的每一个结点本身就是一个结构体，里面包括数据和指针，所以在接下来的模拟中，我们会将链表的每一个结点封装为一个类，也就是结点类。
（2）链表中数据的物理储存空间是不连续的，但是string和vector他们的数据储存物理空间是连续的。因此在访问链表的数据的时候，不能用原生的迭代器来进行访问，我们需要自己重载一个迭代器，自己封装一个迭代器的类。
list的模拟的大体思路：
二、结点类的实现
单个结点类的成员变量有三个：
（1）结点值：_val
（2）指向前一个结点的指针：_prev
（3）指向后一个结点的指针：_next
结点无需拷贝构造、赋值运算符重载，由于没有额外申请空间，因此也不需要析构
// 1.单个的结点类： template<class T> struct Listnode { T _val; Listnode<T>* _next; Listnode<T>* _prev; // 构造: Listnode(const T& x = T()) :_val(x) , _next(nullptr) , _prev(nullptr) { } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
三、list迭代器的实现
1、ListIterator类
（1）我们为什么要对链表的迭代器进行一个单独的封装？
因为之前普通的迭代器++都是连续，可以直接进行访问数据。
但是链表不一样，物理空间连续所以说我要把这个迭代器进行一个类的封装，然后在里面对他运算符重载（例如：++）我们就可以掌控这个迭代器的行为！
当原生的迭代器或者运算符不合我们所需要的预期的话，就可以把它进行一个封装，我们自己来重载，达到我们所需要的预期
（2）迭代器有两种，一种是普通迭代器，一种是const的迭代器
为了不使代码冗余，我们就会将两个迭代器写在一起，用模板！
对于T&，类模板实例化出两个类，一个是T&类，一个是const T&类，同理，T*也一样。使用 ：
template<class T,class Ref,class Ptr>// Ref==T& Ptr==T*- 1
类模板就会实例化出来两个类，一个是普通的、不带const的T，T&， T*，另一个是带const的T，const T&， const T*，其中Ref是引用，Ptr是指针，该类模板实例化了以下这两个类模板：
template class<T,T&,T*> iterator; template class<const T, const T& ,const T*> const_iterator;- 1
- 2
这样我们就解决了两个类的问题。
2、构造函数
template<class T,class Ref,class Ptr> struct ListIterator { typedef Listnode<T> Node;// 1.(这个是单个结点“类型”的重定义) 不管你是什么类型的结点 我都给你整成Node，因为Listnode是一个结点模版！ typedef ListIterator<T, Ref, Ptr> Self; // 2.(这个是本迭代器指针“类型”的重定义) // 成员变量： Node* _node; // 构造： ListIterator(const Node* node) :_node(node) { } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
3、operator*运算符重载
// 重载*(*it) // Ref==T& Ref operator*()// 为什么要传引用返回呢？因为有的时候我们可能需要对it进行修改+1,-1等等。 { return _node->_data; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
5、operator->运算符重载
// 重载-> //Ptr==T* Ptr operator->() {- 1
- 2
- 3
- 4
- 5
6、operator！=运算符重载
对于==和!=的重载的时候，我们一定要想清楚到底是对它里面节点的值来判断相不相等，还是说来判断指向这个结点的迭代器指针相不相等。很明显我们这里重载（ = =）和（！=）通过判断结点的迭代器相等不相等来进行重载的。
// != bool operator!=(const Self& it) { return _node != it._node; }- 1
- 2
- 3
- 4
- 5
7、operator==运算符重载
比较两个迭代器相等不相等的时候一定不能比较所指向节点中的值，万一所有的节点里面值相等都是一样，那你意思就是说：这里面的所有迭代器都是相等吗？不就扯淡吗？！所以说比较迭代器相不相等：就是比较两者是不是指向同一个结点（即：比较指针是否相等！）因为迭代器本质上是指针！
bool operator==(const Self& it) { return _node == it._node; }- 1
- 2
- 3
- 4
8、前置++
//前置++,(++it) Self& operator++()//因为++对内容进行了修改，所以要传引用返回！ { _node = _node->_next; return *this; }- 1
- 2
- 3
- 4
- 5
- 6
9、后置++
//后置++，(it++) Self operator++(int) { Self tmp = *this;//因为后置++，要返回的是++之前的值，所以要先保存未++的值在tmp里面！ _node = _node->_next; return tmp; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
10、前置–
//前置--,(--it) Self& operator--()//因为--对内容进行了修改，所以要传引用返回！ { _node = _node->_prev; return *this; }- 1
- 2
- 3
- 4
- 5
- 6
11、后置–
//后置--，(it) Self operator--(int) { Self tmp = *this;//因为后置--,要返回的是--之前的值，所以要先保存未--的值在tmp里面！ _node = _node->_prev; return tmp; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
四、list类的实现
1、list类
list的成员只需要一个头节点，然后通过迭代器来访问后面的其他元素即可。
2、构造
//1、构造： list() { _head = new Node;//会调ListNode的构造函数 _head->_next = _head;//整个链表只有头节点，先构造一个没有实际节点的链表 _head->_prev = _head;//整个链表只有头节点，先构造一个没有实际节点的链表 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
3、析构
// 2、析构 ~list() { clear(); delete[] _head; _head = nullptr; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
4、拷贝构造
//特意写一个，初始化一个哨兵位 void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; } // 3、拷贝构造 // lt2(lt1) list(const list<T> lt) { empty_init();//先初始化一个头结点 for (auto& e : lt)// 接下来在哨兵位后面 尾插 就可以实现拷贝构造！ { push_back(e); } } // 需要析构，一般就需要自己写深拷贝 // 不需要析构，一般就不需要自己写深拷贝，默认浅拷贝就可以 };- 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
5、赋值运算符重载
（1）传统的赋值运算符重载
//赋值运算符重载 lt1 = lt 传统写法 list<T> operator=(const list<T>& lt) { //链表已存在，只需将节点尾插进去即可 if(this != lt) { for (auto& e : lt) { push_back(e); } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
（2）现代的赋值运算符重载
//4、赋值运算符重载(深拷贝) // lt1=lt2 list<T>& operator=(list<T> lt) { swap(lt); return *this; } void swap(list<T>& lt) { std::(_head, lt._head); std::(_size, lt._size); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
6、迭代器
（1）普通迭代器：
iterator begin() { //iterator it = _head->_next;// 有名对象 //调用迭代器的构造函数创建一个迭代器it //return it; return iterator(_head->_next);// 匿名对象 // return _head->_next; // 不能这样写，因为返回类型是迭代其指针，而你这样返回的是一个结点。 } iterator end() { return iterator(_head); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
只要你有节点的指针，就可以构造迭代器：
下面这里就是构造了一个迭代器，因为它的返回类型是迭代器，你只要有节点的指针我就可以构造一个迭代器，只不过有两种情况是匿名对象，另外一种是有名对象：
（2）const迭代器：const_iterator begin() const { return const_iterator(_head->_next);//头节点不存数据 } const_iterator end() const { return const_iterator(_head);//尾节点的下一个节点位置即头节点 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
7、insert()
// 3.insert void insert(iterator pos, const T& val)//在pos位置之前插入val { //先用一个指针保存pos的位置！ Node* cur = pos._node; //创建一个新的节点newnode来接受val的值 Node* newnode = new Node(val); //再保存pos位置前一个方便newnode插入！ Node* prev = cur->_prev; //prev newnode cur三者之间的交换 newnode->_prev = prev; prev->_next = newnode; newnode->_next = cur; cur->_prev = newnode; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
8、erase()
iterator erase(iterator pos) { // 1、先保存pos位置的前后！ Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; // 2、prev 和 next两者之间进行链接！ prev->_next = next; next->_prev = prev; // 3、直接删除cur delete cur; // 4、因为是模拟原本库里面的erase函数，返回的就是要删除pos位置的下一个位置的迭代器。 return iterator(next); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
9、clear()
void clear() { iterator it = begin(); while (it != end()) { it = erase(it); //因为erase会返回要删除结点的下一个位置，所以要用iterator类型的it接受！ } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
10、push_front()
// 头插 void push_front(const T& x) { insert(begin(), x); }- 1
- 2
- 3
- 4
- 5
11、push_back()
// 尾插 void push_back(const T& x) { insert(end(), x); }- 1
- 2
- 3
- 4
- 5
12、pop_front()
// 头删 void pop_front() { erase(begin()); }- 1
- 2
- 3
- 4
- 5
13、pop_back()
// 尾删 void pop_back() { erase(--end()); }- 1
- 2
- 3
- 4
- 5
- 6
14、empty()
bool empty() { return (_head->_next == _head); }- 1
- 2
- 3
- 4
- 5
- 6
15、size()
size_t size()const { size_t count = 0; Node* cur = _head; while (cur->_next != _head) { cur = cur->_next; count++; } return count; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
五、完整代码
#pragma once #include#include using namespace std; namespace yjl { template<class T> struct Listnode { Listnode<T>* _prev; Listnode<T>* _next; T _data; //单个节点之间的内部构造 Listnode(const T& x = T()) :_prev(nullptr) , _next(nullptr) , _data(x) { } }; /// /// list迭代器的封装： //template //struct ListIterator //{ // typedef Listnode Node;// 1.(这个是单个结点“类型”的重定义) 不管你是什么类型的结点 我都给你整成Node，因为Listnode // typedef ListIterator是一个结点模版！ Self; // 2.(这个是本迭代器指针“类型”的重定义) // Node* _node; // //构造 // ListIterator(Node* node) // :_node(node) // {} // // 重载*(*it) // const T& operator*()// 为什么要传引用返回呢？因为有的时候我们可能需要对it进行修改+1,-1等等。 // { // return _node->_data; // } // // 重载-> // const T* operator->() // { // return &_node->_data;//得到的是地址：T* // } // //前置++,(++it) // Self& operator++()//因为++对内容进行了修改，所以要传引用返回！ // { // _node = _node->_next; // return *this; // } // //后置++，(it++) // Self operator++(int) // { // Self tmp = *this;//因为后置++，要返回的是++之前的值，所以要先保存未++的值在tmp里面！ // _node = _node->_next; // return tmp; // } // //前置--,(--it) // Self& operator--()//因为--对内容进行了修改，所以要传引用返回！ // { // _node = _node->_prev; // return *this; // } // //后置--，(it) // Self operator--(int) // { // Self tmp = *this;//因为后置--,要返回的是--之前的值，所以要先保存未--的值在tmp里面！ // _node = _node->_prev; // return tmp; // } // bool operator!=(const Self& it) // { // return _node != it._node; // } // bool operator==(const Self& it) // { // return _node == it._node; // } //}; // typedef ListIterator是一个结点模版！ typedef ListIterator<T,Ref,Ptr> Self; // 2.(这个是本迭代器指针“类型”的重定义) Node* _node; //构造 ListIterator(Node* node) :_node(node) {} // 重载*(*it) // Ref==T& Ref operator*()// 为什么要传引用返回呢？因为有的时候我们可能需要对it进行修改+1,-1等等。 { return _node->_data; } // 重载-> //Ptr==T* Ptr operator->() { return &_node->_data;//得到的是地址：T* } //前置++,(++it) Self& operator++()//因为++对内容进行了修改，所以要传引用返回！ { _node = _node->_next; return *this; } //后置++，(it++) Self operator++(int) { Self tmp = *this;//因为后置++，要返回的是++之前的值，所以要先保存未++的值在tmp里面！ _node = _node->_next; return tmp; } //前置--,(--it) Self& operator--()//因为--对内容进行了修改，所以要传引用返回！ { _node = _node->_prev; return *this; } //后置--，(it) Self operator--(int) { Self tmp = *this;//因为后置--,要返回的是--之前的值，所以要先保存未--的值在tmp里面！ _node = _node->_prev; return tmp; } bool operator!=(const Self& it) { return _node != it._node; } bool operator==(const Self& it) { return _node == it._node; } }; /// /// template<class T> class list { typedef Listnode<T> Node; public: typedef ListIterator<T,T&,T*> iterator; typedef ListIterator<T, const T&,const T*> const_iterator; iterator begin() { //iterator it = _head->_next;// 有名对象 //调用迭代器的构造函数创建一个迭代器it //return it; return iterator(_head->_next);// 匿名对象 // return _head->_next; // 不能这样写，因为返回类型是迭代其指针，而你这样返回的是一个结点。 } iterator end() { return iterator(_head); } // 1.多个节点之间的构造：初始化一个哨兵位 //特意写一个，初始化一个哨兵位 void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; } // 构造 list() { empty_init(); } // 拷贝构造函数 // lt2(lt1) list(const list<T>& lt) { empty_init();// 先构造一个哨兵位头结点 for (auto& e : lt)// 接下来在哨兵位后面 尾插 就可以实现拷贝构造！ { push_back(e); } } // 需要析构，一般就需要自己写深拷贝 // 不需要析构，一般就不需要自己写深拷贝，默认浅拷贝就可以 //赋值运算符重载(深拷贝) // lt1=lt2 list<T>& operator=(list<T> lt) { swap(lt); return *this; } void swap(list<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } // 析构 ~list() { clear(); delete _head; _head = nullptr; } // 2.push_back() //void push_back(const T& x) //{ // Node* tmp = new Node(x); // Node* tail = _head->_prev;// 因为要尾插，所以保存好尾节点！ // tail->_next = tmp; // tmp->_prev = tail; // tmp->_next = _head; // _head->_prev = tmp; //} // 头插 void push_front(const T& x) { insert(begin(), x); } // 尾插 void push_back(const T& x) { insert(end(), x); } // 头删 void pop_front() { erase(begin()); } // 尾删 void pop_back() { erase(--end()); } // 3.insert void insert(iterator pos, const T& val)//在pos位置之前插入val { //先用一个指针保存pos的位置！ Node* cur = pos._node; //创建一个新的节点newnode来接受val的值 Node* newnode = new Node(val); //再保存pos位置前一个方便newnode插入！ Node* prev = cur->_prev; //prev newnode cur三者之间的交换 newnode->_prev = prev; prev->_next = newnode; newnode->_next = cur; cur->_prev = newnode; } iterator erase(iterator pos) { Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur;// 我们delete cur之后，原来的pos迭代器指针也就消失了，但是我们为什么必须要返回一个：迭代器指针？ return iterator(next);// 因为删除的数据是有不确定性的，万一要删除偶数或者后面有其他的用途，我们没有原来pos的位置，我们如何再找到其他的数据呢？ } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); //因为erase会返回要删除结点的下一个位置，所以要用iterator类型的it接受！ } } //size_t size()const //{ // size_t count = 0; // while (_head->_next != _head) // { // _head = _head->_next;// 因为_head是不能被修改的！！！，所以要创建一个临时指针来指向_head // count++; // } // return count; //} size_t size()const { size_t count = 0; Node* cur = _head; while (cur->_next != _head) { cur = cur->_next; count++; } return count; } bool empty() { return (_head->_next == _head); } private: Node* _head; size_t _size; };- 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
好了，今天的分享就到这里了
如果对你有帮助，记得点赞👍+关注哦！
我的主页还有其他文章，欢迎学习指点。关注我，让我们一起学习，一起成长吧！
-
相关阅读:
什么是活动目录（Active Directory）
虚拟电厂可视化大屏，深挖痛点精准减碳
Next.js下通过env分环境控制功能开关
Vue3新特性--学习笔记
LAYUI-FROM
OpenCV（应用） —— 目标轮廓的相关应用
数据结构与算法（三）散列表篇
我的期末网页设计HTML作品——咖啡文化网页制作
loadrunner-controller-手动场景Schedule配置
[Cortex-M3]-4-如何在内嵌RAM中运行程序
- 原文地址：https://blog.csdn.net/weixin_75128035/article/details/138161636
