第一讲
STL六大部件容器 分配器 算法 迭代器（泛化的指针） 仿函数 适配器
十种容器，头文件名字和容器名相同。
n要很大
标准库 “前闭后开”区间 range-based for statement (since c++ 11) auto keyword (since c++ 11) 容器 — 结构与分类 序列式容器 sequence containers array (c++11) vector测试程序编写经验：使用不同的命名空间；变量用到时定义，顶格书写，易于查找。
往后扩张，空间在其他地方两倍增加，然后复制数据。
分段连续：每次扩充一个buffer
【stack和queue都是deque的一种特殊情况。所以有人把它们看作一种适配器，而不是容器。】
标准库有sort算法，list容器有sort算法，用自己特有的。
forward-list(c++11) 单向链表标准库有sort算法，list容器有sort算法，用自己特有的。
【slist 单向链表
与forward-list一样，可是forward-list是c++提供的，可是slist是编译器很早之前提供的，它的头文件包含方式是：
#include
红黑树 高度平衡二叉树
set/multisetset：key就是value,value就是key
map/multimap unordered containers(c++11) 不定序容器（可以看做是一种关联式容器）
hash table 实现 separate chaining目前最好，用的最多0
分类：unordered set/multiset， unordered map/multimap
（之前叫做：hash_set/multiset/map/multimap）
容器有默认分配器
template
想要使用std::allocator以外的allocator，得自行#include
例如：#include
程序中使用：list
结论：在程序中使用容器，而不是分配器，因为直接用的话不好，指定分配多大内存的同时还要指定释放多大内存，非常不方便；如果有小量内存需求，使用malloc/free或者new/delete.
第二讲
源代码之分布源码之前 了无秘密
用得好 宝库 技巧、技术
安装位置：
E:mingw-w64mingw64libgccx86_64-w64-mingw328.1.0includec++bits
E:mingw-w64mingw64libgccx86_64-w64-mingw328.1.0includec++ext
OOP：企图将datas和methods关联在一起
GP：企图将datas和methods分开来
采用GP：
容器和算法团队可各自闭门造车，其间以迭代器沟通即可。
算法通过迭代器确定操作范围，并通过迭代器取用容器元素。
采用::sort()排序算法的容器的迭代器必须是随机访问迭代器，可以进行加减乘除操作。比如：vector。可是像list它有自己的排序算法，因为它的迭代器不是随机访问迭代器。
泛化：template
struct _type_traits {};
全特化：template <>
struct _type_traits {};
泛化：template
class vector
偏特化：template
class vector
效率高
特殊 范围
allocator:实际是对malloc与free进行包装，没有进行特殊设计。
alloc: gnu2.9中容器使用
malloc一次拿到很大的内存，cookie少很多
gnu4.9中容器不再使用alloc，改用之前的，可是它仍然存在，不过改名字为：_poor_alloc，不是std命名空间。
使用起来会有点复杂：
vector
a要用到b里面的功能，两种方法：a继承b,a复合b.
深度探索 list 迭代器需要遵循的原则 iterator traits（特性特征特质）用以分离class iterators 和 non-class iterators
类迭代器或者指针，类可以直接得到特性，指针不能，因此加一个中间层：iterator traits，加上模板的偏特化来实现。
容器的迭代器是指针。
array forward_listarray:数组 不可扩充，需指定大小 没有构造、析构函数
容器存储在连续空间，迭代器可以用指针来表现，不用设计class.
分段连续
如何模拟连续空间？deque iterators的功劳，迭代器操作符重载。
stack和queue都可选择list或deque作为底层结构，deque比较快。
stack或queue都不允许遍历，也不提供iterator。
编译器不会做全面性检查，合理的可以通过，当遇到不合理的时候才报错，如果没有写不合理的，是不会报错的。
平衡二分搜寻树
中序遍历 排序状态
value和key合一；
不能修改元素值， const_iterator指向的内容不能修改。
set的所有操作，都转呼叫底层红黑树的操作，从这层意义看，set未尝不是个容器适配器。
value包括key和data，每个元素的key不可以改，key可以改
通过pair
map独有operator[];multimap没有.
哈希冲突：一次 二次。。。换位置，可是计算效率低
后来采用：separate chaining，虽然list是线性搜索时间，如果list够小，搜寻速度仍然很快。否则，rehashing，链表变短，花时间。
哈希表大小是素数，rehashing之后的大小大概是原来的两倍。
c++11之后，hash_set/multiset/map/multimap改名为unordered_set/multiset/map/multimap
————————————————第三讲
从语言层面讲：容器、迭代器、仿函数、适配器和分配器是类模板，而算法是函数模板。
移动能力的分类：iterator category
random_access_iterator_tag（随机访问）：array,vector,deque 连续空间
bidirectional_iterator_tag：list, set, multiset, map, multimap
farward_iterator_tag：farward-list
unordered_set/multiset/map/multimap迭代器的种类取决于节点之间的链表是双向还是单向。
input_iterator_tag：istream_iterator（适配器）
output_iterator_tag：ostream_iterator（适配器）
array
算法的效率与是否能对iterator进行分类有很大关系。
算法源代码剖析 accumulate 累计 for each 对容器中元素做同样的事情 replace replace_if replace_copy（范围内所有等同于旧值者都以新值放到新区间，不符合者原值放入新区间） count count_if容器带有成员函数count()：
set/multiset/map/multimap, unordered_set/multiset/map/multimap
容器带有成员函数count()：
set/multiset/map/multimap, unordered_set/multiset/map/multimap
容器带有成员函数sort()：list, farward-list
算法sort()要求迭代器是可以随机访问的。
关于reverse iterator: rbegin(), rend()
先排序；由low_bound去做
仿函数 class里面重载（） 函数对象：仿函数创建出来的对象算术类 逻辑运算类 相对关系类 24个
仿函数functors的可适配（adaptable）条件：stl规定每个adaptable function 都应挑选适当者（unary_function binanry_function）继承之，因为function adapter将会提问问题。
已经存在的不错的东西修改一下，接口修改：参数数目、函数名称
仿函数 迭代器 容器适配器
抓住共性
两种方式：继承 复合
stack queue
函数适配器：binder2nd例：cout << count_if(vi.begin(), vi.end(), not1(binder2nd(less(), 40)));
主体：大的class
辅助函数：让使用者得以方便使用主体
includec++backwardbackward_warning.h
是过时的东西，用bind代替，可是还是可以用
仿函数包成一个适配器，然后传给算法
新型适配器 bind since c++11
