STL源码剖析 读书笔记

set：所有元素根据键值自动被排列。而且不允许有相同的值

set的迭代器是不允许修改set元素值，会严重破坏set组织。iterator 是一种 constant iterators。删除和新增，不会使原来的迭代器失效（是因为，树以节点的形式存着，树的样子虽然在变，但是也是指针指向内容在变）

对于关联容器，应该使用容器提供的find，因为STL算法里的find，是按照顺序的。

map:也会根据元素的键值自动被排序。map不能修改键值，但是能修改value.

俩者不能重复，实现的机制是，RB-tree里的insert_unique;首先先查找，是否有对应的值，有的话就不插入了。真正插入的函数是__insert();

本来想谈谈map和set的区别，但是他的底层几乎一样，没啥区别可言了。。

hashtable:这种结构在插入、删除、搜寻等操作上具有“常数平局时间”

hash function：散列函数，最终要的东西，就是映射函数，问题是，会有碰撞问题。解决方法

线性探测：hash function算出来的已经被用了，则向下寻找，找完了去上面找，直到找到位置。

二次探测：线性是探测H+1，H+2，二次探测是探测H+1,H+4,H+9（好像假如表格大小为质数，且负载系数在0.5以下，探测次数不超过2，真tm的都行。。）

开链：就是拉链法。