STL与泛型编程第一周学习笔记——Boolan

在完成了STL与泛型编程第一周的学习之后，有一些总结和心得在这里通过学习笔记的方式分享出来，笔记我是跟着老师在视频中所讲的内容按照顺序记录的，也不能说是流水账，对课程中的一些问题还是添加了自己的理解和分析，供也在学习C++的小伙伴用作学习交流，如有理解不到位的地方，欢迎批评指正。

本周学习了STL，标准模板库（Standard Template Library）的六大部件（Components）:

容器（Containers）、分配器（Allocators）、算法（Algorithms）、迭代器（Iterators）、适配器（Adapters）、仿函式（Functors），它们之间的关系如下图所示，六大部件相互协作，完成标准模板库的功能。

本周主要介绍了容器（Containers）的结构与分类，对容器有了一个大致的了解，形成了一个分类的印象。

容器主要分为三类：Sequence Containers, Associative Containers, Unordered Containers Sequence Containers主要包含以下五种容器：

1.Array：固定了元素个数，前后封闭；

2.Vector：一端开口的数组，可增加元素个数，一端封闭，一旦内存不够便成倍扩充；

3.Deque：两端开口的队列，双向进出，一旦内存不够便扩充一个buffer；容器queque（先进先出）和stack（先进后出）也是由deque作为底层容器来支持；

4.List：双向链表，在空间上是非连续的，每个元素用双向指针串起来；

5.Forward-List：单向链表，用单向指针将元素串起来。

Associative Containers称为关联式的容器，其底层由高度平衡的二分树（红黑树）支持，用于需要大量查找时效率较高，主要包括以下两种容器：

1.Set/Multiset：是一种Key与value不分的红黑树，Set中的key不能重复，Multiset中的key允许重复；

2.Map/Multimap：是一种有key与value之分的红黑树，可以通过key来快速查找value，同样，Map中的key不能重复，Multimap中的key允许重复

Unordered Containers是一种无序排列的容器，其底层实际是由Hash Table支持的，分为Unordered Set/Multiset和Unordered Map/Multimap，各元素按照一定的编排方式挂在Hash Table的buckets上，再由单向链表将挂在同一个bucket上的元素串起来，bucket的个数一定大于元素的个数。

容器背后都会有一个分配器（Allocator）来支持容器的使用。