哈希表总结

常用数据结构总结

1. 数组
   有些时候， 使用数组可以直接充当简单的哈希表，
   数组元素的下标作为 key 值，元素的值作为 value 值
   比如统计一个单词各个字符出现的次数，因为字母 26 个数目是有限的，所以数组的下标也是有限的，可以轻松实现。

   使用数组的情况， 数组的下标一般都是有限的， 同时下标也要>=0，有些时候可以做适当的转换

2. set
   set 包含头文件
   set 为一个元素的集合，只存储键值，为有序集合---1 2 3 4 5

   unordered_set 包含头文件<unordered_set>
   unordered_set 为无序集合，查找更高效--- 3 1 4 5 2

   multiset 包含头文件为(不常用)
   multiset 为有序集合，元素可重复，--- 1 1 2 3 3 4 5
   有时候，也可以代替 map 的功能，如有元素个数有多个则插入多个相同元素

3. map
   map 包含头文件

   unordered_map 包含头文件<unordered_map>

   mutlimap 包含头文件(不常用)

set 和 map 的常用方法

以 unordered_set 和 unordered_map 为例子

访问元素

根据 key 获取 value---用于 unordered_map
unordered_map 中访问元素可以直接通过下标进行访问，也就是通过 key 值来访问

如 myMap['a']

也可以通过迭代器来访问
auto it = myMap.find('a');
it->first
it->second

插入元素
unordered_set，插入 key 值
mySet.insert(key)

unordered_map，插入元素的（key,value）
有三种方式

1. 直接使用下标的方式， 类似于数组的赋值

   myMap['name'] = "peiqi";

2. 使用 insert 加上 pair

   myMap.insert(pair<string,string>("name","peiqi"));

3. 使用 insert 加上 value_type

   myMap.insert(map<string,string>::value_type("name","peiqi"));

   也可以结合 typedef，简化书写，如

   typedef std::unordered_map<int, int> Mymap;

   tempMap.insert(Mymap::value_type(nums[i], i));

查询元素
find---根据 key 值来查询元素，返回一个指向目标的迭代器

auto it = mySet.find('a');

if(it!=mySet.end()), 表示元素在集合内

*it;

auto it = myMap.find('a');

it->first;

it->second;

修改元素

对于 unordered_map， 可以直接使用下标进行修改
myMap["name"] = "qiaozhi"

也可以先用 find 获取迭代器指针 it，再用迭代器指针修改 it->second

删除元素

使用 erase

iterator erase(const_iterator Where);

iterator erase(const_iterator First, const_iterator Last);

size_type erase(const key_type& Key);//返回删除元素的个数

根据 key 值删除

使用迭代器删除