STL标准库与泛型编程（侯捷）
本文是学习笔记，仅供个人学习使用。如有侵权，请联系删除。
参考链接
Github:STL源码剖析中源码 https://github.com/SilverMaple/STLSourceCodeNote/tree/master
Github:课程ppt和源码 https://github.com/ZachL1/Bilibili-plus
文章目录
介绍vector, array, deque, queue, stack的底层实现
16 vector深度探索
Vector将元素复制到内部的dynamic array中。元素之间总是存在一定的顺序，所以vector是一种有序集合（ordered collection）。 Vector支持随机访问，因此只要知道位置，你可以在常量时间内访问任何一个元素。 Vector提供随机访问迭代器，所以适用于任何STL算法。
如果你在末端附加或删除元素，vector的效率相当好。但如果你在前端或中段安插或删除元素，效率就不怎么样了，因为作用点之后的每一个元素都必须移到另一位置，而每一次移动都得调用assignment操作符。
Vector是动态数组，它会进行扩充，但不是原地扩充，而是当数组空间用完时，它会在某个地方重新分配内存空间（原来的两倍大小），再把先前的内容搬过去。
vector底部有三个指针，start, finish, end_of_storage
在C++中，std::vector 是一个动态数组，它的底层通常包含三个指针成员：start、finish 和 end_of_storage。
start: 这是指向数组的第一个元素的指针，表示 vector 的起始位置。finish: 这是指向数组最后一个元素的下一个位置的指针，表示 vector 当前存储的元素范围结束位置。注意，finish指向的位置是当前存储元素的末尾的下一个位置，而不是最后一个元素的位置。end_of_storage: 这是指向 vector 内存空间的末尾的下一个位置的指针。当 vector 的元素数量接近其容量时，end_of_storage可能指向当前分配内存的末尾。如果要添加更多的元素导致超过当前分配的内存空间，vector 可能需要重新分配更大的内存块，然后end_of_storage会被更新为新的内存块的末尾。
这些指针的作用是帮助 vector 进行动态内存管理。start 和 finish 之间的部分是当前 vector 存储的元素，而 finish 和 end_of_storage 之间的部分是 vector 预分配但尚未使用的内存空间。当 vector 的元素数量增加时，它可能需要重新分配内存，然后更新 end_of_storage 指针，以确保有足够的空间来容纳更多的元素。
现在看看两倍空间增长是怎么做的
下面是push_back的实现，当前分配的空间用完的时候，会调用insert_aux函数
insert_aux关于空间两倍增长的部分如下图所示
const size_type len = old_size != 0 ? 2 * old_size : 1;
下面的try catch里面就是具体的从旧位置把元素拷贝到新位置的源代码，分别是：把原vector的内容拷贝到新vector，然后为新元素赋值，新的finish指针后移，如果有insert函数，还需要把insert后面的元素复制过来。
后面还会把原来旧的vector空间释放掉
vector’s iterator
list的迭代器设计为一个class，这里vector的迭代器就是一个指针T *, 然后借助前面介绍的iterator_traits的偏特化（范围的偏特化，从接收T变成接收指针T *）,会把associated types里面的 value_type直接指定为T，而不是基于类的迭代器的I::value_type。下图是GNU C++2.9版本的内容
下面是对GNU C++4.9版本的vector的介绍：多了几个类，但是izeof(vector<T>)还是12B，因为vector继承自_Vector_base, 它里面有一个_Vector_impl的成员，它里面的data是三个指针，在32位电脑里面一个指针是4B，因此在32位电脑上vector的大小是12B。
GNU C++4.9版本的vector的iterator呢？
下图所示的设计很复杂，经过层层推导，可以看到_Iterator _M_current变量的类型也是_Tp*即上面GNU C++2.9版本的T*类型。
而且，GNU C++4.9版本的vector的iterator不再是G++2.9版本的指针T*，而是vector<T>::iterator，如下图箭头所指。
17 array、forward list深度探索
容器array
TR1：C++ TR1（Technical Report 1，技术报告 1）是一个介于 C++03 标准和 C++11 标准之间的阶段性技术报告，旨在为 C++ 标准库引入新功能和库组件提供一种机制。TR1 提供了一些 C++ 标准库的扩展，以及一些新的库组件，作为对 C++03 标准库的增强。
TR1 中的一些建议和组件后来被纳入 C++11 标准，成为了正式的 C++ 标准库的一部分。C++11 标准以及之后的版本中包括了 TR1 中的一些组件，例如 <memory>, <functional>, <random>, <tuple> 等。
这里介绍TR1版本的array实现
array的用法，需要指定array的大小
array<int, 10> myArray;
auto ite = myArray.begin();
ite += 3;
cout << *ite;
array的实现中没有构造函数和析构函数，GNU C++（g++） 2.9版本中直接拿原生指针当作迭代器， g++2.9版本的vector也是这种实现。
GNU C++ 4.9版本的array
容器forward_list
单向链表，下面的slide配合list学习。
std::forward_list 是 C++ 标准模板库（STL）中的一种单向链表容器。与 std::list 不同，std::forward_list 是一个单向链表，每个元素只保存指向下一个元素的指针，而不保存指向前一个元素的指针。
以下是一些 std::forward_list 的主要特点和操作：
特点：
- 单向链表：
std::forward_list是一个单向链表，每个元素只有指向下一个元素的指针。 - 没有 size() 函数： 由于是单向链表，
std::forward_list没有提供直接获取元素个数的 size() 函数。获取元素个数需要遍历整个链表。 - 高效插入和删除： 在链表中间插入或删除元素的操作比在其他序列容器中更加高效。
- 不支持随机访问： 由于是单向链表，
std::forward_list不支持通过索引直接访问元素。
18 deque、queue和 stack深度探索（上）
容器deque
std::deque（双端队列，deque 意为 double-ended queue）是 C++ 标准模板库（STL）中的一个容器，它提供了动态数组的功能，允许在两端进行高效的插入和删除操作。以下是关于 std::deque 的一些主要特点和概念：
双端操作：
std::deque允许在队列的两端（前端和后端）进行高效的插入和删除操作，而不仅仅是在尾部。动态数组：
std::deque的内部结构通常是由多个固定大小的块组成的，每个块中存储一定数量的元素。这种结构允许在两端执行常数时间的插入和删除操作，而不需要像动态数组那样移动大量元素。迭代器：
std::deque提供随机访问迭代器，可以在常数时间内对其元素进行随机访问。这使得std::deque在许多算法和操作中能够高效地使用。不要求连续存储： 与
std::vector不同，std::deque不要求元素在内存中是连续存储的。这使得在std::deque头部和尾部执行插入和删除操作更加高效。大小可变：
std::deque的大小可以动态调整，因此它可以根据需要动态分配和释放内存。
总体而言，std::deque 是一个强大的容器，适用于需要在两端进行高效插入和删除操作的情况。它提供了动态数组的灵活性，同时避免了由于频繁在中间插入或删除元素而引起的性能问题。
deque的内部：
首先有一个map（暂且称为控制中心），里面存储指针，指针指向各个缓冲区buffer（或者叫做node），缓冲区是数组，具体存储数据。缓冲区是连续的，但是不同的缓冲区之间不是连续的，所以称为分段连续。如下图所示，下图中有5个 buffer。
对于下图中的迭代器中的cur,first,last,node四个元素，first和last分别是一个buffer的起始和结束，node是控制中心中哪个buffer的指针，cur指向的是具体的元素值。
所有的容器都维护了两个begin() 和 end(), 就是下图中的迭代器start和finish，它里面也有上述四个元素。
下面看一下class deque的内容，它里面的数据有：
iterator start; // 16B，
iterator finish; // 16B
map_pointer map; // 4B，上面所说的控制中心
size_type map_size; // 4B， 控制中心这个vector的大小
上面的16 + 16 + 4 + 4 = 40B，这就是一个class deque创建出来的对象本身大小有40B（32位机器上），至于deque里面存储的数据占用的空间大小，是动态分配获得的，和对象本身大小无关。
再看下图的右上角，其中一个模板参数位 BufSiz, 这是GNU C++2.9版本，可以用来指定缓冲区的大小。
下图是iterator的成员（方框框起来的部分），可以看到map_pointer是 T**,它本身是一个指针，所以cur, first, last, node共计4 * 4B = 16B(在32位电脑上指针是4B大小)，这个就是上面iterator的大小。
下图中有
typedef random_access_iterator_tag iterator_category;
指定迭代器的类型是随机存取的类型，这就是deque对外表现：提供随机访问迭代器，可以在常数时间内对其元素进行随机访问。其实通过上面的学习，我们知道deque底层不是连续的，它是分段连续的。
下面看deque的insert函数
insert可以在指定位置插入元素，这一页ppt展示的是插入的位置在deque的头或尾，直接调用push_front和push_back，对于中间的插入放到下一页ppt中的insert_aux函数讲。
下面是insert_aux函数的具体讲解
由于deque是连续的，并且是可以双向扩充的，当插入一个元素（对应安插点）时，就要看一下，哪端元素少，要决定元素的移动是向前还是向后，然后再插入新值，这样速度更快。
19 deque、queue和 stack深度探索（下）
先看一下deque的函数：
reference front()
{
return *start;
}
reference back()
{
iterator tmp = finish; // 迭代器tmp赋值为finish，finish指向最后一个元素的下一个位置
--tmp;// 迭代器--，往前移动一格
return *tmp; // 此时返回的是最后一个元素
}
size_type size() const
{
return finish - start; // -操作符重载
//
}
这里是从源代码中的operator-的重载，摘录如下：
// _Deque_iterator里面的四个值
_Tp* _M_cur;
_Tp* _M_first;
_Tp* _M_last;
_Map_pointer _M_node;
difference_type operator-(const _Self& __x) const {
return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
(_M_cur - _M_first) + (__x._M_last - __x._M_cur);
}
// 每个buffer容纳的元素个数，buffer_size
inline size_t __deque_buf_size(size_t __size) {
return __size < 512 ? size_t(512 / __size) : size_t(1);
}
static size_t _S_buffer_size() {
return __deque_buf_size(sizeof(_Tp)); }
下面看deque如何模拟连续空间，主要是deque iterators的功劳
下面的_M_node - __x._M_node - 1中的_M_node指的是上图中的迭代器中的node节点，_M_node - __x._M_node - 1指的是控制中心两个node相减，得到是首尾buffer之间buffer的个数。(__x._M_last - __x._M_cur)指的是起始buffer的元素个数，就是下图中的97，98，99所在buffer的计算，这个buffer中右侧是元素，左侧是空白（目前还没有存数据）。(_M_cur - _M_first)指的是末尾buffer的元素个数，这个buffer左侧是数据，右侧是空白。
// 两个迭代器之间的距离：指的是多少个元素在两个迭代器之间
difference_type operator-(const _Self& __x) const {
return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
(_M_cur - _M_first) + (__x._M_last - __x._M_cur);
}
下面看++和–操作符重载：移动一个位置
_Self& operator++() {
++_M_cur;
if (_M_cur == _M_last) {
// 到达一个buffer的边界
// _M_node是控制中心的节点
_M_set_node(_M_node + 1); // 跳转到下一个buffer
_M_cur = _M_first;
}
return *this;
}
_Self operator++(int) {
_Self __tmp = *this;
++*this;
return __tmp;
}
_Self& operator--() {
if (_M_cur == _M_first) {
_M_set_node(_M_node - 1);
_M_cur = _M_last;
}
--_M_cur;
return *this;
}
_Self operator--(int) {
_Self __tmp = *this;
--*this;
return __tmp;
}
// 从一个buffer跳转到另一个buffer
void _M_set_node(_Map_pointer __new_node) {
_M_node = __new_node;
_M_first = *__new_node; // 指向新buffer的start
_M_last = _M_first + difference_type(_S_buffer_size()); //指向新buffer的last
}
deque号称是连续空间，迭代器可以跳过多个位置，所以迭代器提供+=的重载
当跳过多个位置跨越了当前buffer的边界，就会到另一个buffer，
_Self& operator+=(difference_type __n)
{
difference_type __offset = __n + (_M_cur - _M_first);
// 目标位置在同一个缓冲区buffer
if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
_M_cur += __n;
else {
// 目标位置不在同一个缓冲区buffer
difference_type __node_offset =
__offset > 0 ? __offset / difference_type(_S_buffer_size())
: -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
// 切换到正确的buffer
_M_set_node(_M_node + __node_offset);
// 切换至正确的元素
_M_cur = _M_first +
(__offset - __node_offset * difference_type(_S_buffer_size()));
}
return *this;
}
_Self operator+(difference_type __n) const
{
_Self __tmp = *this;
return __tmp += __n;
}
-=的重载调用上文的+=
_Self& operator-=(difference_type __n) {
return *this += -__n; }
_Self operator-(difference_type __n) const {
_Self __tmp = *this;
return __tmp -= __n;
}
// 连续空间需要提供下标操作符[]
reference operator[](difference_type __n) const {
return *(*this + __n); }
另外这里补充一下this 和 *this的区别：
bool operator==(const _Self& __x) const {
return _M_cur == __x._M_cur; }
bool operator!=(const _Self& __x) const {
return !(*this == __x); }
问题：这里的this是什么类型，*this是什么类型？
回答：
在C++中，this 是一个指向当前对象的指针。在成员函数中，this 指针被隐式地传递给成员函数，指向调用该成员函数的对象。因此，this 的类型是指向当前类类型的指针。
在上述代码中，*this 表示当前对象的解引用。由于 this 是指针，*this 就是该指针所指向的对象。因此，*this 的类型是当前类的对象类型。
具体来说，上述代码是一个用于比较不等于的运算符重载函数。*this 是当前对象，__x 是另一个对象。通过 *this == __x 这一比较操作，判断当前对象是否等于另一个对象。!(*this == __x) 表示当前对象不等于另一个对象，因此返回 true。这个重载函数的目的是实现 != 运算符，如果你已经在类中实现了 == 运算符，这个函数就是通过对 == 的结果取反来实现 !=。
g++4.9版本的deque
deque的类图如下图所示，也是deque继承自一个deque base，deque base有一个deque impl实现，这个deque impl有一个迭代器deque iterator。
新版本不允许用户指定缓冲区的大小，使用默认值512.
deque里面有四个成员变量
_M_map // 指向控制中心(这是一个vector)map，控制中心控制一块一块的缓冲区
_M_map_size // 控制中心的大小
// 两个迭代器
_M_start // 指向deque所有元素的头
_M_finish // 指向deque所有元素的尾
这里补充控制中心这个vector扩充的规则：
当vector空间满的时候，会自动两倍扩充空间，并且把旧的元素拷贝进新的两倍空间中，这里实现的时候，拷贝到新vector的中间部分，从而实现vector中间部分不仅可以向后扩张（记录新的缓冲区），而且还可以向前扩张（记录新的缓冲区），如下图右侧，中间控制中心（灰色）。
容器queue
std::queue 是 C++ 标准模板库（STL）中的一个容器适配器，用于实现先进先出（FIFO）的队列数据结构。它是建立在其他 STL 容器之上的一个封装，通常使用 std::deque 作为默认底层容器。
以下是 std::queue 的一些主要特点和操作：
先进先出（FIFO）：
std::queue实现了队列的基本特性，确保最先进入队列的元素最先被移出。容器适配器：
std::queue是一个容器适配器，意味着它不直接提供存储元素的能力，而是通过封装底层容器（默认是std::deque）来实现队列的行为。底层容器： 默认情况下，
std::queue使用std::deque作为底层容器，但你也可以通过模板参数来指定其他底层容器，比如std::list或std::vector。入队和出队操作：
std::queue提供了push方法用于将元素入队，pop方法用于将队首元素出队。std::queue<int> myQueue; myQueue.push(1); myQueue.push(2); myQueue.pop();队首和队尾访问：
front方法返回队首元素的引用，back方法返回队尾元素的引用。std::queue<int> myQueue; int frontElement = myQueue.front(); // 访问队首元素 int backElement = myQueue.back(); // 访问队尾元素大小和空判断：
size方法返回队列中的元素数量，empty方法检查队列是否为空。std::queue<int> myQueue; bool isEmpty = myQueue.empty(); // 检查队列是否为空
std::queue 提供了一种方便的方式来操作队列，尤其是在需要实现先进先出的场景下。它隐藏了底层容器的实现细节，使得队列的使用更加简单。
queue的源代码如下图，它调用deque中的各种方法实现自己的功能
容器stack
std::stack 是 C++ 标准模板库（STL）中的一个容器适配器，用于实现后进先出（LIFO）的栈数据结构。它是建立在其他 STL 容器之上的一个封装，通常使用 std::deque 作为默认底层容器。
以下是 std::stack 的一些主要特点和操作：
后进先出（LIFO）：
std::stack实现了栈的基本特性，确保最后入栈的元素最先被弹出。容器适配器：
std::stack是一个容器适配器，意味着它不直接提供存储元素的能力，而是通过封装底层容器（默认是std::deque）来实现栈的行为。底层容器： 默认情况下，
std::stack使用std::deque作为底层容器，但你也可以通过模板参数来指定其他底层容器，比如std::list或std::vector。入栈和出栈操作：
push方法用于将元素入栈，pop方法用于将栈顶元素出栈。std::stack<int> myStack; myStack.push(1); myStack.push(2); myStack.pop();栈顶访问：
top方法返回栈顶元素的引用。std::stack<int> myStack; int topElement = myStack.top(); // 访问栈顶元素大小和空判断：
size方法返回栈中的元素数量，empty方法检查栈是否为空。std::stack<int> myStack; bool isEmpty = myStack.empty(); // 检查栈是否为空
std::stack 提供了一种方便的方式来操作栈，尤其是在需要实现后进先出的场景下。它隐藏了底层容器的实现细节，使得栈的使用更加简单。
下面是stack的源代码，它也是调用deque的各个函数实现自己的功能
queue和stack，关于其iterator和底层结构
stack和queue都不允许遍历，不提供iterator
stack和queue都可以选择list或者deque作为底层结构，如下图所示，便是使用list作为底层结构
stack<string, list<string>> c;
queue<string, list<string>> c1;
stack可以选择vector作为底层结构
queue不能选择vector作为底层结构
stack和queue都不能选择set或map做底层结构
后记
截至2024年1月7日，学习完list, vector, deque, queue, stack的底层实现，接下来要学习基于红黑树的容器。
