-
C++——list的模拟实现
list的节点类
定义了一个类模板
list_node,表示链表节点。成员变量包括指向下一个节点的指针
_next,一个指向上一个节点的指针_prev和一个存储值的变量_val在构造函数中，可以通过传入参数来初始化节点的值，默认值为类型
T的默认构造值定义了一个节点类，用来创建一个双链表，可以存储任意类型的值。每个节点都包含上一个节点和下一个节点的指针
templatestruct list_node { list_node * _next; list_node * _prev; T _val; list_node(const T& val = T()) :_next(nullptr) , _prev(nullptr) , _val(val) {} }; - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
定义了一个双线链表的迭代器类
__list_iterator，这个迭代器有三个模板参数，分别是类型T,引用类型Ref和指针类型Ptrlist的迭代器类
这段代码定义了一个双向链表的迭代器类
__list_iterator。这个迭代器有三个模板参数，分别是类型T、引用类型Ref和指针类型Ptr。__list_iterator类有一个私有成员变量_node，它是指向Node类型的指针。类的构造函数
__list_iterator(Node* node)接收一个Node类型的指针作为参数，并将其赋值给私有成员变量_node。templatestruct __list_iterator { typedef list_node Node; typedef __list_iterator - 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
typedef list_node语句的意思是给Node; list_node类型取一个别名叫做Node。通过这种方式，可以使用Node来代替list_node，使代码更加简洁和易读。list_node是一个模板类，表示链表中的节点。typedef语句将list_node类型命名为Node，可以通过Node来声明和使用节点对象，比如Node*表示指向节点的指针，Node val表示一个节点对象等。注意，这里的
T是一个模板参数，可以根据实际需求来指定具体的类型。例如，如果定义了list_node，则Node表示一个整数类型的链表节点。typedef list_nodeNode; - 1
typedef __list_iterator语句的意思是给__list_iterator类型取一个别名叫做self。通过这种方式，可以使用self来代替__list_iterator，使代码更加简洁和易读。__list_iterator是一个迭代器模板类，表示链表的迭代器。typedef语句将__list_iterator类型命名为self，可以通过self来声明和使用迭代器对象，比如self it表示一个迭代器对象，self*表示指向迭代器的指针等。注意，这里的
T、Ref和Ptr是模板参数，可以根据实际需求来指定具体的类型。例如，如果定义了__list_iterator，则self表示一个整数类型的链表迭代器。typedef __list_iterator- 1
__list_iterator(Node* node) : _node(node) {}是一个构造函数的定义。构造函数用于初始化类的对象。这个构造函数接受一个指向
Node类型的指针node作为参数。在构造函数的执行过程中，将传入的node赋值给类的成员变量_node，用于初始化迭代器对象的内部状态。这里假设
__list_iterator是一个链表迭代器类，存储指向链表节点的指针。构造函数的作用是根据传入的节点指针初始化迭代器对象。__list_iterator(Node* node) :_node(node) {}- 1
- 2
- 3
operator*()重载了解引用运算符，返回当前节点的值，以引用类型Ref返回。Ref operator*() { return _node->_val; }- 1
- 2
- 3
- 4
operator->()重载了箭头运算符，返回当前节点的指针，以指针类型Ptr返回。Ptr operator->() { return &_node->_val; }- 1
- 2
- 3
- 4
operator++()重载了前置递增运算符，使得迭代器指向下一个节点，并返回自身的引用。self& operator++() { _node = _node->_next; return *this; }- 1
- 2
- 3
- 4
- 5
operator++(int)重载了后置递增运算符，使得迭代器指向下一个节点，并返回递增前的迭代器自身self operator++(int) { self tmp(*this); _node = _node->_next; return tmp; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
operator--()重载了前置递减运算符，使得迭代器指向上一个节点，并返回自身的引用。self& operator--() { _node = _node->_prev; return *this; }- 1
- 2
- 3
- 4
- 5
operator--(int)重载了后置递减运算符，使得迭代器指向上一个节点，并返回递减前的迭代器自身。self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
operator!=()重载了不等于运算符，判断两个迭代器是否不相等。bool operator!=(const self& it) const { return _node != it._node; }- 1
- 2
- 3
- 4
operator==()重载了等于运算符，判断两个迭代器是否相等bool operator==(const self& it) const { return _node == it._node; }- 1
- 2
- 3
- 4
list类模板
public: typedef __list_iterator& lt) //list(const list& lt) { empty_init(); for (auto& e : lt) { push_back(e); } } void swap(list & lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } list & operator=(list lt) //list& operator=(list lt) { swap(lt); return *this; } ~list() { clear(); delete _head; _head = nullptr; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } _size = 0; } void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } // pos位置之前插入 iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); prev->_next = newnode; newnode->_next = cur; cur->_prev = newnode; newnode->_prev = prev; ++_size; return newnode; } iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; --_size; return next; } size_t size() { return _size; } 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
这段代码是使用
typedef关键字定义了一个名为iterator的类型别名。__list_iterator是一个自定义的模板类，用于表示链表的迭代器。它具有三个模板参数，分别是T、T&和T*。- 第一个模板参数
T表示链表中节点存储的数据类型。 - 第二个模板参数
T&表示迭代器所引用的数据类型，即通过迭代器可以对节点中的数据进行修改。 - 第三个模板参数
T*表示指向节点的指针类型。
通过将
__list_iterator模板实例化并传入上述模板参数，就可以得到具体类型的迭代器类。而typedef关键字则用来给这个具体类型的迭代器类起一个别名，即iterator。通过这个别名，我们可以方便地使用
iterator作为具体类型的迭代器对象的类型，而不需要每次都使用完整的模板参数列表来声明迭代器对象。typedef __list_iterator- 1
typedef __list_iterator- 1
begin()：返回一个指向链表第一个元素的迭代器（支持可读可写）iterator begin() { return iterator(_head->_next); }- 1
- 2
- 3
- 4
end()：返回一个指向链表尾部的迭代器。（支持可读可写）iterator end() { return _head; }- 1
- 2
- 3
- 4
begin()：返回一个指向链表第一个元素的迭代器（支持可读）const_iterator begin() const { return const_iterator(_head->_next); }- 1
- 2
- 3
- 4
end()：返回一个指向链表尾部的迭代器。（支持可读可写）const_iterator end() const { return _head; }- 1
- 2
- 3
- 4
empty_init()：初始化空链表的头节点，并设置头节点的前驱和后继指针。void empty_init() { _head = new Node; _head->_prev = _head; _head->_next = _head; _size = 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
list()：默认构造函数，调用empty_init()初始化空链表。list() { empty_init(); }- 1
- 2
- 3
- 4
list(const list：复制构造函数，通过遍历参数& lt) lt中的元素，逐个调用push_back(e)插入到新链表中。list(const list& lt) { empty_init(); for (auto& e : lt) { push_back(e); } } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
swap(list：交换当前链表和参数& lt) lt的内容。void swap(list& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } - 1
- 2
- 3
- 4
- 5
list：赋值运算符重载，通过调用& operator=(list lt) swap(lt)将参数lt和当前链表内容交换。list& operator=(list lt) { swap(lt); return *this; } - 1
- 2
- 3
- 4
- 5
- 6
~list()：析构函数，调用clear()清空链表并释放头节点的内存。~list() { clear(); delete _head; _head = nullptr; }- 1
- 2
- 3
- 4
- 5
- 6
push_back(const T& x)：在链表末尾插入元素x。void push_back(const T& x) { insert(end(), x); }- 1
- 2
- 3
- 4
push_front(const T& x)：在链表头部插入元素x。void push_front(const T& x) { insert(begin(), x); }- 1
- 2
- 3
- 4
pop_back()：删除链表末尾的元素。void pop_back() { erase(--end()); }- 1
- 2
- 3
- 4
pop_front()：删除链表头部的元素。void push_front(const T& x) { insert(begin(), x); }- 1
- 2
- 3
- 4
insert(iterator pos, const T& x)：在迭代器pos指向的位置之前插入元素x。iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; --_size; return next; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
erase(iterator pos)：删除迭代器pos指向的元素。iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; --_size; return next; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
size()：返回链表的大小。size_t size() { return _size; }- 1
- 2
- 3
- 4
完整代码
#pragma once #include#include #include #include -
#include
using namespace std; namespace bit { template struct list_node { list_node * _next; list_node * _prev; T _val; list_node(const T& val = T()) :_next(nullptr) , _prev(nullptr) , _val(val) {} }; template struct __list_iterator { typedef list_node Node; typedef __list_iterator class list { typedef list_node Node; public: typedef __list_iterator const_iterator; // 这样设计const迭代器是不行的，因为const迭代器期望指向内容不能修改 // 这样设计是迭代器本身不能修改 // typedef const __list_iterator const_iterator; // const T* ptr1; // T* const ptr2; // 如何设计const迭代器？ iterator begin() { //return _head->_next; return iterator(_head->_next); } iterator end() { return _head; //return iterator(_head); } const_iterator begin() const { //return _head->_next; return const_iterator(_head->_next); } const_iterator end() const { return _head; //return const_iterator(_head); } void empty_init() { _head = new Node; _head->_prev = _head; _head->_next = _head; _size = 0; } list() { empty_init(); } // lt2(lt1) list(const list & lt) //list(const list& lt) { empty_init(); for (auto& e : lt) { push_back(e); } } void swap(list & lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } list & operator=(list lt) //list& operator=(list lt) { swap(lt); return *this; } ~list() { clear(); delete _head; _head = nullptr; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } _size = 0; } void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } // pos位置之前插入 iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); prev->_next = newnode; newnode->_next = cur; cur->_prev = newnode; newnode->_prev = prev; ++_size; return newnode; } iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; --_size; return next; } size_t size() { return _size; } private: Node* _head; size_t _size; }; void Print(const list & lt) { list ::const_iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; } void test_list1() { list lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); list ::iterator it = lt.begin(); while (it != lt.end()) { (*it) += 1; cout << *it << " "; ++it; } cout << endl; for (auto e : lt) { cout << e << " "; } cout << endl; Print(lt); } struct A { A(int a1 = 0, int a2 = 0) :_a1(a1) , _a2(a2) {} int _a1; int _a2; }; void test_list2() { list lt; lt.push_back(A(1, 1)); lt.push_back(A(2, 2)); lt.push_back(A(3, 3)); lt.push_back(A(4, 4)); list::iterator it = lt.begin(); while (it != lt.end()) { cout << it->_a1 << " " << it->_a2 << endl; ++it; } cout << endl; } void test_list3() { list lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_front(5); lt.push_front(6); lt.push_front(7); lt.push_front(8); for (auto e : lt) { cout << e << " "; } cout << endl; lt.pop_front(); lt.pop_back(); for (auto e : lt) { cout << e << " "; } cout << endl; lt.clear(); lt.push_back(10); lt.push_back(20); lt.push_back(30); lt.push_back(40); for (auto e : lt) { cout << e << " "; } cout << endl; cout << lt.size() << endl; } void test_list4() { list lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); for (auto e : lt) { cout << e << " "; } cout << endl; list lt1(lt); for (auto e : lt1) { cout << e << " "; } cout << endl; list lt2; lt2.push_back(10); lt2.push_back(20); lt2.push_back(30); lt2.push_back(40); for (auto e : lt2) { cout << e << " "; } cout << endl; lt1 = lt2; for (auto e : lt1) { cout << e << " "; } cout << endl; } } int main() { bit::test_list4(); return 0; } - 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
- 413
-
相关阅读:
SpringIOC之support模块SimpleThreadScope
Qgis加载arcgis的gdb格式数据
【Python爬虫实战】 不生产小说，只做网站的搬运工，太牛逼了~（附源码）
BigDecimal运算使用方法(附简单案例)
Oracle自治事务详解
POSIX 标准头文件及unistd.h头文件说明
PyCharm中 python 类型文件被识别为Text文本类型
Springboot楼盘销售管理系统x1w9c计算机毕业设计-课程设计-期末作业-毕设程序代做
Python实践提！
Qt加Opencv实现 梯度矫正 功能
- 原文地址：https://blog.csdn.net/weixin_51799303/article/details/133278611
