STL源码剖析 5、关联式容器

关联式容器

树的导览

二叉搜索树：
●任何节点的值一定大于左子树中每一个节点的值，并小于右子树的每一个节点的值。
●从根一直往左，直到无左路可走，就是最小元素（换成右就是最大）
●高度可能不平衡，造成搜索效率低，用AVL树改进
●中序遍历有序（刷题用）

AVL树：加了额外平衡条件的二叉搜索树
●任何节点的左右子树高度差最多为1
●违反平衡条件时用单旋转、双旋转 调整

红黑树 RB-tree

性质：
●是二叉搜索树
●每个节点不是红色就是黑色
●根节点是黑色
●父子节点不能同时为红
●任意节点到叶子节点的路径所含黑节点数相同

各种算法：有点复杂，见书5.2
节点、迭代器、红黑树代码：见书

set

标准的STL set以RB-tree为底层机制，几乎所有的set操作行为都是转调用RB-tree的操作行为，如insert()、find()、count()

set的迭代器是const_iterator，无法写入

map

实现：map中以红黑树为底层机制，所有元素都为pair<const Key ,T>，pair的第一元素为键值（key），第二元素为实值（value）

template<class T1, class T2>
struct{
	typedef T1 first_type;
	typedef T2 second_type;
	T1 first;
	T2 second;
	pair() : first(T1()), second(T2()) {}	//不带参构造
	pair(const T1& a, const T2& b) : first(a), second(b) {}		//带参构造
}

只能修改second：

operator[]

T& operator[](const key_type& k){
	return (*((insert(value_type(k,T()))).first)).second;
	//value_type(k,T())产生一个型别相同的临时对象（value_type是pair）
	//insert返回一个pair，第一元素是迭代器（重复就不插入，指向重复的），第二元素是插入成功与否
	//对first解引用获得存储的pair
	//对pair再去second获得value
}

●如果[]作为左值运用（添加新元素），正好返回要填的位置的引用
●如果[]作为右值（根据键取值），恰好返回旧键值对的值

multiset

和set的区别就是插入采用的是insert_equal()而不是insert_unique()

multimap

和map的区别就是插入采用的是insert_equal()而不是insert_unique()

hashtable

基本原理：
 使用一个下标范围比较大的数组来存储元素。把关键字Key通过一个固定的算法函数即所谓的哈希函数（散列函数）转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标。
 为了避免哈希表太大，需要用到某种映射函数，将大数映射为小数，这种函数称为散列函数hash function。但hash function会带来碰撞问题，即不同的元素被映射到相同位置。

解决碰撞三种方法：
●线性探测：位置被占用了就往下一一寻找。插入多了后会浪费很多时候在解决碰撞上

●二次探测：位置被占用了就寻找i^2个，即H被使用的话寻找H+1,H+4,H+9…
 假设表格大小为质数，而且永远保持负载系数小于0.5（超过就重新配置），那么就可以确定没插入一个新元素所需要的探测次数不多于2

●开链法（hashtable使用）：在每一个表格元素中维护一个list，list搜寻是线性操作，但是list够短的话速度还是很快

template<class Value>
struct _hashtable_node
{
	_hashtable_node *node;
	Value val;
};

hashtable存取过程
hash_map，首先分配一大片内存，形成许多桶。是利用hash函数，对key进行映射到不同区域（桶）进行保存。其插入过程是：

1.得到key
2.通过hash函数得到hash值（有些类型需要自定义hash函数）
3.得到桶号(一般都为hash值对桶数求模)
4.存放key和value在桶内。
其取值过程是:
1.得到key
2.通过hash函数得到hash值
3.得到桶号(一般都为hash值对桶数求模)
4.比较桶的内部元素是否与key相等，若都不相等，则没有找到。
5.取出相等的记录的value。

hashtable代码见书5.7

hash_set（即unordered_set）

set由红黑树实现，hash_set由hashtable实现
set的元素有自动排序功能而hash_set没有（hash_set效率更高）

hash_map（即unordered_map）

map由红黑树实现，hash_map由hashtable实现
map的元素有自动排序功能而hash_map没有（hash_map效率更高）

hash_multiset

hash_set的insert_equal()变为insert_unique()，允许插入重复值

hash_multimap

hash_map的insert_equal()变为insert_unique()