2021-11-21STL——array&deque

2021-11-21STL——array&deque

array实现用类对数组的封装，这样可以使用 algorithm 对其进行 *** 作。

其容量不可扩展。

使用 native pointer 作为 iterator，这点与 vector 一致。

如果申请一个大小为 0 的数组会自动扩充到 1 .

deque

map（T**）指向整个“控制中心”，每个控制中心的单元都指向存放元素的大块内存 buffer ，大块内存里面放置了元素。

iterator内含4个指针：
1）first（T*）—— buffer 开始的位置
2）last(T*)—— buffer 结束的位置
3）cur（T*）——当前元素的位置
4）node（T**）——当前 buffer 在“控制中心”对应的单元的位置

在64位系统下，一个 iterato r的大小为 4*8=32byte

一个 deque 的组成：
1）start 和 finish 两个 iterator
2）map（T**）指向”控制中心“的 pointer
3）一个统计有多少块 buffer 的 map_size

在64位系统下，一个空的 deque 的大小为 32 * 2 + 8 * 2 = 80

buffer size 的大小也就是一个缓冲区存放多少元素该如何决定呢？
如果有指定大小就使用指定的大小；
如果没有指定的大小就将元素的大小与 512 byte 比较
如果大于等于 512 byte 一个 buffer 就只存放一个元素。
如果小于 512 byte 一个 buffer 就存放 512/size 个元素。

deque 的 iterator 具有能够跳跃的特性

deque 的 insert（）函数

先判断是否在头端或者在尾端，是的话直接调用函数实现插入，否则使用辅助函数

判断插入点的位置是靠近头端还是更靠近尾端，如果更加靠近头端，就将插入位置前面的元素都向前挪动一格，如果更加靠近右端就将插入位置后面的元素都向后面移动一格。

deque的 *** 作符重载

获取 size 的时候，使用了 - 的 *** 作符重载

两个元素之间的间隔 = 第一块 buffer 的元素个数 + 中间间隔的 buffer 个数 * buffer 中含的元素的个数 + 最后一块 buffer 元素个数。

后置递增 / 递减符号调用前置 递增 / 递减函数

deque 如何模拟连续空间？
先判断目标位置和当前位置是否在同一个 buffer 里头，如果是就直接移动，如果不是，中间间隔了多少个 buffer
如果 offerset < 0 那一块儿有些没有看懂。

如果是 - 号就相当于 offerset 为负

容器 queue 和 stack 使用了 deque 的部分函数，如果其他的容器也有同名的函数可以调用，也可以作为 queue 和 stack 的底层实现。

无法获取 queue 和 stack 的迭代器，因为这两个容器不支持随机访问，只是简单的调用了底层实现的某些函数。