哈希表总结
哈希表总结
常用数据结构总结
-
数组
有些时候， 使用数组可以直接充当简单的哈希表，
数组元素的下标作为 key 值，元素的值作为 value 值
比如统计一个单词各个字符出现的次数，因为字母 26 个数目是有限的，所以数组的下标也是有限的，可以轻松实现。使用数组的情况， 数组的下标一般都是有限的， 同时下标也要>=0，有些时候可以做适当的转换
-
set
set 包含头文件
set 为一个元素的集合，只存储键值，为有序集合---1 2 3 4 5unordered_set 包含头文件<unordered_set>
unordered_set 为无序集合，查找更高效--- 3 1 4 5 2multiset 包含头文件为
(不常用)
multiset 为有序集合，元素可重复，--- 1 1 2 3 3 4 5
有时候，也可以代替 map 的功能，如有元素个数有多个则插入多个相同元素 -
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）
有三种方式
-
直接使用下标的方式， 类似于数组的赋值
myMap['name'] = "peiqi";
-
使用 insert 加上 pair
myMap.insert(pair<string,string>("name","peiqi"));
-
使用 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 值删除
使用迭代器删除