深入stl

六大部件：

分配器、容器、迭代器、算法、仿函数、适配器

容器是需要分配器帮助分配内存的但是可以不写（模板里有默认的）

迭代器就是泛化的指针

容器即为存放数据的各种数据结构

算法即为一些对数据的操作通常通过迭代器访问到容器

仿函数和适配器则是添砖加瓦帮助算法用迭代器跟容器进行交互

有些地方会很巧妙估计突破口就在这块地方

一大堆容器一大堆算法

怎么选选哪个最好

并没有答案否则直接提供最好的那个就够了无需提供这么多选择

前面也领会到了这些东西的选择应该是根据情况而定的

而怎么准确的选择到最合适的

就得在两块方面有理解

一是对于问题的分析知道要做什么该怎么做这是在算法课里要锻炼的思维

二是对这些容器和算法要知其所以然知道它内部是怎么做的才能更好贴合前面的分析结果才有选择的余地才有改进的可能

所以对stl的理解在某种程度上也是走算法路的一个基础

先从容器入手

这些容器内部是怎么样的结构是数组还是链表还是哈希或是堆我们不能只知道这个叫vector或是list 得知道其本质是什么内部元素是怎么样的关系才能选的出适合的算法

大致分为两种：

序列式容器、关联式容器

第三块的不定序容器其实也能分进关联式容器中

其实底层就是用哈希表做的

array很简单就是把数组封装成了类的形式定长

vector可以看出左闭右开实际是个可变长的数组

怎么做到可变长？分配器帮它做的事

deque双向队列

留下一个疑惑:为什么一个容器能做到一头能扩充，另一头也能扩充？

双向链表（内部其实是环状的）

单向链表

以上都是序列式容器

根据数据放进去的顺序进行排列

关联式容器

set和map

底层是用红黑树（高度平衡二分树）

map多了一个key 通过key找value

对于这两种而言

意思其实是为了表达元素不按固定的顺序进行存放

其内部就是哈希表

哈希表本来有很多种实现方式（数据结构里面了解过了）

但目前基本公认了这种方式（附议）

接下来深入容器去学以致用

06-深入stl