2. 第 2 章 抽象数据类型

1. 算法与数据结构应该以巧妙的方式结合起来，达到解决问题的目的，并提高效率。

2. 数据的静态组织和动态的操作算法，构成了ADT。一旦选择了某种数据结构，ADT的性能也可以确定。由此得知，抽象数据类型的挑选本质上是确定其数据结构。

3. 用数组存放数据，会出现空间超出不够用或浪费用不完的情况（即使是动态分配的数组，也会出现这种情况）。 vector 则很好的解决了这个问题（它是一个动态分配的数组，但是提供了很好的动态化策略）。

4. 如果数据在数组中有序存储，那么增删都会比较麻烦。（vector 在内存中也是连续存储的）。为了应对数据动态变化，必须要打破连续存储的物理形态，于是链表应运而生（ list 容器）。

5. 二叉查找树结合查找和链接，使得增删元素可以高效的实现。需要注意，平衡性是二叉查找树的重要指标，一旦失去平衡，查找效率就会急剧下降，可以限定结点的平衡程度来提升查找性能。

6. 在观察不同数据结构实现的同时，应该发现数据结构不仅给出静止的逻辑结构，更应该发现它给出了从一个状态到另一个状态的迁移规则。

7. 从不同的数据结构中进行选择，标准是通过分析完成任务的总时间来确定使用何种抽象数据类型。

8. STL是一套由模板写成的标准库，给出了多种常用的容器。容器可以说是抽象数据类型，它能容纳任何类型的对象，并在内部按照一定的数据结构将对象组织起来。

9.  向量容器vector 的使用基本与数组类似，但有点在于可以灵活伸缩，并有较好的性能。

10. 列表容器 list 可以操作表首和表尾，执行删除操作时需要判断 list 是否为空。只能操作表首和表尾的抽象数据类型叫做双端队列。

11. 栈容器 stack 可以执行 pop（删除栈顶元素），push（将新元素放在栈顶），top（返回栈顶元素）。

12.队列容器 queue 可以执行 pop（删除队首元素），push（将新元素放在队尾），front （返回队首元素）。

13. 优先级队列容器 priority_que 可以执行 pop （删除最大元素）， push （将新元素放入容器），top （返回容器中的最大元素）。优先队列使用的头文件也是 queue。

14. 集合容器 set 可以执行 insert（插入元素），erase（删除元素），find（查找元素）等。

15. 多重集合容器 mutilset 允许加入重复元素。mutilset 所使用的头文件也是 set。

16. 映射容器 map 是存储键值 pair 对象的集合。

17. 多重映射容器 mutilmap。

18. 迭代器： 不但可以隐藏容器复杂的内部结构，还能提高使用的便捷性并约束不当访问行为。（需要注意，访问受限的容器一般不提供迭代器）

19. 适配器：对现有的数据类型进行改装，提供新的接口。