向量
ADT(Aabstract data type)
抽象数据类型，数据模型+定义在该模型上的一组操作
DS(Data Structure)
数据结构, 基于某种特定语言，实现ADT的一整套算法
c/c++语言中，数组A[]中的元素与[0,n)内的编号一一对应。每个元素均可以有编号唯一指代，并可以直接访问，也称之为线性数组。
向量是数组的抽象与泛化，由一组元素按线性次序封装而成.
- 各元素与[0,n)内的秩一一对应 (循秩访问)
- 元素的类型不局限于基本类型
- 操作、管理更加简化、统一与安全
- 可更为便捷的参与复杂的数据类型的定制与实 现
向量ADT接口
| 操作 | 功能 | 适用对象 |
|---|---|---|
| size() | 报告向量当前的规模(向量长度) | 向量 |
| Get(r) | 获取秩为r的元素 | 向量 |
| put(r,e) | 用e替换秩为r元素的数值 | 向量 |
| insert(r,e) | e作为秩为r元素插入，原后继元素依次后移 | 向量 |
| Remove(r) | 删除秩为r的元素，返回该元素中原本存放的对象 | 向量 |
| disordered() | 判断所有元素是否已按非降序排列 | 向量 |
| sort() | 调整各元素位置，使之按非降序排列 | 向量 |
| find(e) | 查找目标元素e | 向量 |
| search(e) | 查找目标元素e，返回不大于e且秩最大的元素 | 有序向量 |
| deduplicate() | 剔除重复元素 | 向量 |
| Uniquify | 剔除重复元素 | 有序向量 |
| traverse() | 遍历向量并统一处理所有元素，处理方法由函数对象制定 | 向量 |
递增式扩容
最坏情况：在初始容量为0的空向量中，连续插入n=m*I >> 2个元素…
在1，I+1,2I+1..都需要扩容
装填因子：100%
加倍式扩容
最坏情况： 在初始容量为1的空向量中，连续插入$n=2^m >> 2$个元素
在1,2,4,8…都需要扩容
装填因子：50%