STL关联容器总结

有序的都不带unordered，即如下：

set multiset map multimap

其中带multi的表示关键字可以重复

无序的带unordered，如下：

unordered_map

unordered_set

unordered_multimap

unordered_multiset

map系有KEY和VALUE,set系只有KEY没有VALUE

4个有序容器的KEY必须重载<号，不然无法比较，内部实现为红黑树

4个无序容器的KEY必须重载==号和HASH函数，内部实现为哈希表

所有8个关联容器都有迭代器begin()、end()

set系的迭代器不能更改KEY，map的迭代器也不能改KEY，但可以改VALUE

map:

key_type:KEY类型

mapped_type:VALUE类型

values_type:pair类型【pair(key,value)类型】

set:

key_type和value_type类型是一样的，没有mapped_type类型

插入元素：

.insert()

.emplace()

map[x]=y;

删除元素：

.erase(VAL)		删除所有值为VAL的项，返回删除的元素个数

.erase(p)		删除p迭代器	返回p后面一个迭代器

.erase(b,e)		删除迭代器b到e的元素（不含e）返回e

查找元素：

非multi（单关键字）：

	.find(VAL)	返回迭代器，找不到返回.end()

	.count(VAL)		返回出现次数

multi(多关键字)：

	.find(VAL)返回第一个找到的迭代器

	有序容器：

	.lower_bound(K) 返回第一个KEY不小于K的迭代器

	.upper_bound(K) 返回第一个KEY大于K的迭代器

	无序容器只能用下面的这个（因为lower,upper显然对无序容器无意义），当然有序容器也能用下面的equal_range。

	equal_range(K)	返回一个pair，其中包含两个迭代器，指明等于KEY等于K的范围

巴特西