STL

STL之unordered_map

Posted by Liao on 2020-03-21

定义

​ 该容器提供了Key-Value的存储和查找功能

  • 无序性：unordered_map中的元素根据哈希值存储到桶中，以允许通过键直接快速访问每个元素

  • 唯一性：unordered_map中每个元素的值是唯一的

  • 关联性：unorederd_map 是一个关联容器，其中的元素根据键来引用，而不是根据索引来引用。

    插入值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<unordered_map>
using namespace std;

int main(){
     unordered_map<int,string> mymap;
     unordered_map<int,string>::iterator it;
     mymap.insert(make_pair(1,"LeetCode"));
     mymap.insert(make_pair(2,"HDU"));
     mymap.insert(make_pair(3,"OFFER"));
     for(it = mymap.begin(); it != mymap.end(); it++){
        cout << it->first << "," << it->second <<endl;
     }
}

/*
3,OFFER
2,HDU
1,LeetCode
*/

删除

1
2
3
4
5
6
7
8
    mymap.insert(make_pair(1,"LeetCode"));
    mymap.insert(make_pair(2,"HDU"));
    mymap.insert(make_pair(3,"OFFER"));
    mymap.erase(mymap.find(2),mymao.end());  //删除键为2之后的元素

/*
3,OFFER
*/

遍历

1
2
3
for(auto [k, v] : mp) {
	//...
}

容量查询

bool empty()

size_type size()

count()可以查询哈希表中是否有某个字符串

1
2
3
4
5
6
7
8
9
10
11
12
#include<unordered_map>
using namespace std;
int main()
{
    unordered_map<string,int> mp;
    mp.insert(make_pair("hello",1));
    if(mp.count("hello"))
        cout << "yes"<<endl;
    else
        cout << "no" <<endl;
}

unordered_map 和　map的比较

map相当于Java中的Treemap，而unordered_map相当于Hash_map

map底层为红黑树查找大致为logN的时间复杂度；unordered_map底层是闭散列的哈希桶，查找为O(1)，性能更优。

LeetCode 四数之和

求四个元组的和为0的个数

题目关键：四数（偶数个），和为0（用相反数）

思路：首先遍历并存储前两个集合每个元素之和，记录每个元素的和出现多少次。由于要判断四数之和为0，因此只需要遍历遍历剩下两个集合的和的相反数，在上面存储了多少个，累加起来即可。

这道题目用unordered_map很巧妙，原本用数组存储两数之和出现多少次，但是会出现负数，由于数组下表负数的话会出现越界，因此用unordered_map比较合适。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
    if(A.empty() || B.empty() || C.empty() || D.empty())
        return 0;
    unordered_map<int,int>arr; //可处理下标为负数　　<统计和　记录次数>
    for(int a : A){
        for(int b : B){
            arr[a+b]++;
        }
    }
    int ans = 0;
    int t;
    for(int c : C){
        for(int d :D){
            t = c + d;
            ans += arr[-t];
        }
    }
    return ans;
}

字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        unordered_map<string,int>mp;
        int cnt = 0;
        string tmp;
        for(string s : strs){
            tmp = s;
            sort(tmp.begin(),tmp.end());
            if(mp.count(tmp)){
                ans[mp[tmp]].push_back(s);
            }
            else{
                vector<string>vec(1,s);
                ans.push_back(vec);
                mp[tmp] = cnt++;
            }
        }
        return ans;
    }
FEATURED TAGS
STL
FRIENDS