14.1.3 查找并获取map中元素

14.1.4 从map中删除元素

14.1.5 map的基本操作函数

C++ Maps是一种关联式容器，包含“关键字/值”对
begin() 返回指向map头部的迭代器
clear(） 删除所有元素
count() 返回指定元素出现的次数
empty() 如果map为空则返回true
end() 返回指向map末尾的迭代器
equal_range() 返回特殊条目的迭代器对
erase() 删除一个元素
find() 查找一个元素
get_allocator() 返回map的配置器
insert() 插入元素
key_comp() 返回比较元素key的函数
lower_bound() 返回键值>=给定元素的第一个位置
max_size() 返回可以容纳的最大元素个数
rbegin() 返回一个指向map尾部的逆向迭代器
rend() 返回一个指向map头部的逆向迭代器
size() 返回map中元素的个数
swap() 交换两个map，不是一个容器中的元素交换，而是两个容器交换；
upper_bound() 返回键值>给定元素的第一个位置
value_comp() 返回比较元素value的函数

14.2 unordered_map

unordered_map是一种关联容器，通过键值和映射值存储元素。允许根据键值快速检索各个元素，其相比于map，其键值并不需要从小到大排序，所以开销较少。
在unordered_map中，键值一般用来唯一标识元素，而对应的值是一个对象关联到这个键的内容。键映射值的类型可能会有所不同。
在内部unordered_map的元素不以键值或映射的元素作任何特定的顺序排序，其存储位置取决于哈希值允许直接通过其键值为快速访问单个元素（具有恒定平均的平均时间复杂度）。
unordered_map容器map容器更快地通过键值访问他们的单个元素，虽然unordered_map一般都是比map通过其元素的一个子集范围迭代效率低。
unordered_map允许使用操作运算符（运算符[]）以其键值作为参数直接访问元素。

14.3 Set

一个集合（set）是一个容器，它其中所包含的元素的值是唯一的。集set和多集multiset的区别是：set支持唯一键值，set中的值都是特定的，而且只出现一次；而multiset中可以出现副本键，同一值可以出现多次。
set和map是非常相似的，主要的是差别是map是key和value的一个组合。

14.3.1 set的基本操作函数

begin() 返回指向第一个元素的迭代器
clear() 清除所有元素
count() 返回某个值元素的个数
empty() 如果集合为空，返回true(真）
end() 返回指向最后一个元素之后的迭代器，不是最后一个元素
equal_range() 返回集合中与给定值相等的上下限的两个迭代器
erase() 删除集合中的元素
find() 返回一个指向被查找到元素的迭代器，如果没找到则返回end()
get_allocator() 返回集合的分配器
insert() 在集合中插入元素
lower_bound() 返回指向大于（或等于）某值的第一个元素的迭代器
key_comp() 返回一个用于元素间值比较的函数
max_size() 返回集合能容纳的元素的最大限值
rbegin() 返回指向集合中最后一个元素的反向迭代器
rend() 返回指向集合中第一个元素的反向迭代器
size() 集合中元素的数目
swap() 交换两个集合变量
upper_bound() 返回大于某个值元素的迭代器
value_comp() 返回一个用于比较元素间的值的函数

14.4 Hash表实现

是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。如下图所示：
</kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxoNCBpZD0="1441-hash表结构">14.4.1 Hash表结构

哈希表一般是由数组+链表组成的，一个定长的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过Hash函数获得。

哈希表的初始化：


14.4.2 Hash函数

这里的Hash函数是可以通过取模得到（当然还有其他的取模方式）


14.4.3 查找

14.4.4 插入

14.5 并查集

并查集主要解决将属于同一组的元素所在的集合合并，并在其间反复查找一个元素在哪个集合中。比如有这样一道题：

记A与B相通为A-B，如果有如下几列： A-B, B-C, E-A, F-E, I-B … … , 问R是否能到达A

这一类问题近几年来反复出现在信息学的国际国内赛题中，看似并不复杂，不过用常规方法来解确非常麻烦，可是用并查集确能非常快速解决。所以对于没参加过ACM的同学来说，这个数据结构比较少见，我以前没见过也没用过，不过许多公司的笔试编程题确涉及到这些方面。
并查集一般是通过一个数组来实现，每个数组的值初化为其标号（表示数组项的先驱结点为其本身），每一次读入记录时，就将数组项pre的值标记为先驱结点（比如1和3相连，则将1项的根结点标记为3项的根结点，即pre[1]=pre[2]），所以并查集的操作主要包含插入join和查找根结点find两个操作。

int pre[1000]; // 存储结点（标号）的先驱结点（根结点） int find(int x) //查找先驱结点（根节点） { int r=x; while (pre[r]!=r) //返回根节点r r=pre[r]; int i=x , j ; while( i != r ) //路径压缩 { j=pre[i]; // 在改变上级之前用临时变量j记录下他的值 pre[i]=r; //把上级改为根节点 i=j; } return r ; } //判断x,y是否连通 //如果连通，就不用管了，如果不连通，则合并 void join(int x,int y) { int fx=find(x),fy=find(y); if(fx!=fy) pre[fx]=fy; }