C++中的unordered_map如何改写为长尾？

本文共计481个文字，预计阅读时间需要2分钟。

c#define LOG_N 3#define TABLE_SIZE (1 <

struct map_entry { int key; int value;};

struct map { struct map_entry *entries; int size; int log_size;};

// map初始化函数void map_init(struct map *m, int size) { m->size=size; m->log_size=size==1 ? 0 : 31 - __builtin_clz(size); m->entries=malloc(sizeof(struct map_entry) * TABLE_SIZE); if (!m->entries) { // 处理内存分配失败的情况 m->size=0; }}

// map销毁函数void map_free(struct map *m) { free(m->entries); m->entries=NULL; m->size=0; m->log_size=0;}

是一种特殊的map，查询键值的复杂度为O(1)，但是map查询键值的复杂度为O(log N)

有的编译器使用时要加入下面的头文件：

#if(__cplusplus == 201103L) #include <unordered_map> #include <unordered_set> #else #include <tr1/unordered_map> #include <tr1/unordered_set> namespace std { using std::tr1::unordered_map; using std::tr1::unordered_set; } #endif

下面看几个函数：

#include <bits/stdc++.h> #if(__cplusplus == 201103L) #include <unordered_map> #include <unordered_set> #else #include <tr1/unordered_map> #include <tr1/unordered_set> namespace std { using std::tr1::unordered_map; using std::tr1::unordered_set; } #endif using namespace std; const int maxn = 1e5 + 100; unordered_map<int, int> fa; int main() { fa[1]=2; fa[2]=3; fa[3]=4; fa[4]=0; //count函数 查询键值是否有值 返回0或者1 cout<<fa.count(5)<<endl;//0 cout<<fa.count(4)<<endl;//1 cout<<fa.count(3)<<endl;//1 if(fa.find(1)==fa.end()) cout<<"不存在"<<endl;//存在 else cout<<"存在"<<endl; if(fa.find(4)==fa.end()) cout<<"不存在"<<endl;//存在 else cout<<"存在"<<endl; if(fa.find(5)==fa.end()) cout<<"不存在"<<endl;//不存在 else cout<<"存在"<<endl; //遍历fa unordered_map<int,int>::iterator it; for(it=fa.begin();it!=fa.end();) { cout<<it->first<<" "<<it->second<<endl; ++it; } cout<<endl<<endl; //移除某个键值为奇数的元素 for(it=fa.begin();it!=fa.end();) { if(it->first%2==1) it=fa.erase(it); //删除之后指向下一个 else ++it; } for(it=fa.begin();it!=fa.end();) { cout<<it->first<<" "<<it->second<<endl; ++it; } return 0; }