本篇文章参考 oi-wikicodeforces。文章内容为原创。
众所周知,unordered_map是C++11的一个新功能,他是最好在O(1)的时间复杂度中进行插入操作。

请注意!这是最好情况。最坏的情况是O(size()),CF可能会被hack、

C++11使用方法:

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int main() {
unordered_map<int,int> m;
unordered_map<int,int>::iterator it;
m[3]=4;
m[7]=9;
m[5]=6;
for(it=m.begin();it!=m.end();it++)
printf("%d %d\n",it->first,it->second);
return 0;
}

使用auto指针

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;
int main() {
unordered_map<int,int> m;
m[3]=4;
m[7]=9;
m[5]=6;
for(auto x:m)
printf("%d %d\n",x.first,x.second);
return 0;
}

如何在C++98中使用unordered_map

请注意:本人并未在NOIP赛事中测试,并未测试可行性

使用方式参考下方代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
#include<tr1/unordered_map>
using namespace std;
int main() {
tr1::unordered_map<int,int> m;
tr1::unordered_map<int,int>::iterator it;
m[3]=4;
m[7]=9;
m[5]=6;
for(it=m.begin();it!=m.end();it++)
printf("%d %d\n",it->first,it->second);
return 0;
}

如何卡成$O(n^2)$:可以参考一下文章;http://codeforces.com/blog/entry/62393
简单描述:unordered_map是使用hash的,如果每个值都进行哈希碰撞。那么就会出现$O(n^2)$的最坏情况。不过,根据G++版本的不同,他的hash值也可能不一样。gcc 6 or earlier, 126271 does the job, and for gcc 7 or later, 107897 will work
实例:大家可以看我创建在洛谷的一道个人题目https://www.luogu.org/problem/U84784
unordered_map不初始化随机值:https://www.luogu.org/record/23104830
map做法:https://www.luogu.org/record/23104851