1. STL体系结构基础介绍

1.1 STL六大部件

分配器是负责支持容器的，帮容器分配内存。

与oop不同，数据保存在容器里，对数据的操作在算法里，中间的桥梁是迭代器（类似指针），

仿函数的作用类似一个函数，在仿函数中自定义你要进行的算法操作（相加，相乘，排序）。

适配器就是类似变压器，能够把输入的东西转换成我们需要的规格。

1.2 STL六大部件关系

vector 是一个容器， allocator<int> 是默认的分配器，这里显示写出来了，注意内部 <int> 要与 vector<int> 保持一致。

count_if() 是一个算法，用于统计满足某种情况的元素数量。内部的 vi.begin() 和 vi.end() 是两个迭代器，用来表示选定作用的区间（前闭后开）。

less<int>() 是一个仿函数，作用是比大小，a小于b则为真，但是这里的接口不对，我们需要a小于40，因此使用 bind2nd() ，它是一个仿函数适配器，用于绑定第二参数40，这里就变成a小于40。

not1()是一个仿函数适配器，作用是取反，让这里小于40的条件变为大于等于40。

综上，not1(bind2nd(less<int>()，40)) 组成了一个判别式，大于等于40就为真，将其作为 count_if 的第三个参数，就能帮我们找出符合要求的元素。

1.3 其它

• 复杂度

• 前闭后开

• range-based for statement(since C++11)

• auto keyword

2. 容器——结构与分类

2.1 Sequence Containers（序列容器）

Array是固定长度的数组，不能删除也不能扩充。

Vector起点固定，但是尾端是可以动态扩充的（一般是两倍增长）。

Deque双端队列，两头都可以扩充。

List双向链表，包含前向指针和后向指针，因此占用空间更大，在某些实现中是环形。

Forward-List单向链表，占用空间更少。

2.2 Associative Containers（关联容器）

关联容器默认按照key值排序，适合快速查找，底层使用红黑树实现，是一种平衡二叉树。

2.3 Unordered Containers（不定序容器，也是一种关联容器）

底层使用hash table实现，通过散列函数也可以做到O(1)的时间来查找值，但是如果冲突过多会退化到O(n)，因此现在常用的策略是哈希表上存放指针来指向对象，发生冲突在此对象基础上继续套娃，当然如果某一列过长则需要重新设计散列函数。

2.4 各种测试

• 测试程序的时候，可以使用namespace来区分，这样测试程序的变量名不会影响到正式程序。

• 头文件也写在每一个namespace的上面，而不是把所有头文件一股脑写在最上面，由于头文件有保护机制，相同的头文件并不会重复导入。

• push_front会把所有元素都往后移，包括构造、析构，时间消耗很大，因此最好使用尾插法push_back。

• 有时候快速排序+二分查找并不比直接sort快，但我个人认为直接sort快是因为运气好罢了。

• Forward-List和slist是一样的。

• stack和queue都是deque实现的，为了防止破坏各自的特性，这两种容器（严格来说是容器适配器）没有迭代器。

2.5 分配器之测试

模板都有第二个参数：默认分配器：std::allocator

GP

我不关心怎么比大小，因为比大小会触发操作符重载，由你自己定义

template<>表示特化

两个模板参数，但是确定一个模板参数，就是偏特化

分配器

allocator<int>()构建了一个临时对象，还的时候要告知借了多少，因此不太实用。

list

数据部分：node 两个指针

所有的容器的iterator都设计成一个类，才能足够“聪明”

i++ 和 ++i

i++有参数

int不允许两次后++，因此我们的后++重载传回来的不含reference。