1. 首页
  2. 文章中心
  3. STL 源码剖析

STL 源码剖析读书笔记三：序列式容器之 vector、list

104 阅读 0 评论
我是靠谱客的博主 机灵春天，这篇文章主要介绍STL 源码剖析读书笔记三：序列式容器之 vector、list，现在分享给大家，希望可以做个参考。

1. STL 中的容器

容器，置物之所也。STL 容器即是将运用最广的一些数据结构实现出来。如下图所示：

这里写图片描述

上图以内缩方式来表达基层和衍生层的关系。所谓衍生，并非派生关系，而是内含关系。例如 heap 内含一个 vector，priority-queue 内含一个 heap、stack、queue都内含一个 deque，set/map/multimap/multiset 都内含一个 RB-tree，hash_x 都内含一个 hashtable。

2. 序列式容器之 vector

所谓序列式容器，其中的元素都可序，但未必有序。

vector 的数据安排以及操作方式，与 array 非常相似。两者唯一的差别在于空间的运用灵活性。array 是静态空间，一旦配置了就不能改变，要换个更大（或小）的，就由客户端自己来：先配置一块新空间，然后将元素从旧址复制到新址，再把原来的空间释还给系统。vector 是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。

vector 实现的关键在于其对大小的控制以及重新配置时数据移动的效率。

2.1 vector 的定义

vector 的定义如下：

复制代码
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
class vector {
public:
  typedef T value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type* iterator;
  typedef const value_type* const_iterator;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  typedef reverse_iterator<const_iterator> const_reverse_iterator;
  typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  typedef reverse_iterator<const_iterator, value_type, const_reference, 
                           difference_type>  const_reverse_iterator;
  typedef reverse_iterator<iterator, value_type, reference, difference_type>
          reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
protected:
  typedef simple_alloc<value_type, Alloc> data_allocator; // SGI STL 空间配置器接口
  iterator start;               // 表示目前使用空间的头
  iterator finish;              // 表示目前使用空间的尾
  iterator end_of_storage;      // 表示目前可用空间的尾
  void insert_aux(iterator position, const T& x);
  void deallocate() {           // 释放空间
    if (start) data_allocator::deallocate(start, end_of_storage - start);
  }

  void fill_initialize(size_type n, const T& value) {
    start = allocate_and_fill(n, value);
    finish = start + n;
    end_of_storage = finish;
  }
public:
  // 各种迭代器
  iterator begin() { return start; }
  const_iterator begin() const { return start; }
  iterator end() { return finish; }
  const_iterator end() const { return finish; }
  reverse_iterator rbegin() { return reverse_iterator(end()); }
  const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
  reverse_iterator rend() { return reverse_iterator(begin()); }
  const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

  // size、max_size、capacity、empty
  size_type size() const { return size_type(end() - begin()); }
  size_type max_size() const { return size_type(-1) / sizeof(T); }
  size_type capacity() const { return size_type(end_of_storage - begin()); }
  bool empty() const { return begin() == end(); }
  // 重载 []
  reference operator[](size_type n) { return *(begin() + n); }
  const_reference operator[](size_type n) const { return *(begin() + n); }


  // 构造函数，大都调用 fill_initialize
  vector() : start(0), finish(0), end_of_storage(0) {}
  vector(size_type n, const T& value) { fill_initialize(n, value); }
  vector(int n, const T& value) { fill_initialize(n, value); }
  vector(long n, const T& value) { fill_initialize(n, value); }
  explicit vector(size_type n) { fill_initialize(n, T()); }

  vector(const vector<T, Alloc>& x) {
    start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());
    finish = start + (x.end() - x.begin());
    end_of_storage = finish;
  }
#ifdef __STL_MEMBER_TEMPLATES
  template <class InputIterator>
  vector(InputIterator first, InputIterator last) :
    start(0), finish(0), end_of_storage(0)
  {
    range_initialize(first, last, iterator_category(first));
  }
#else /* __STL_MEMBER_TEMPLATES */
  vector(const_iterator first, const_iterator last) {
    size_type n = 0;
    distance(first, last, n);
    start = allocate_and_copy(n, first, last);
    finish = start + n;
    end_of_storage = finish;
  }
#endif /* __STL_MEMBER_TEMPLATES */

  // 析构函数
  ~vector() { 
    destroy(start, finish);
    deallocate();
  }
  vector<T, Alloc>& operator=(const vector<T, Alloc>& x);
  void reserve(size_type n) {
    if (capacity() < n) {
      const size_type old_size = size();
      iterator tmp = allocate_and_copy(n, start, finish);
      destroy(start, finish);
      deallocate();
      start = tmp;
      finish = tmp + old_size;
      end_of_storage = start + n;
    }
  }

  // 首尾元素
  reference front() { return *begin(); }
  const_reference front() const { return *begin(); }
  reference back() { return *(end() - 1); }
  const_reference back() const { return *(end() - 1); }
  void push_back(const T& x) {
    if (finish != end_of_storage) {
      construct(finish, x);
      ++finish;
    }
    else
      insert_aux(end(), x);
  }
  void swap(vector<T, Alloc>& x) {
    __STD::swap(start, x.start);
    __STD::swap(finish, x.finish);
    __STD::swap(end_of_storage, x.end_of_storage);
  }

  // 插入操作
  iterator insert(iterator position, const T& x) {
    size_type n = position - begin();
    if (finish != end_of_storage && position == end()) {
      construct(finish, x);
      ++finish;
    }
    else
      insert_aux(position, x);
    return begin() + n;
  }
  iterator insert(iterator position) { return insert(position, T()); }
#ifdef __STL_MEMBER_TEMPLATES
  template <class InputIterator>
  void insert(iterator position, InputIterator first, InputIterator last) {
    range_insert(position, first, last, iterator_category(first));
  }
#else /* __STL_MEMBER_TEMPLATES */
  void insert(iterator position,
              const_iterator first, const_iterator last);
#endif /* __STL_MEMBER_TEMPLATES */

  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 pop_back() {
    --finish;
    destroy(finish);
  }

  //清除某位置上的元素
  iterator erase(iterator position) {
    if (position + 1 != end())
      copy(position + 1, finish, position); // 后续元素往前移动
    --finish;
    destroy(finish);
    return position;
  }

  // 清除迭代器所指定的区间的元素
  iterator erase(iterator first, iterator last) {
    iterator i = copy(last, finish, first);
    destroy(i, finish);
    finish = finish - (last - first);
    return first;
  }

  // 重新设置 vector 大小，若设置值 new_size 大于当前 size，在尾端插入 x
  void resize(size_type new_size, const T& x) {
    if (new_size < size()) 
      erase(begin() + new_size, end());
    else
      insert(end(), new_size - size(), x);
  }
  void resize(size_type new_size) { resize(new_size, T()); }
  void clear() { erase(begin(), end()); }

protected:
  // 配置空间并填满内容，其中__STL_TRY、__STL_UNWIND 为异常相关的宏，在 stl_config.h 中定义
  iterator allocate_and_fill(size_type n, const T& x) {
    iterator result = data_allocator::allocate(n);
    __STL_TRY {
      uninitialized_fill_n(result, n, x);
      return result;
    }
    __STL_UNWIND(data_allocator::deallocate(result, n));
  }

#ifdef __STL_MEMBER_TEMPLATES
  template <class ForwardIterator>
  iterator allocate_and_copy(size_type n,
                             ForwardIterator first, ForwardIterator last) {
    iterator result = data_allocator::allocate(n);
    __STL_TRY {
      uninitialized_copy(first, last, result);
      return result;
    }
    __STL_UNWIND(data_allocator::deallocate(result, n));
  }
#else /* __STL_MEMBER_TEMPLATES */
  iterator allocate_and_copy(size_type n,
                             const_iterator first, const_iterator last) {
    iterator result = data_allocator::allocate(n);
    __STL_TRY {
      uninitialized_copy(first, last, result);
      return result;
    }
    __STL_UNWIND(data_allocator::deallocate(result, n));
  }
#endif /* __STL_MEMBER_TEMPLATES */


#ifdef __STL_MEMBER_TEMPLATES
  template <class InputIterator>
  void range_initialize(InputIterator first, InputIterator last,
                        input_iterator_tag) {
    for ( ; first != last; ++first)
      push_back(*first);
  }

  // This function is only called by the constructor.  We have to worry
  // about resource leaks, but not about maintaining invariants.
  template <class ForwardIterator>
  void range_initialize(ForwardIterator first, ForwardIterator last,
                        forward_iterator_tag) {
    size_type n = 0;
    distance(first, last, n);
    start = allocate_and_copy(n, first, last);
    finish = start + n;
    end_of_storage = finish;
  }

  template <class InputIterator>
  void range_insert(iterator pos,
                    InputIterator first, InputIterator last,
                    input_iterator_tag);

  template <class ForwardIterator>
  void range_insert(iterator pos,
                    ForwardIterator first, ForwardIterator last,
                    forward_iterator_tag);

#endif /* __STL_MEMBER_TEMPLATES */
};

2.2 vector 的迭代器

vector 维护的是一个连续的线性空间，所以不论其元素型别如何，普通指针 都可以作为 vector 的迭代器而满足所有必要条件，因为 vector 迭代器所需要的操作行为，如 operator*，operator->，operator++， operator–， operator+，operator-，operator+=， operator-=，普通指针天生就具备。vector 支持随机存取，而普通指针正有这样的能力。所以，vector 提供的是 Random Access Iterators。

复制代码
1
2
3
4
5
6
7
8
template <class T, class Alloc = alloc>
class vector
{
public:
    typedef T             value_type;
    typedef value_type*   iterator;
    ...
}

根据定义，如果客户端写出这样的代码：

复制代码
1
2
vector<int>::iterator ivite;
vector<Shape>::iterator svite;

则，ivite 型别就是 int*，svite 的型别就是 Shape*。

2.3 vector 的数据结构

vector 所采用的数据结构非常简单：连续线性空间。它以；两个迭代器 start 和 finish 分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器 end_of_storage 指向整块连续空间（含备用空间）的尾端：

复制代码
1
2
3
4
5
6
7
8
9
template <class T, class Alloc = alloc>
class vector
{
...
protected:
  iterator start;               // 表示目前使用空间的头
  iterator finish;              // 表示目前使用空间的尾
  iterator end_of_storage;      // 表示目前可用空间的尾
}

为了降低空间配置时的速度成本，vector 实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充。这便是容量（capacity）的概念。

添加新元素时，如果超出当时的容量，则容量会扩充至两倍，如果两倍容量仍不足，就扩充至足够大的容量。上述容量的扩张必须经历“重新配置、元素移动、释放空间”等过程。

2.4 vector 的构造和相关操作

vector 缺省使用 alloc 作为空间配置器，并据此定义出 data_allocator，为的是更方便的以元素大小作为配置单位：

复制代码
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
template <class T, class Alloc = alloc>
class vector {
...
protected:
  typedef simple_alloc<value_type, Alloc> data_allocator;
...
  void deallocate() {
    if (start) data_allocator::deallocate(start, end_of_storage - start);
  }

  void fill_initialize(size_type n, const T& value) {
    start = allocate_and_fill(n, value);
    finish = start + n;
    end_of_storage = finish;
}

public:
  vector(size_type n, const T& value) { fill_initialize(n, value); }

protected:
  iterator allocate_and_fill(size_type n, const T& x) {
    iterator result = data_allocator::allocate(n);
    __STL_TRY {
      uninitialized_fill_n(result, n, x);
      return result;
    }
    __STL_UNWIND(data_allocator::deallocate(result, n));
  }

构造函数调用 fill_initialize，fill_initialize调用 allocate_and_fill，allocate_and_fill 调用 uninitialized_fill_n，uninitialized_fill_n 会根据第一参数的型别特性，决定使用算法 fill_n() 或反复调用 construct() 来完成任务。

复制代码
1
2
3
4
5
6
7
8
  void push_back(const T& x) {
    if (finish != end_of_storage) {
      construct(finish, x);
      ++finish;
    }
    else
      insert_aux(end(), x);
  }

push_back：

push_back 插入元素 x，若还有备用空间，直接在备用空间上构造，并调整迭代器 finish。如果没有备用空间了，就扩充空间（重新配置、移动数据、释放原空间）：

复制代码
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
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
  // 还有备用空间
  if (finish != end_of_storage) {
    construct(finish, *(finish - 1));
    // 调整 finish
    ++finish;
    T x_copy = x;
    // 与 copy 本质相同，只是从后面复制,可以避免区间有重叠时覆盖数据的问题
    copy_backward(position, finish - 2, finish - 1);
    *position = x_copy;
  }
  // 已无备用空间
  else {
    const size_type old_size = size();
    const size_type len = old_size != 0 ? 2 * old_size : 1;
    // 以上配置原则为：
    // 如果原大小为0，则配置1；
    // 如果原大小不为0，则配置为原来2倍，前半段用来放置数据，后半段准备用来放置新数据
    iterator new_start = data_allocator::allocate(len);
    iterator new_finish = new_start;
    __STL_TRY {
      // 将原 vector 拷贝至新 vector
      new_finish = uninitialized_copy(start, position, new_start);
      // 为新元素设定初值 x
      construct(new_finish, x);
      // 调整 new_finish
      ++new_finish;
      // 将安插点的原内容也拷贝过来
      new_finish = uninitialized_copy(position, finish, new_finish);
    }

#       ifdef  __STL_USE_EXCEPTIONS 
    catch(...) {
      destroy(new_start, new_finish); 
      data_allocator::deallocate(new_start, len);
      throw;
    }
#       endif /* __STL_USE_EXCEPTIONS */
    // 析构并释放原 vector
    destroy(begin(), end());
    deallocate();
    // 调整迭代器
    start = new_start;
    finish = new_finish;
    end_of_storage = new_start + len;
  }
}

注意：一旦对 vector 的操作引起空间重新配置，指向原 vector 的所有迭代器就全部失效。

pop_back：

复制代码
1
2
3
4
  void pop_back() {
    --finish;
    destroy(finish);
  }

insert：

复制代码
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
template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {
  // 当 n != 0 才进行以下所有操作
  if (n != 0) {
    // 备用空间大于等于新增元素个数
    if (size_type(end_of_storage - finish) >= n) {
      T x_copy = x;
      const size_type elems_after = finish - position;
      iterator old_finish = finish;
      // 针对插入点后现有元素与新增元素个数的数量采取不同的操作
      // 插入点后现有元素个数大于新增元素个数
      if (elems_after > n) {
        uninitialized_copy(finish - n, finish, finish);
        finish += n;
        copy_backward(position, old_finish - n, old_finish);
        fill(position, position + n, x_copy);
      }
      // 插入点后现有元素个数小于等于新增元素个数
      else {
        uninitialized_fill_n(finish, n - elems_after, x_copy);
        finish += n - elems_after;
        uninitialized_copy(position, old_finish, finish);
        finish += elems_after;
        fill(position, old_finish, x_copy);
      }
    }
    else {
      // 备用空间小于新增元素个数（必须配置额外的内存）
      // 首先决定新长度：旧长度的2倍，或者旧长度+新增元素个数
      const size_type old_size = size();        
      const size_type len = old_size + max(old_size, n);
      // 配置新的 vector 空间
      iterator new_start = data_allocator::allocate(len);
      iterator new_finish = new_start;
      __STL_TRY {
        new_finish = uninitialized_copy(start, position, new_start);
        new_finish = uninitialized_fill_n(new_finish, n, x);
        new_finish = uninitialized_copy(position, finish, new_finish);
      }
#         ifdef  __STL_USE_EXCEPTIONS 
      catch(...) {
        // 如有异常发生，实现 commit or rollback 语义
        destroy(new_start, new_finish);
        data_allocator::deallocate(new_start, len);
        throw;
      }
#         endif /* __STL_USE_EXCEPTIONS */
      // 清除并释放旧的 vector
      destroy(start, finish);
      deallocate();
      // 调整迭代器
      start = new_start;
      finish = new_finish;
      end_of_storage = new_start + len;
    }
  }
}

erase：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
iterator erase(iterator position) {
  if (position + 1 != end())
    copy(position + 1, finish, position);
  --finish;
  destroy(finish);
  return position;
}
iterator erase(iterator first, iterator last) {
  iterator i = copy(last, finish, first);
  destroy(i, finish);
  finish = finish - (last - first);
  return first;
}

resize 和 clear：

复制代码
1
2
3
4
5
6
7
8
void resize(size_type new_size, const T& x) {
  if (new_size < size()) 
    erase(begin() + new_size, end());
  else
    insert(end(), new_size - size(), x);
}
void resize(size_type new_size) { resize(new_size, T()); }
void clear() { erase(begin(), end()); }

3. 序列式容器之 list

相对于 vector 的连续线性空间，list 就显得复杂许多，它的好处是每次插入或删除一个元素，就配置或释放一个元素的空间。因此，list 对于空间的运用绝对精准，一点也不浪费。而且对于任何位置的元素插入或删除，list 都是常数时间。

list 和 vector 是两个最常用的容器。在什么时机下选择哪一种容器，必须视元素的多寡、元素构造复杂度（有无 non-trivial copy construct，non-trivial copy assignmen operator）、元素存取行为的特性而定。

3.1 list 的节点、迭代器和数据结构

每一个设计过 list 的人都知道，list 本身和 list 的节点是不同的结构，需要分开设计。以下是 STL list 的节点结构：

复制代码
1
2
3
4
5
6
7
8
template <class T>
struct __list_node
{
    typedef void* void_pointer;    // 型别为 void*，其实可设为 __list_node<T>*
    void_pointer prev;
    void_pointer next;
    T data;
};

list_node_allocator(n) 表示配置 n 个节点空间。以下四个函数：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
protected:
  // 配置一个节点并返回
  link_type get_node() { return list_node_allocator::allocate(); }
  // 释放一个节点
  void put_node(link_type p) { list_node_allocator::deallocate(p); }

  // 产生一个节点，带有元素值
  link_type create_node(const T& x) {
    link_type p = get_node();
    __STL_TRY {
      construct(&p->data, x);
    }
    __STL_UNWIND(put_node(p));
    return p;
  }
  // 销毁一个节点
  void destroy_node(link_type p) {
    destroy(&p->data);
    put_node(p);
  }
...

list 提供许多构造函数，其中一个是默认构造函数，构造一个空的 list：

复制代码
1
2
3
4
5
6
7
8
9
10
...
protected
  void empty_initialize() { 
    node = get_node();
    node->next = node;
    node->prev = node;
  }
public:
  list() { empty_initialize(); }
...

其他构造函数与 vector 类似，调用 fill_initialize：

复制代码
1
2
3
4
5
6
7
void fill_initialize(size_type n, const T& value) {
  empty_initialize();
  __STL_TRY {
    insert(begin(), n, value);
  }
  __STL_UNWIND(clear(); put_node(node));
}

list 不再能够像 vector 一样以普通指针作为迭代器，因为其节点不保证在存储空间连续存在。list 的迭代器必须有能力指向 list 的节点，并有能力进行正确的递增、递减、取值、成员存取等操作。

由于 STL list 是一个双向链表，迭代器必须具备前移、后移的能力，所以 list 提供的迭代器是 Bidirectional Iterators。此外，list 的插入（insert）和接合 splice 都不会造成原有 list 迭代器失效，删除（erase）操作只会导致指向被删除的那个迭代器失效，其他迭代器不受影响。

以下是 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
template<class T, class Ref, class Ptr>
struct __list_iterator {
  typedef __list_iterator<T, T&, T*>             iterator;
  typedef __list_iterator<T, const T&, const T*> const_iterator;
  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) {}

  bool operator==(const self& x) const { return node == x.node; }
  bool operator!=(const self& x) const { return node != x.node; }
  // 迭代器取值，取的是节点的数据值
  reference operator*() const { return (*node).data; }

#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_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;
  }
};

3.2 list 的数据结构

SGI list 不仅仅是一个双向链表，还是循环双向链表。所以它只需一个指针，便可以完整表现整个链表：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 const value_type* const_pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef list_node* link_type;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

public:
  typedef __list_iterator<T, T&, T*>             iterator;
  typedef __list_iterator<T, const T&, const T*> const_iterator;
...
protected:
  link_type node;

让指针 node 指向刻意置于尾端的一个空白节点，node 便能符合 STL 对于“前闭后开”区间的要求，成为 last 迭代器，如下函数便可轻易完成：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// begin、end、rbegin、rend
iterator begin() { return (link_type)((*node).next); }
const_iterator begin() const { return (link_type)((*node).next); }
iterator end() { return node; }
const_iterator end() const { return node; }
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 

// empty、size、max_size
bool empty() const { return node->next == node; }
size_type size() const {
  size_type result = 0;
  distance(begin(), end(), result);
  return result;
}
size_type max_size() const { return size_type(-1); }

// front、back
reference front() { return *begin(); }
const_reference front() const { return *begin(); }
reference back() { return *(--end()); }
const_reference back() const { return *(--end()); }

3.3 list 的构造和相关操作

list 默认使用 alloc 作为空间配置器，并据此另外定义一个list list_node_allocator，为的是更方便地以节点大小配置单位：

复制代码
1
2
3
4
5
6
7
8
template <class T, class Alloc = alloc>
class list {
protected:
...
  typedef __list_node<T> list_node;
  typedef simple_alloc<list_node, Alloc> list_node_allocator;
...
}

list 的常见操作主要包括：insert、push_front、push_back、erase、pop_front、pop_back、clear、remove、unique、splice、merge、sort 等。

复制代码
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
// 在指定节点插入一个节点
iterator insert(iterator position, const T& x) {
  link_type tmp = create_node(x);
  tmp->next = position.node;
  tmp->prev = position.node->prev;
  (link_type(position.node->prev))->next = tmp;
  position.node->prev = tmp;
  return tmp;
}

// 插入一个节点，作为头节点
void push_front(const T& x) { insert(begin(), x); }

// 插入一个节点，作为尾节点
void push_back(const T& x) { insert(end(), x); }

// 删除指定节点
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);
}

// 删除头节点
void pop_front() { erase(begin()); }

// 删除尾节点
void pop_back() { 
  iterator tmp = end();
  erase(--tmp);
}

// 清空链表
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->next = node;
  node->prev = node;
}

// 移除指定值的元素
template <class T, class Alloc>
void list<T, Alloc>::remove(const T& value) {
  iterator first = begin();
  iterator last = end();
  while (first != last) {
    iterator next = first;
    ++next;
    if (*first == value) erase(first);
    first = next;
  }
}

// 移除数值相同的连续元素
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;
  }
}

// 将 [first,last) 内的所有元素移动到 position 之前，是一个非公开接口
void transfer(iterator position, iterator first, iterator last) {
  if (position != last) {
    (*(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;
  }
}

// 接合操作：将某连续范围的元素从一个 list 移动到另一个（或者同一）list 的某个定点
// 为了提供各种接口弹性，list<T>::splice 有许多版本
void splice(iterator position, list& x) {
  if (!x.empty()) 
    transfer(position, x.begin(), x.end());
 }
void splice(iterator position, list&, iterator i) {
  iterator j = i;
  ++j;
  if (position == i || position == j) return;
  transfer(position, i, j);
}
void splice(iterator position, list&, iterator first, iterator last) {
  if (first != last) 
    transfer(position, first, last);
}

// 将 x 合并到 *this 上，两个 lists 的内容都必须先经过递增排序
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();
  // 两个 list 都已是递增排序
  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);
}

// 翻转 list
template <class T, class Alloc>
void list<T, Alloc>::reverse() {
  // 若链表尾空或者只有一个节点，则不进行任何操作
  if (node->next == node || link_type(node->next)->next == node) return;
  iterator first = begin();
  ++first;
  while (first != end()) {
    iterator old = first;
    ++first;
    transfer(begin(), old, first);
  }
}

// list 不能使用 STL 的 sort 算法，必须使用自己的 sort，采用的是 quick sort
// 原因是 STL 算法 sort 只接受 RamdonAccessIterator
template <class T, class Alloc>
void list<T, Alloc>::sort() {
  // 若链表尾空或者只有一个节点，则不进行任何操作
  if (node->next == node || link_type(node->next)->next == node) return;
  list<T, Alloc> carry;
  list<T, Alloc> counter[64];
  int fill = 0;
  while (!empty()) {
    carry.splice(carry.begin(), *this, begin());
    int i = 0;
    while(i < fill && !counter[i].empty()) {
      counter[i].merge(carry);
      carry.swap(counter[i++]);
    }
    carry.swap(counter[i]);         
    if (i == fill) ++fill;
  } 

  for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1]);
  swap(counter[fill-1]);
}

最后

以上就是机灵春天最近收集整理的关于STL 源码剖析读书笔记三：序列式容器之 vector、list的全部内容，更多相关STL内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(69)

相关文章

STL 源码剖析读书笔记五：序列式容器之 heap、priority_queue、slist
STL 源码剖析读书笔记五：序列式容器之 heap、priority_queue、slist
Iterator迭代器遍历（List,Set,Map都通用）
Iterator迭代器遍历（List,Set,Map都通用）
python中的iter迭代
python中的iter迭代
go mongodb Iter迭代器示例
go mongodb Iter迭代器示例
STL 源码剖析读书笔记三：序列式容器之 vector、list
STL 源码剖析读书笔记三：序列式容器之 vector、list
【STL源码剖析】总结笔记（5）：认识迭代器的好帮手--list
【STL源码剖析】总结笔记（5）：认识迭代器的好帮手--list
STL源码剖析_读书笔记:第三章 迭代器概念与traits编程技法
STL源码剖析_读书笔记:第三章 迭代器概念与traits编程技法
STL源码剖析读书笔记 第3章 迭代器概念与traits编程技法
STL源码剖析读书笔记 第3章 迭代器概念与traits编程技法

评论列表共有 0 条评论

立即
投稿
返回
顶部