STL学习（自学手册+源码分析）

1.1 STL六大组件 功能与运用

1.容器（containers）：各种数据结构，如vector，list，deque,set,map，用来存放数据。STL容器是一种类模板（calss template ）。
2.算法（algorithm）：各种常用算法如sort、search、copy、erase等。STL算法是一种（函数模板）function template。
3.迭代器（iterators）：扮演容器与算法之间的“胶合剂”，是所谓的“泛型指针”。从实现角度看，迭代器是一种将*、->、++、–等指针操作重载的类模板，所有STL容器都附带有自己专属的迭代器。
4.仿函数（functors）：行为类似函数，可以作为算法的某种策略（policy）。是一种重载了函数调用运算符（）的class 或 class template。一般函数指针可以视为狭义的仿函数。
5.适配器（adapters）：一种用来修饰容器或仿函数或迭代器接口的东西。例如STL提供的queue和stack，虽然看似容器，但是实质是容器适配器，因为底层是用其他容器（例如deque）首先的。
6.配置器（allocators）：负责空间配置与管理。从实现的角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的类模板。

1.2容器结构与分类

1.序列式容器（每个元素都有确凿位置）
1）Array：数组 使用的是连续空间 固定大小。
2）vector：尾部可以扩充，分配器来实现自动扩充。
3）deque（双端队列）： 两端都可以插入
4）list（双向链表）：实际上也是双线环状的链表
5）forward_list（单向链表）：只能单向访问
2.关联式容器（key-value）
1）Set/Multiset：不可重复/可重复的集合（Key = Value），内部使用红黑树实现结构。
2）Map/Multimap：不可重复Map/可重复Map（允许拥有重复Key）
3.无序式容器（也是一种关联式容器）
底层实现使用的hashtable

1）unordered_Set/Multiset：无序集合 底层实现用hash。
2）unordered_Map/Multimap：无序Map，底层实现用hash。