C++中STL底层实现:vector、list和unordered_map_unorderedmap底层实现

1. unordered_map底层实现细节

哈希表实质上就是空间换时间。

最简单的方法就是创建一个大的数组，关键字就为下标索引，$a[i]==0$来查找元素

负载系数：元素个数/表格大小；（在0~1之间，除非采用开链的策略）

（1）线性探测方法：平均插入成本的成长幅度远高于负载系数的成长幅度。这主要是由于主集团的存在，使得发生冲突的概率增加，并且又会增长主集团的大小。

（2）二次探测：表格大小为质数，负载系数在0.5以下，可以确定插入新元素所需的探测次数不多于2。表格扩容时需要找到下一个质数(大约为原质数的两倍，并且重新计算哈希)

（3）开链做法：STL使用的方式

哈希表中存储的是一个链表指针。每个元素指向一个bucket
迭代器++操作时，如果到达bucket尾节点，则跳转至下一个bucket；（目前gcc的实现中，不光是bucket对应的节点采用链表相连，所有节点都是采用链表相连）

1.1. bucket数量变化策略

（1）缓存素数
之前的实现中是预先将一些质数计算好，缓存28个。
在gcc 9.4实现中，仍然是缓存好一些素数，这些素数由一个unsigned long数组__prime_list保存（数量为: 256 + xxx），查找时采用二分查找找到不小于__n的下一个素数；最大的bucket数量为 576460752303423487
（2）增长规则
通过哈希函数的_M_need_rehash方法（里面调用_M_next_bkt）计算出下一个bucket值，采用2倍的关系查找下一个bucket数量（实际上是max(element_size + increment, 2*cur_bucket_size)， 该值为上述函数参数中的__n）。
负载系数到1的时候，会进行重新哈希（不会对性能产生大的影响，java中默认值是0.75）
（3）不同初始化的情况
如果采用有参构造函数，即构造时指定数量，才会创建出2，3，5~13等素数的大小的bucket，如果采用的是默认构造函数创建，则在第一次插入元素时分配一个较大值。
，以下为bucket变化情况。

1.2.插入操作

node节点存储在一个数组中。（在SGI实现中为vector<node *>）

插入给定关键字key时，

1. 首先检测是否已经存在键值为key节点；若不存在，新建立一个node节点，执行插入。
2. 插入节点时，首先判断是否需要重建哈希表（调用_M_need_rehash函数）；
3. 若需要重建哈希表，则申请新的空间，并将原先空间中的节点，添加到新空间中。从原链表的头部删除，不断加入新链表的头部。
4. 总是插入在链表的头部

2.空间配置

将内存申请/释放，对象构造/析构拆分开
（1）SGI使用双层配置器
第一级直接使用malloc和free，
第二级维护一个内存池，处理小的请求；需求区块大于128字节，转到第一级。
具体而言，是采用分离的自由链表
（2）第二级配置器流程：申请一块大小为$n$的空间（为8的倍数）

1. 当对应的空闲链表有位置时，返回即可。
2. 当空闲链表中没有位置时，会从内存池中申请空间来填充空闲链表。
   会从内存池中申请一段较大的内存（默认为20个大小为$n$节点，根据内存池的大小，至少为1个），并将该内存划分为一个个大小为$n$的节点，组成单链表。
3. 当缓存池中没有空间时，会尝试调用malloc函数，从heap申请的内存至少为需求量的两倍以上；如果调用失败，会尝试从空闲链表中比$n$大的位置处获取一块内存空间填入到内存池中。如果还是失败就调用第一级配置器

3.迭代器

算法和容器的设计是分开的，迭代器作为中间件。

（1）在算法中很有可能用到迭代器指向对象的类型，那么如何获取迭代器指向对象的类型呢？

1. 可以采用函数模板的类型推导机制，但这种机制无法在返回值上使用。
2. 类中内嵌声明，在每个类中都声明一下指向的类型。访问时Class::value_type
   用在函数返回值上时，编译器并不知道value_type是成员函数、数据成员还是类型。此时就需要用到typename关键字了。
   typename和class的不同点：typename可以用来表明其为一个类型

（2）对于C++内置数据类型，无法在其中添加内嵌声明。解决办法是：采用一个模板类来专门表示类型信息。使用偏特化来特殊处理内置数据类型。

（3）迭代器相应类型
value type：迭代器指向对象的类型
difference type：迭代器之间距离的类型，可以用来表示容量。count返回值就是此类型

4. vector内存管理

（1）new 和 new[]的区别就是调用一次或多次构造函数。
delete 和 delete[]区别就是调用一次或多次析构函数。

（2）通过三个指针指示空间。_M_start、_M_finish即代表end()迭代器指向的位置、_M_end_of_storage。_M_finish指向_M_end_of_storage时，认为当前空间满。

（3）空间不足时调用_M_realloc_insert,在该函数中首先调用_M_check_len，其会判断当前大小是否大于max_size，若不是，则对当前空间加倍（实际上会判断std::max(size(), __n)，这里的__n为1，可认为是加倍）。根据返回的新大小申请一块新空间。

（4）在函数_M_realloc_insert中，复制原先空间内容到新空间时划分为三步：
先复制当前迭代器position对象
复制当前迭代器position之前的对象到新空间
复制当前迭代器position之后的对象到新空间
注意在向新空间复制元素时，会调用__uninitialized_move_if_noexcept_a函数，判断其移动构造函数是否被标记不抛出异常，若未标记，则调用复制构造函数；

这是因为空间扩张不一定是由push_back引起的，也有可能是插入的中间位置导致的。

（5）需要注意的是 删除元素时，并不会缩减空间。

（6）emplace_back中参数为万能引用（T&&），再通过完美转发到构造函数中（并不检测移动构造函数是否是noexcept）；push_back中若其参数为右值，也会调用emplace_back；

（7）resize会改变当前大小，如果比当前大小大，则调用默认构造函数在末尾添加元素，如果比size小，则截断元素。
与之相比，reserve负责空间调整，只有比当前容量大时才会起作用。

缩减空间的函数为shrink_to_fit，其功能为reduce capacity() to size(). 调用_M_reallocate重新分配内存空间。
at函数会调用_M_range_check，其会检查当前索引值是否大于 size()

（8）相比而言，array在初始化时需要指定大小，其是通过结构体中的_Type[_Nm]在栈区创建。

（9）swap其实就是交换三个指针，经常使用此技巧来和临时变量交换，以调用析构函数释放空间。clear和~vector()都会调用_Destroy析构vector中存储对象，但~vector()会额外调用基类的析构函数~_Vector_base()，其中调用_M_deallocate来释放vector本身占用的空间。

5. list内存管理

其为循环双向链表，使用额外的头结点（实际上位于整个链表的尾部，并且来代表end()迭代器的位置）来标识头尾节点及数量
（1） 在_List_node_base结构体中包含指针：_M_next和_M_prev，其hook函数就是将 新结点（this） 插入到position之前。

1. 头结点_List_node_header中还额外维护了链表大小，此节点实际上是链表end()返回的节点。其位于_List_base中，该类还负责节点空间的申请和释放，其节点为_M_impl._M_node
2. 存储值的节点_List_node

（2）基本函数

• 由于其是循环链表，begin()函数返回的是end()._M_next
• clear函数删除掉插入的数据节点，而不会删除掉_M_node节点，只是将其重置。
• 在emplace_back中使用了forward可以将参数类型完美转发到其他函数中（保持左值/右值）。这里是转发给_M_insert，然后再转发给_M_create_node，最终转发给构造函数
  之前没有forward时，需要实现两个重载函数，参数为右值引用的，需要调用std::move()传递给其他函数
• transfer函数是将原先链表中的一个或连续多个节点插入新链表中的this位置之前。
• remove函数中的细节：额外判断了当前迭代器地址是否与引用参数__value的地址一致，若一致，则先不进行删除，最后才删除。

（3）算法实现

• 在merge函数（会按照大小顺序合并链表）和splice函数底层都是调用上述transfer函数。这两个函数也都会改变原链表。
• sort函数，采用归并排序的思想。
  • 1.维护一个链表数组，数组中索引为$i$的位置存放的为排序好的并且节点数量为$2^i$，数组大小为64。（不太可能越界），就类似二进制进位的规则。
  • 2.从原先链表中不断删去头部结点，加入到临时变量中；
  • 3.从头开始扫描链表数组，当前索引为$i$
    若有结点，则调用merge进行合并，存储到临时变量处，接着进行循环；
    若无结点，直接结束循环，并存储到$i$处。
  • 4.当原链表为空时，结束循环，否则，跳到步骤2
  • 5.不断调用merge合并链表数组。
• reverse函数，循环双向链表的反转比较简单，遍历原链表，不断调用swap即可

6. 反向迭代器

（1）在list中

注意到调用rbegin()时，会使用end()创建反向迭代器。

在对反向迭代器取值运算时*reverse_iter，会执行如下运算，实际上取的是反向迭代器指向的前一个迭代器的值。

	_Iterator __tmp = current;
	return *--__tmp;
1
2

同理*rend()会实际返回的是list中的头结点的值。调用base()函数会返回其正向迭代器，主要是方便插入操作。

因此可以认为rbegin()指向最后一个元素，rend()指向第一个元素前面的空位置（list中的头结点）

 rend                  rbegin            反向迭代器表现出来的行为，理论指向
   |                     |
      1    2    3   4    5  header
      |                       |   
  rend.base()           rbegin.base()    反向迭代器内部实际指向
1
2
3
4
5

对于insert及erase等函数，是没有以反向迭代器作为参数的接口，因此必须在调用前述函数时调用base转换普通迭代器。
因此：
在插入时，会插入在riter逻辑指向的后面
在删除时，会删除在riter逻辑指向的后面的元素，若想删除riter逻辑指向的元素需要执行erase((++riter).base())