pb_ds 大法好
看到没有人用pbds就来普及一篇
对比起stl是真心快
pbds hash table官网pbds hash table
pbds提供两种算法cc_hash_table和gp_hash_table
cc_hash_table是拉链法
gp_hash_table是查探法
gp的结果是:用时: 641ms / 内存: 19628KB
cc的结果是:用时: 611ms / 内存: 11404KB
pbds的hash是支持find和operator的
不过使用时要注意命名空间,string是std的
typedef basic_string<char> string;
所以一定要当心
直接上代码:
#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define pbds __gnu_pbds
using namespace std;
pbds::gp_hash_table<string,int> h;
/*
cc的定义是
pbds::cc_hash_table<string,int> h;
*/
int main()
{
int n,ans;
cin>>n;
ans=n;
for (int i=1;i<=n;i++){
string a;
cin>>a;
h[a]++;
if (h[a]>1){ans--;h[a]=1;}
}
cout<<ans<<endl;
return 0;
}