2.1向量vector
1、接口与实现
2、Abstract Data Type vs. Data Structure
抽象数据结构=数据模型+定义在该模型上的一组操作
数据结构=基于某种特定语言，实现ADT的一整套算法
| 定义与实现 | 复杂度 | 存储方式 | |
|---|---|---|---|
| 抽象数据类型 | 抽象定义，一种定义 | 外部的逻辑特性，不考虑时间复杂性 | 操作&语义，不涉及数据存储方式 |
| 数据结构 | 具体实现，多种实现 | 内部的表示与实现与复杂度密切相关 | 完整算法，考虑数据的具体存储机制 |
3、从数组到向量
在c/c++语言中数组中每个元素都有编号一一对应，反之，每个元素均有非负编号唯一指代，并可直接访问
A[i]的物理地址=A+i×s，s为单个元素占用的空间量。（linear array）
向量是数组的抽象与泛化，由一组元素按照线性次序封装而成，各元素与[0，n)内的秩（rank）一一对应，元素类型不限于基本类型，操作、管理维护更加简化、同意与安全。
可更为便捷地参与复杂数据结构的定制与实现。
向量ADT接口(图片来自与课程截图)：