STL之关联容器（set /map /multiset /multimap)

资料备份

关联容器一般以平衡二叉搜索树作为内部数据结构，RB-tree的应用尤其广泛。
RB-tree是许多平衡二叉查找树的一种，一颗有n个内结点的红黑树的高度至多为2lg(n+1)，

它能保证在最坏情况下，基本的动态集合操作时间为O(lgn)。

关联容器支持通过键来高效地查找和读取元素，两个基本的关联容器是map和set。

set仅包含一个键，并有效地支持关于某个键是否存在的查询。

map的元素是“键-值”对的二元组形式：键用作元素在map中的索引，而值则表示所存储和读取的数据。

set和map类型的对象所包含的元素都具有不同的键。如果需要一个键对应多个实例，则需要使用multimap或multiset类型

具体的操作：

和顺序容器相比不支持元素访问的操作像front，back，at,operater[],

不支持修改器中的 asign ,pop_back,pop_front,push_front,push_back也不支持resize

还有顺序容器没有的key_comp,value_comp,find,count,lower_bound,upper_bound,equal_range 操作

学习资料记录：

STL 各容器对比表

Sequence containers			Associative containers
Headers			<vector>	<deque>	<list>	<set>		<bitset>
Members		complex	vector	deque	list	set	multiset	map	multimap	bitset
constructor	*	constructor	constructor	constructor	constructor	constructor	constructor	constructor	constructor
destructor	O(n)	destructor	destructor	destructor	destructor	destructor	destructor	destructor
operator=	O(n)	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operators
iterators	begin	O(1)	begin	begin	begin	begin	begin	begin	begin
	end	O(1)	end	end	end	end	end	end	end
	rbegin	O(1)	rbegin	rbegin	rbegin	rbegin	rbegin	rbegin	rbegin
	rend	O(1)	rend	rend	rend	rend	rend	rend	rend
capacity	size	*	size	size	size	size	size	size	size	size
	max_size	*	max_size	max_size	max_size	max_size	max_size	max_size	max_size
	empty	O(1)	empty	empty	empty	empty	empty	empty	empty
	resize	O(n)	resize	resize	resize
element access	front	O(1)	front	front	front
	back	O(1)	back	back	back
	operator[]	*	operator[]	operator[]	operator[]	operator[]
	at	O(1)	at	at
modifiers	assign	O(n)	assign	assign	assign
	insert	*	insert	insert	insert	insert	insert	insert	insert
	erase	*	erase	erase	erase	erase	erase	erase	erase
	swap	O(1)	swap	swap	swap	swap	swap	swap	swap
	clear	O(n)	clear	clear	clear	clear	clear	clear	clear
	push_front	O(1)	push_front	push_front
	pop_front	O(1)	pop_front	pop_front
	push_back	O(1)	push_back	push_back	push_back
	pop_back	O(1)	pop_back	pop_back	pop_back
observers	key_comp	O(1)	key_comp	key_comp	key_comp	key_comp
	value_comp	O(1)	value_comp	value_comp	value_comp	value_comp
operations	find	O(log n)	find	find	find	find
	count	O(log n)	count	count	count	count	count
	lower_bound	O(log n)	lower_bound	lower_bound	lower_bound	lower_bound
	upper_bound	O(log n)	upper_bound	upper_bound	upper_bound	upper_bound
	equal_range	O(log n)	equal_range	equal_range	equal_range	equal_range
unique members		capacity reserve	splice remove remove_if unique merge sort reverse	set reset flip to_ulong to_string test anynone

简单的例子：

http://developer.51cto.com/art/201107/275765.htm

夜风总结

http://blog.csdn.net/yfkiss/article/category/826423

jiahehao:

http://blog.csdn.net/jiahehao/article/category/342088

网站推荐：

http://www.cplusplus.com/