C++中使用哈希表(unordered_map)的一些常用操作方法
C++标准库中使用的unordered_map底层实现是哈希表,下面这篇文章主要给大家介绍了关于C++中使用哈希表(unordered_map)的一些常用操作方法,需要的朋友可以参考下。
·
C++标准库中使用的unordered_map底层实现是哈希表,下面这篇文章主要给大家介绍了关于C++中使用哈希表(unordered_map)的一些常用操作方法,需要的朋友可以参考下
【参考】C++中使用哈希表(unordered_map)的一些常用操作方法
1.建立基本数据类型的哈希表
unordered_map<int,int> m; //<string,string>,<char,char>,数据类型任意
2.向哈希表中添加元素
1）.insert 函数
m.insert(pair<int,int>(1, 10));
m.insert(pair<int,int>(2, 20));
1：pair的定义
（1）：pair是将两个数据组合成一组数据，pair的实现其实是一个结构体，既然是将两个数据组合成一个数据，那么里面自然就有两个数据了，我们将其称之为成员变量，分别为first和second。
2：pair的操作以及使用
（1）定义pair类型：
//定义一个pair的基本格式
pair<p1,p2>name;
//在这里的p1和p2分别表示数据类型（就是int,char那些），这里的name表示你自己取得名字，就是这个是你定义的
//不过如果定义多个pair的话，我们会觉得太麻烦，会使用typedef来重命名
typedef pair<p1,p2>ua;
ua a;
//这里的ua就是类型的新名字了，a就是变量名字啦，后面会有代码例子具体给大家
2）pair的基本操作
其中的赋值操作直接使用=就可以了，只有它的first和second两个都相等才相等。
比较大小的话是按字典顺序来比较的，先比较first然后比较second，如果first不一样就不需要在比较second了
初始化pair的话可以在定义的时候直接初始化，也可以使用make_pair初始化，具体如何使用大家可以看看下面的代码，嘿嘿嘿！！！
#include<bits/stdc++.h>
using namespace std;
//因为定义pair比较繁琐，所以我一般用typedef重命名
typedef pair<int,string>au;
typedef pair<int,int>bu;
int main()
{
//初始化pair我一般使用两种
//第一种:直接初始化
au p1(1,"niubi");
//第二种，使用make_pair
au p2;
p2=make_pair(23,"iuiu");
//因为pair是将两个数据组合成一组数据，所有我们可以
//认为里面有两个数据，我们将它成为成员变量
//也就是first和second
cout<<p1.first<<" "<<p1.second<<endl<<p2.first<<" "<<p2.second<<endl;
au p3=make_pair(1,"sdd");
au p4=make_pair(1,"niubi");
if(p3==p1)cout<<"true"<<endl;
else cout<<"false"<<endl;
bool h=p3>p4;
cout<<h;
return 0;
}
2）.用数组方法直接添加
m[3]=30;
m[4]=40;
3.成员函数
begin(),end()函数
m.begin() //指向哈希表的第一个容器
m.end() //指向哈希表的最后一个容器，实则超出了哈希表的范围，为空
find()查找函数
m.find(2) //查找key为2的键值对是否存在 ,若没找到则返回m.end()
if(m.find(2)!=m.end()) //判断找到了key为2的键值对
count() 查找函数
m.count(3) //返回 1
m.count(5) //返回0
size()函数
m.size() //返回哈希表的大小
empty()函数
m.empty() //判断哈希表是否为空，返回值为true/false
clear()函数
m.clear() //清空哈希表
swap()函数
交换两个哈希表中的元素,整个哈希表的键值对全部都交换过去
unordered_map<int,int> m1;
unordered_map<int,int> m2;
m1.swap(m2);
swap(m1,m2);
4 哈希表的遍历
第一种遍历
unordered_map<int, int> count;
for (auto p : count) {
int front = p.first; //key
int end = p.second; //value
}
第二种遍历
unordered_map<int, int> count;
for(auto it=m.begin();it!=m.end();it++)
{
int front = it->first; //key
int end = it->second; //value
}
5 哈希 实际应用
5.2 字母异位词
LeetCode的242题：有效的字母异位词
题目描述：
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-anagram
具体的分析可以去看LeetCode上面的优质解答，那上面的最高赞，或者关注的人比较多的答案基本都是很优秀的解答和分析。这个问题的解法其中一个就是使用了unordered_map进行解决的：
t 是 ss 的异位词等价于「两个字符串排序后相等」
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
unordered_map<char, int> umap;
for (int i = 0; i < s.size(); ++i) {
umap[s[i]]++;
umap[t[i]]--;
}
for (auto ch : umap) { //ch是hash里面的内容值，不是下标
if (ch.second != 0) {//ch.first=char的内容，ch.second是键
return false;
}
}
return true;
}
};
测试
#include<iostream>
#include<unordered_map>
using namespace std;
int main()
{
vector<string> str = { "anagram","nagaram","rat","car","art","tar"};
bool res;
res = isAnagram(str[0], str[1]);
cout << res << endl;
res = isAnagram(str[2], str[3]);
cout << res << endl;
res = isAnagram(str[4], str[5]);
cout << res << endl;
}
2 两数之和
给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
示例1
输入：[3,2,4],6
返回值：[2,3]
说明：
因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回[2,3]
示例2
输入：[20,70,110,150],90
返回值：[1,2]
vector<int> twoSum(vector<int>& numbers, int target) {
// write code here
vector<int> res;
//创建哈希表，两元组分别表示值、下标
unordered_map<int, int> hash;
//在哈希表中查找target-numbers[i]
// for(auto i : numbers){//不能使用auto i，这里i是hash里的内容值，不是下标
for(int i = 0; i < numbers.size(); i++){
int temp = target - numbers[i];
//.find()查找temp的键是否存在 ,若没找到则返回.end(),end指向哈希表的最后一个容器，实则超出了哈希表的范围，为空；
//若没找到，将信息计入哈希表
if(hash.find(temp) == hash.end())
hash[numbers[i]] = i;
else {
//若在哈希表里，就将其下标和当前i，加1，作为返回结果(要返回两个加数的下标)
res.push_back(hash[temp] + 1);
res.push_back(i + 1);
break;
}
}
return res;
}
3 数组中出现次数超过一半的数字
数组中出现次数超过一半的数字
给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
int MoreThanHalfNum_Solution(vector<int> numbers) {
//无序哈希表统计每个数字出现的次数
unordered_map<int,int> hash;
//遍历数组
for(int i=0;i<numbers.size();i++){
if(hash.find(numbers[i]) != hash.end())
hash[numbers[i]]++;
else
hash[numbers[i]] = 1;
if(hash[numbers[i]] > numbers.size()/2)
return numbers[i];
}
return 0;
}
或
int MoreThanHalfNum_Solution(vector<int> numbers) {
//无序哈希表统计每个数字出现的次数
unordered_map<int,int> hash;
//遍历数组
for(int i=0; i<numbers.size();i++){
//哈希表中相应数字个数加1
hash[numbers[i]]++;
//一旦有个数大于长度一半的情况即可返回
if(hash[numbers[i]] > numbers.size()/2)
return numbers[i];
}
return 0;
}
4 哈希统计数组中，数字出现的次数
4.1
//哈希统计数组中，数字出现的次数
void num_count(vector<int> arr, unordered_map<int, int> &hash)
{
//遍历
for (int i = 0; i < arr.size(); i++)
{
//find寻找当前字符串是否在hash表里，如果一直找到表尾了，说明不存在;
if (hash.find(arr[i]) != hash.end())
hash[arr[i]]++; //若找到了，次数加一
else
hash[arr[i]] = 1; //若没找到，存入hash表，并且记录一次
}
}
测试
//哈希统计数组中，数字出现的次数
unordered_map<int, int> hash2;
vector<int> array = {1,2,3,2,2,2,5,4,2};
num_count(array, hash2);
for (auto& i : hash2)
{
cout << i.first << ":" << i.second << endl;
}
4.2
//哈希统计数组中，数字出现的次数
void num_count2(vector<int> arr, unordered_map<int, int>& hash)
{
for (int i = 0; i < arr.size(); i++)
hash[arr[i]]++; //统计每个元素出现次数
}
4.3
//哈希统计数组中，数字出现的次数
void num_count3(vector<int> arr, unordered_map<int, int>& hash)
{
for (auto num :arr) //num是数组中的元素，不是下标
hash[num]++; //统计每个元素出现次数
}
5 哈希统计字符串，出现的次数
//哈希统计字符串，出现的次数
void create(vector<string>vec,unordered_map<string,int>& hash)
{
for (int i = 0; i < vec.size(); i++)
{
//find寻找当前字符串是否在hash表里，如果一直找到表尾了，说明不存在;
if (hash.find(vec[i]) != hash.end())
hash[vec[i]]++; //若找到了，次数加一
else
hash[vec[i]] = 1; //若没找到，存入hash表，并且记录一次
}
}
测试
//哈希统计字符串，出现的次数
unordered_map<string, int> hash;
vector<string> vec = { "123","456","456","abc","456" };
create(vec, hash);
for (auto& i : hash)
{
cout << i.first << ":" << i.second << endl;
}
函数简化，貌似没问题
//哈希统计字符串，出现的次数
void create2(vector<string>vec, unordered_map<string, int>& hash)
{
for (int i = 0; i < vec.size(); i++)
hash[vec[i]]++; //若找到了，次数加一
}
6 hash去重
9.给定一个数据集，比如[1,2,3,4,2,3,2,4,5]写一个通用函数对数据进行清洗（去除重复项）。
vector<int> func(vector<int> &arr) {
unordered_map<int, int> hash;//hash去重
vector<int> res;
for (int i = 0; i < arr.size(); i++)
//如果arr[i]做为hash的键，若对应的值不在哈希表里，则将hash的键对应值赋为1，同时压入结果res;
if (hash.find(arr[i]) == hash.end()) {
hash[arr[i]] = 1;
res.push_back(arr[i]);
}
return res;
}
测试
int main() {
vector<int> arr = { 1,0,2,3,4,2,3,6,6,6,6,2,4,5 };
vector<int> res = func(arr);
for(int i : res)
cout << i << endl;
}
7 字符串中出现最多的字母
找出一段英文语句内出现最多的字母，比如：good evening,ladies and gentlemen,honorable judges and distinguished guest! 输出：e 。
char func2(string &str) {
unordered_map<char, int> hash;//hash计数
vector<int> res;
for (int i = 0; i < str.size(); i++)
hash[str[i]]++;
int max_count = hash[str[0]];
char ch;
for (int i = 0; i < str.size(); i++)
if ((str[i] != ' ' && str[i] !=',' && str[i] != '\0') && hash[str[i]] > max_count) {
max_count = hash[str[i]];
ch = str[i];
}
return ch;
}
测试
int main() {
vector<int> arr = { 1,0,2,3,4,2,3,6,6,6,6,2,4,5 };
vector<int> res = func(arr);
for(int i : res)
cout << i << endl;
string s = "good evening, ladiesand gentlemen, honorable judgesand distinguished guest!";
char ch = func2(s);
cout << ch << endl;
}
6 相关文章
C++深入探究哈希表如何封装出unordered_set和unordered_map
C++哈希表之线性探测法实现详解
C++基础算法基于哈希表的索引堆变形
C++ 实现哈希表的实例
C++语言实现hash表详解及实例代码
基于一致性hash算法 C++语言的实现详解
C++数据结构哈希表详解
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
34
0- 0
已为社区贡献5条内容
所有评论(0)