在实现 TinySTL 过程中对思路的一些梳理，并不涉及代码（大概），如有兴趣可以跳至相关实现。所谓序列式容器，其中的元素都可序，但未必有序。很绕是吧，换句话说，序列式容器中的元素就像字典一样可以按索引依次访问，但是又跟字典不太一样，因为它不一定按某种排序规律（例如递增、递减）来存储，元素存储顺序仅仅与插入顺序一致，除非手动排序😉
2024-08-15 12:04:56
目录：
1.1 概述
1.2 迭代器
1.3 数据结构
2.1 概述
2.2 迭代器
3.1 概述
3.2 中控器
3.3 迭代器
1 vector
1.1 概述
vector与array非常相似，二者唯一的差别在于对空间运用的灵活性。array是静态空间，一旦配置了就不能改变，但不是说一定不可，只是如果我们要扩容，只能手动去 “配置新空间 / 数据移动 / 释放旧空间”，array内部是没有设置相应处理机制的。vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。因此，vector的实现技术关键在于其对空间大小的控制以及重新配置时的数据移动效率，稍后我们便可以看到 SGI vector 的空间配置策略
1.2 迭代器
vector维护的是一个连续线性空间，所以不论其元素型别为何，普通指针都可以作为vector的迭代器而满足所有必要条件，所以，vector提供的是 Random Access Iterator
1.3 数据结构
vector所采用的数据结构非常简单：线性连续空间。它以两个迭代器 start 和 finish 分别指向配置而来的连续空间中目前已使用的范围（大小），并以迭代器 end_of_storage 指向整块连续空间的尾端（容量）。容量通常会比大小大，以便预留一些备用空间来应对可能的扩充，一旦大小等于容量，便是满载，此时已经没有备用空间了，需要动态增加大小，也就是以原来大小的两倍另外配置一块空间，然后将原内容拷贝过来，并在原内容之后构造新元素，最后释放原来的空间。因此，对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器都失效，这是一个容易犯错的地方：
1 | std::vector<int> vec; |
vector是以元素大小为配置单位的
1.4 元素操作与空间配置
vector的元素操作对于理解其空间策略有着巨大的帮助，如insert()，从以下关于insert(position, n, x)的示例图中你可以得以一窥：
备用空间 2 >= 新增元素 2
插入点之后的现有元素个数 3 > 新增元素个数 2
插入点之后的现有元素个数 2 <= 新增元素个数 3
备用空间 < 新增元素，n == 3
《STL 源码剖析》中有这么一句话：注意，插入完成后，新节点将位于哨兵迭代器（上例之position，标识出插入点）所指之节点的前方——这是 STL 对于 “插入操作” 的标准规范。稍微有些绕，举个例子会好理解一些，例如
insert(position, 3)，它是在 position 这个迭代器所指的元素前面插入的，最终展示出来的元素顺序是 {…，3，position指向的元素，…}，而不是 {…，position 指向的元素，3，…}
2 list
2.1 概述
相较于vector的连续线性空间，list就显得复杂许多，它是由双向链表（double linked-list）实现的非连续线性空间。list对于空间的使用十分吝啬，一点也不浪费，每次插入或删除一个元素，就配置或释放一个元素空间。而且，在任何位置的元素插入或删除，list都是常数时间
2.2 迭代器
这里简单提及一下，由于list和list的节点是不同的结构，需要分开设计
list不能像vector一样使用普通指针作为迭代器，因为其节点不保证在存储空间中连续存在。list迭代器必须指向list的节点，并且其迭代器的行为必须进行重载，因为它的递增、递减、取值、成员存取等行为均是基于节点的结构的操作
由于list是双向链表，迭代器必须具备前移、后移的功能，所以list提供的是 BIdirectional Iterator
list有一个重要性质：insert()和splice()都不会造成原有的list迭代器失效。这对vector来说是不可思议的，根据上文的讲述，vector的操作一旦引起空间的重新配置，之前所有的迭代器都会失效，而list并不会在空间不足时做重新配置，这是由于list是非连续空间，当需要添加元素时直接将配置好的节点连接到list尾端即可，并不像vector需要 “配置新空间 / 数据移动 / 释放旧空间”
2.3 数据结构
我们需要注意的是，list不仅仅是双向链表，它还是环状的，而为了符合 STL 规范的 “前闭后开”区间，还刻意在环状链表的尾端加上了一个空白节点
list是以节点大小为配置单位的
2.4 元素操作与空间配置
list内部提供了一个所谓的迁移操作（transfer）：将某连续范围内的元素迁移到某个特定位置之前。这个操作是list很多复杂操作如 splice()、sort()、merge()的基础，并且理解了这个操作的实现细节，也就明白了list绝大数操作的原理，无非是节点间的指针移动而已
以下是transfer()的操作示意图：
3 deque
3.1 概述
vector是单向开口的连续线性空间，deque则是一种双向开口（在头尾均可以做元素的插入和删除）的连续性空间。
vector也可以在头部操作，但是其效率奇差无比，无法被接受，要知道 STL 是极其讲究效率的
deque和vectoe的最大差异，一在于deque允许于常数时间内在头端进行元素的插入或删除操作，二在于deque没有所谓容量（capacity）的概念，这是因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并连接起来
3.2 中控器
deque的最大任务，便是在分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。既曰分段连续线性空间，就必须由中央控制，而为了维护整体连续的假象，数据结构的设计及迭代器前进后退等操作都颇为繁琐
deque采用一块所谓的 map（注意，不是 STL 中的map容器）作为主控。这里所谓 map 是一小块连续空间，其中每个元素（称为节点 node）都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是deque的存储空间主体。以下示意图展示了中控器的结构：
3.3 迭代器
deque是分段连续空间，维护其整体连续的假象的人任务就落到了迭代器的operator++和operator--两个运算子身上
deque的迭代器必须能够指出分段连续空间（即缓冲区）在哪里，其次它必须能够判断自己是否处在其所在缓冲区的边缘，如果是，一旦前进或后退时就必须跳跃至下一个或上一个缓冲区，为了能够正确跳跃，deque必须随时掌握管控中心（map）
如下示意图所示的是deque的中控器、缓冲区、迭代器的关系：
由于迭代器内对各种指针运算都进行了重载操作，所以各种指针运算如加、减、前进、后退都不能直观视之。其中最关键的就是：一旦行进时遇到缓冲器边缘，要特别当心，视前进或后退而定，可能需要跳至下一个或上一个缓冲区
3.4 数据结构与空间配置
deque除了维护一个指向 map 的指针外，也维护 start，finish 两个迭代器，分别指向第一个缓冲区的第一个元素和最后一个喊冲区的最后一个元素。此外它也必须要记住目前的 map 大小，因为一旦 map 所提供的节点不足，就必须重新配置更大的一块 map
deque的缓冲区扩充操作相当繁琐，因此接下来将会采取分解成图的方式进行描述，以下示例图是在各种情况下deque的状态：
在最后端插入三个元素，最后一个缓冲区有够用的备用元素空间，不会引起缓冲区的再配置：
在最后端插入一个元素，尾端只剩一个元素备用空间，先配置一整块新的缓冲区，再构造新元素：
在最前端插入一个元素，先需要扩充 map，后续配置一整块新的缓冲区，再构造新元素：
在最前端插入两个元素，由于第一缓冲区尚有够用的备用元素空间，不会引起缓冲区的再配置，直接构造新元素即可：
上述的连环图解充分展示了deque的空间运用策略