STL源码剖析笔记<六> 序列式容器-list

list

vector是以线性空间存储数据,list是由链表实现,每次插入,删除一个元素就配置或者释放一个元素空间,list对于空间的利用是精准不浪费的,对于任何位置元素的插入或者移除,List都是线性时间

list实现一些重要的特性

  • list是一个双向链表,而且还是一个环状的链表。
    在尾端之后加上一个空白节点,在代码种为node,便可以表示整个链表了。

    1
    2
    iterator begin(){return (link_type)((*node).next);}
    itreator end(){return node;}
  • 插入操作和接合操作都不会造成原有的list迭代器失效。
    这在vector是不成立的。因为vector的插入操作可能造成记忆体重新配置,导致原有的迭代器全部失效。甚至list的元素删除操作(erase),也只有“指向被删除元素”的那个迭代器失效,其他迭代器不受任何影响。

  • merge() 操作需要两个list内容都经过排序,
  • reverse() 将链表逆序
  • sort() List必须使用自己的sort(),因为STL算法sort() 只接受RamdonAccessIterator,SGI使用的quick sort
  • 内部函数transfer是将连续范围的元素从一个List移动到另一个(或同一个)list的某个定点之前

list的源码分析

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
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
////////////////////////////////////////////////////////////////////////////////
// list结点, 提供双向访问能力
////////////////////////////////////////////////////////////////////////////////
// -------- -------- -------- --------
// | next |---------->| next |---------->| next |---------->| next |
// -------- -------- -------- --------
// | prev |<----------| prev |<----------| prev |<----------| prev |
// -------- -------- -------- --------
// | data | | data | | data | | data |
// -------- -------- -------- --------
////////////////////////////////////////////////////////////////////////////////
//list节点结构
template <class T>
struct __list_node
{
typedef void* void_pointer;
void_pointer next; //使用void* 为指针类型
void_pointer prev;
T data;
};
// 至于为什么不使用默认参数, 这个是因为有一些编译器不能提供推导能力,
// 而作者又不想维护两份代码, 故不使用默认参数
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef __list_iterator<T, T&, T*> iterator; // STL标准强制要求
typedef __list_iterator<T, Ref, Ptr> self;
typedef bidirectional_iterator_tag iterator_category; //双向迭代器
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef __list_node<T>* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
link_type node; //迭代器内部当然要有一个普通指针,指向list的节点
__list_iterator(link_type x) : node(x) {}
__list_iterator() {}
__list_iterator(const iterator& x) : node(x.node) {}
// 在STL算法中需要迭代器提供支持
bool operator==(const self& x) const { return node == x.node; }
bool operator!=(const self& x) const { return node != x.node; }
// 以下对迭代器取值(dereference),取的是节点的数据值
reference operator*() const { return (*node).data; }
// 以下是迭代器的成员存取运算子的标准做法
pointer operator->() const { return &(operator*()); }
// 前缀自加,对迭代器累加1,就是前进一个节点
self& operator++()
{
node = (link_type)((*node).next);
return *this;
}
// 后缀自加, 需要先产生自身的一个副本, 然会再对自身操作, 最后返回副本
self operator++(int)
{
self tmp = *this;
++*this;
return tmp;
}
// 前缀自减
self& operator--()
{
node = (link_type)((*node).prev);
return *this;
}
//后缀自减
self operator--(int)
{
self tmp = *this;
--*this;
return tmp;
}
};
////////////////////////////////////////////////////////////////////////////////
// list不仅是个双向链表, 而且还是一个环状双向链表
////////////////////////////////////////////////////////////////////////////////
// end() 头结点(node) begin()
// ↓ ↓ ↓
// -------- -------- -------- --------
// ---->| next |---------->| next |---------->| next |---------->| next |------
// | -------- -------- -------- -------- |
// | --| prev |<----------| prev |<----------| prev |<----------| prev |<--| |
// | | -------- -------- -------- -------- | |
// | | | data | | data | | data | | data | | |
// | | -------- -------- -------- -------- | |
// | | | |
// | | -------- -------- -------- -------- | |
// ---|-| next |<----------| next |<----------| next |<----------| next |<--|--
// | -------- -------- -------- -------- |
// ->| prev |---------->| prev |---------->| prev |---------->| prev |----
// -------- -------- -------- --------
// | data | | data | | data | | data |
// -------- -------- -------- --------
////////////////////////////////////////////////////////////////////////////////
// 默认allocator为alloc, 其具体使用版本请参照<stl_alloc.h>
template <class T, class Alloc = alloc>
class list
{
protected:
typedef void* void_pointer;
typedef __list_node<T> list_node;
// 专属之空间配置器,每次配置一个节点大小
typedef simple_alloc<list_node, Alloc> list_node_allocator;
public:
typedef T value_type;
typedef value_type* pointer;
typedef value_type& reference;
typedef list_node* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef __list_iterator<T, T&, T*> iterator;
protected:
link_type node ; // 只要一个指针,便可表示整个环状双向链表
// 分配一个新结点, 注意这里并不进行构造,
// 构造交给全局的construct, 见<stl_stl_uninitialized.h>
link_type get_node() { return list_node_allocator::allocate(); }
// 释放指定结点, 不进行析构, 析构交给全局的destroy
void put_node(link_type p) { list_node_allocator::deallocate(p); }
// 产生(配置并构造)一个节点, 首先分配内存, 然后进行构造
link_type create_node(const T& x)
{
link_type p = get_node();
construct(&p->data, x);
return p;
}
// 析构结点元素, 并释放内存
void destroy_node(link_type p)
{
destroy(&p->data);
put_node(p);
}
protected:
// 用于空链表的建立
void empty_initialize()
{
node = get_node(); // 配置一个节点空间,令node指向它
node->next = node; // 令node头尾都指向自己,不设元素值
node->prev = node;
}
// 创建值为value共n个结点的链表
// 注: commit or rollback
void fill_initialize(size_type n, const T& value)
{
empty_initialize();
__STL_TRY
{
// 此处插入操作时间复杂度O(1)
insert(begin(), n, value);
}
__STL_UNWIND(clear(); put_node(node));
}
public:
list() { empty_initialize(); }
// 链表成环, 当指所以begin()就是Node的下一个
iterator begin() { return (link_type)((*node).next); }
// 链表成环, 当指所以头节点也就是end
iterator end() { return node; }
// 头结点指向自身说明链表中无元素
bool empty() const { return node->next == node; }
// 使用全局函数distance()进行计算, 时间复杂度O(n)
size_type size() const
{
size_type result = 0;
distance(begin(), end(), result);
return result;
}
size_type max_size() const { return size_type(-1); }
reference front() { return *begin(); }
reference back() { return *(--end()); }
////////////////////////////////////////////////////////////////////////////////
// 在指定位置插入元素 ,是插入在position之前
////////////////////////////////////////////////////////////////////////////////
// insert(iterator position, const T& x)
// ↓
// create_node(x)
// p = get_node();-------->list_node_allocator::allocate();
// construct(&p->data, x);
// ↓
// tmp->next = position.node;
// tmp->prev = position.node->prev;
// (link_type(position.node->prev))->next = tmp;
// position.node->prev = tmp;
////////////////////////////////////////////////////////////////////////////////
iterator insert(iterator position, const T& x)
{
link_type tmp = create_node(x); // 产生一个节点
// 调整双向指针,使tmp插入进去
tmp->next = position.node;
tmp->prev = position.node->prev;
(link_type(position.node->prev))->next = tmp;
position.node->prev = tmp;
return tmp;
}
// 指定位置插入n个值为x的元素, 详细解析见实现部分
void insert(iterator pos, size_type n, const T& x);
void insert(iterator pos, int n, const T& x)
{
insert(pos, (size_type)n, x);
}
void insert(iterator pos, long n, const T& x)
{
insert(pos, (size_type)n, x);
}
// 在链表前端插入结点
void push_front(const T& x) { insert(begin(), x); }
// 在链表最后插入结点
void push_back(const T& x) { insert(end(), x); }
// 移除迭代器position所指节点
iterator erase(iterator position)
{
link_type next_node = link_type(position.node->next);
link_type prev_node = link_type(position.node->prev);
prev_node->next = next_node;
next_node->prev = prev_node;
destroy_node(position.node);
return iterator(next_node);
}
// 擦除一个区间的结点, 详细解析见实现部分
iterator erase(iterator first, iterator last);
void resize(size_type new_size, const T& x);
void resize(size_type new_size) { resize(new_size, T()); }
void clear();
// 删除链表第一个结点
void pop_front() { erase(begin()); }
// 删除链表最后一个结点
void pop_back()
{
iterator tmp = end();
erase(--tmp);
}
list(size_type n, const T& value) { fill_initialize(n, value); }
list(int n, const T& value) { fill_initialize(n, value); }
list(long n, const T& value) { fill_initialize(n, value); }
// 使用全局函数distance()进行计算, 时间复杂度O(n)
size_type size() const
{
size_type result = 0;
distance(begin(), end(), result);
return result;
}
~list()
{
// 释放所有结点
clear();
// 释放头结点
put_node(node);
}
list<T, Alloc>& operator=(const list<T, Alloc>& x);
protected:
////////////////////////////////////////////////////////////////////////////////
// 将[first, last)内的所有元素移动到position之前
// 如果last == position, 则相当于链表不变化, 不进行操作
////////////////////////////////////////////////////////////////////////////////
// 初始状态
// first last
// ↓ ↓
// -------- -------- -------- -------- -------- --------
// | next |-->| next |-->| next | | next |-->| next |-->| next |
// ... -------- -------- -------- ... -------- -------- -------- ...
// | prev |<--| prev |<--| prev | | prev |<--| prev |<--| prev |
// -------- -------- -------- -------- -------- --------
//
// position
// ↓
// -------- -------- -------- -------- -------- --------
// | next |-->| next |-->| next |-->| next |-->| next |-->| next |
// ... -------- -------- -------- -------- -------- -------- ...
// | prev |<--| prev |<--| prev |<--| prev |<--| prev |<--| prev |
// -------- -------- -------- -------- -------- --------
//
// 操作完成后状态
// first
// |
// --------------|--------------------------------------
// | ------------|------------------------------------ | last
// | | ↓ | | ↓
// -------- | | -------- -------- -------- | | -------- --------
// | next |-- | ----->| next |-->| next | | next |----- | -->| next |-->| next |
// ... -------- | | -------- -------- ... -------- | | -------- -------- ...
// | prev |<--- | ---| prev |<--| prev | | prev |<-- | -----| prev |<--| prev |
// -------- | | -------- -------- -------- | | -------- --------
// | | | |
// | ------ | |
// ------- | ------------------------------ |
// | | | |
// | | | -----------------------------
// | | | |
// | | | | position
// | | | | ↓
// -------- -------- | | | | -------- -------- -------- --------
// | next |-->| next |-- | | -->| next |-->| next |-->| next |-->| next |
// ... -------- -------- | | -------- -------- -------- -------- ...
// | prev |<--| prev |<--- ------| prev |<--| prev |<--| prev |<--| prev |
// -------- -------- -------- -------- -------- --------
////////////////////////////////////////////////////////////////////////////////
void transfer(iterator position, iterator first, iterator last)
{
if (position != last) // 如果last == position, 则相当于链表不变化, 不进行操作
{
(*(link_type((*last.node).prev))).next = position.node;
(*(link_type((*first.node).prev))).next = last.node;
(*(link_type((*position.node).prev))).next = first.node;
link_type tmp = link_type((*position.node).prev);
(*position.node).prev = (*last.node).prev;
(*last.node).prev = (*first.node).prev;
(*first.node).prev = tmp;
}
}
public:
// 将链表x移动到position所指位置之前
void splice(iterator position, list& x)
{
if (!x.empty())
transfer(position, x.begin(), x.end());
}
// 将链表中i指向的内容移动到position之前
void splice(iterator position, list&, iterator i)
{
iterator j = i;
++j;
if (position == i || position == j) return;
transfer(position, i, j);
}
// 将[first, last)元素移动到position之前
void splice(iterator position, list&, iterator first, iterator last)
{
if (first != last)
transfer(position, first, last);
}
void remove(const T& value);
void unique();
void merge(list& x);
void reverse();
void sort();
};
// 销毁所有结点, 将链表置空
template <class T, class Alloc>
void list<T, Alloc>::clear()
{
link_type cur = (link_type) node->next;
while (cur != node)
{
link_type tmp = cur;
cur = (link_type) cur->next;
destroy_node(tmp);
}
// 恢复node原始状态
node->next = node;
node->prev = node;
}
// 链表赋值操作
// 如果当前容器元素少于x容器, 则析构多余元素,
// 否则将调用insert插入x中剩余的元素
template <class T, class Alloc>
list<T, Alloc>& list<T, Alloc>::operator=(const list<T, Alloc>& x)
{
if (this != &x)
{
iterator first1 = begin();
iterator last1 = end();
const_iterator first2 = x.begin();
const_iterator last2 = x.end();
while (first1 != last1 && first2 != last2) *first1++ = *first2++;
if (first2 == last2)
erase(first1, last1);
else
insert(last1, first2, last2);
}
return *this;
}
// 移除容器内所有的相邻的重复结点
// 时间复杂度O(n)
// 用户自定义数据类型需要提供operator ==()重载
template <class T, class Alloc>
void list<T, Alloc>::unique()
{
iterator first = begin();
iterator last = end();
if (first == last) return;
iterator next = first;
while (++next != last)
{
if (*first == *next)
erase(next);
else
first = next;
next = first;
}
}
// 假设当前容器和x都已序, 保证两容器合并后仍然有序
template <class T, class Alloc>
void list<T, Alloc>::merge(list<T, Alloc>& x)
{
iterator first1 = begin();
iterator last1 = end();
iterator first2 = x.begin();
iterator last2 = x.end();
// 注意:前提是,两个lists都已经递增排序
while (first1 != last1 && first2 != last2)
if (*first2 < *first1)
{
iterator next = first2;
transfer(first1, first2, ++next);
first2 = next;
}
else
++first1;
if (first2 != last2)
transfer(last1, first2, last2);
}