4
用c++实现一把golang里面的map数据类型
source link: https://studygolang.com/articles/35160
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
因为之前写过一篇golang 数据类型分析的文章。包含slice、map、channel等。 想写一篇用其它语言实现golang数据类型的代码，于是选中map作为实验对象。 笔者之前写过5年的c++， 虽然 c++代码大概有3年没有写过了，但还是想试一试（可能是手痒痒。虽然写go很开心，但是也没有说对c++过河拆桥，偶尔还会想起以前gdb、makefile、linux kernel codeing、对照汇编指令集的日子）。 于是一边百度c++恢复功力，一边实现本文的代码，竟然大概用了2个小时。 目前实现的功能有：创建map(支持任意数据类型)、插入数据(自动扩容)、查询数据。数据删除和数据资源回收（在golang中是GC，在c++中就是析构函数对对象进行释放）后面有空再实现，时间不早准备休息了。
目录结构：
c++代码：
// main.cc
#include <iostream>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <limits>
#include <time.h> // for nanosleep
#include <sys/time.h> // for gettimeofday
using namespace std;
using std::hash;
using std::string;
using std::cout;
class S {
public:
string first_name;
string last_name;
};
template<typename S>
class myhash
{
public:
size_t operator()(const S &s) const
{
size_t h1 = hash<string>()(s.first_name);
size_t h2 = hash<string>()(s.last_name);
return h1 ^ (h2 << 1);
}
};
template<typename KEY, typename VALUE>
class bmap {
public:
char topbits;
KEY key[8];
VALUE values[8];
//pad uintptr
//
void * overflow;
};
template<typename KEY, typename VALUE>
class TangMap
{
typedef bmap<KEY, VALUE> slot_node;
public:
TangMap(int slot_len=8) {
slot_num= slot_len;
buckets = (slot_node *)malloc(sizeof(slot_node) * slot_num);
slot_node * it = (slot_node *)buckets;
for (auto i=0; i<slot_num; i++) {
it->overflow = NULL;
}
count = 0;
//cout << "----:" << slot_num << endl;
printf("%p", buckets);
}
~TangMap() {
cout << "destruction function is invoked!" << endl;
}
void insert(KEY key, VALUE val) {
hash<KEY> hash_fn;
size_t slot_index = (hash_fn(key) & 0xff) % slot_num;
size_t subslot_index = ((hash_fn(key) >> 8) & 0xff) % slot_num;
cout << "slot_index is:" << slot_index << ", subslot_index is:" << subslot_index << endl;
auto it = &buckets[slot_index]; // 获取槽位头节点
for (;;) {
if (it->topbits & (1 << subslot_index)) {
cout << "--->bmap can not insert into this node" << endl;
if (it->overflow != NULL) {
it = (slot_node *)it->overflow;
continue;
} else {
auto node = new(slot_node);
node->overflow = NULL;
it->overflow = node;
it->key[subslot_index] = key;
it->values[subslot_index] = val;
it->topbits |= 1 << subslot_index;
count++;
break;
}
} else {
cout << "bmap can insert into this node" << endl;
it->key[subslot_index] = key;
it->values[subslot_index] = val;
it->topbits |= 1 << subslot_index;
printf("it->topbits=%d\r\n", it->topbits);
count++;
break;
}
}
printf("it->topbits=%d\r\n", it->topbits);
}
VALUE * operator[](KEY key) {
hash<KEY> hash_fn;
size_t slot_index = (hash_fn(key) & 0xff) % slot_num;
size_t subslot_index = ((hash_fn(key) >> 8) & 0xff) % slot_num;
cout << "slot_index is:" << slot_index << ", subslot_index is:" << subslot_index << endl;
auto it = &buckets[slot_index]; // 获取槽位头节点
for (;;) {
if (it->topbits & (1 << subslot_index)) {
if (key == it->key[subslot_index]) {
cout << "find key!" << endl;
return &it->values[subslot_index];
} else {
if (it->overflow != NULL) {
it = (slot_node *)it->overflow;
continue;
} else {
return NULL;
}
}
} else {
if (it->overflow != NULL) {
it = (slot_node *)it->overflow;
continue;
} else {
return NULL;
}
}
}
}
// 元素个数，调用 len(map) 时，直接返回此值
int count;
char flags;
int slot_num; // buckets 的对数 log_2
slot_node * buckets; // 指向内存的指针，可以看作是：[]bmap。 其大小为 2^B. 如果元素个数为0，就为 nil
void *extra;
};
inline int randf(void)
{
struct timespec tim;
tim.tv_sec=0; tim.tv_nsec=1e4;
nanosleep(&tim, 0);
struct timeval cur;
gettimeofday(&cur, 0);
srand(cur.tv_usec);
return rand()/float(RAND_MAX);
}
string randstr(char *str, const int len)
{
srand(time(NULL));
int i;
for (i = 0; i < len; ++i)
{
switch ((randf() % 3))
{
case 1:
str[i] = 'A' + randf() % 26;
break;
case 2:
str[i] = 'a' + randf() % 26;
break;
default:
str[i] = '0' + randf() % 10;
break;
}
}
str[++i] = '\0';
return str;
}
int main(int arcg, char **argv) {
const int LEN_NAME=40;
char name[LEN_NAME+1];
TangMap<std::string,string> obj;
for (auto i=0; i<40; i++) {
auto key = "key" + std::to_string(i);
auto val = "value" + std::to_string(i);
obj.insert(key, val);
auto v = obj[key];
printf("val is:%s, v is:%s\r\n\r\n", val.c_str(), v->c_str());
}
}
编译执行：
root@ubuntu:~/zz/map# g++ main.cc
root@ubuntu:~/zz/map#
root@ubuntu:~/zz/map# ./a.out
0x55ef79a2ce70slot_index is:4, subslot_index is:2
bmap can insert into this node
it->topbits=4
it->topbits=4
slot_index is:4, subslot_index is:2
find key!
val is:value0, v is:value0
slot_index is:2, subslot_index is:2
bmap can insert into this node
it->topbits=4
it->topbits=4
slot_index is:2, subslot_index is:2
find key!
val is:value1, v is:value1
slot_index is:4, subslot_index is:6
bmap can insert into this node
it->topbits=68
it->topbits=68
slot_index is:4, subslot_index is:6
find key!
val is:value2, v is:value2
slot_index is:2, subslot_index is:6
bmap can insert into this node
it->topbits=68
it->topbits=68
slot_index is:2, subslot_index is:6
find key!
val is:value3, v is:value3
slot_index is:6, subslot_index is:2
bmap can insert into this node
it->topbits=4
it->topbits=4
slot_index is:6, subslot_index is:2
find key!
val is:value4, v is:value4
slot_index is:0, subslot_index is:0
bmap can insert into this node
it->topbits=1
it->topbits=1
slot_index is:0, subslot_index is:0
find key!
val is:value5, v is:value5
slot_index is:7, subslot_index is:1
bmap can insert into this node
it->topbits=2
it->topbits=2
slot_index is:7, subslot_index is:1
find key!
val is:value6, v is:value6
slot_index is:5, subslot_index is:3
bmap can insert into this node
it->topbits=8
it->topbits=8
slot_index is:5, subslot_index is:3
find key!
val is:value7, v is:value7
slot_index is:4, subslot_index is:5
bmap can insert into this node
it->topbits=100
it->topbits=100
slot_index is:4, subslot_index is:5
find key!
val is:value8, v is:value8
slot_index is:3, subslot_index is:6
bmap can insert into this node
it->topbits=64
it->topbits=64
slot_index is:3, subslot_index is:6
find key!
val is:value9, v is:value9
slot_index is:5, subslot_index is:0
bmap can insert into this node
it->topbits=9
it->topbits=9
slot_index is:5, subslot_index is:0
find key!
val is:value10, v is:value10
slot_index is:5, subslot_index is:7
bmap can insert into this node
it->topbits=-119
it->topbits=-119
slot_index is:5, subslot_index is:7
find key!
val is:value11, v is:value11
slot_index is:0, subslot_index is:0
--->bmap can not insert into this node
it->topbits=1
slot_index is:0, subslot_index is:0
find key!
val is:value12, v is:value12
slot_index is:7, subslot_index is:2
bmap can insert into this node
it->topbits=6
it->topbits=6
slot_index is:7, subslot_index is:2
find key!
val is:value13, v is:value13
slot_index is:4, subslot_index is:4
bmap can insert into this node
it->topbits=116
it->topbits=116
slot_index is:4, subslot_index is:4
find key!
val is:value14, v is:value14
slot_index is:3, subslot_index is:1
bmap can insert into this node
it->topbits=66
it->topbits=66
slot_index is:3, subslot_index is:1
find key!
val is:value15, v is:value15
slot_index is:4, subslot_index is:1
bmap can insert into this node
it->topbits=118
it->topbits=118
slot_index is:4, subslot_index is:1
find key!
val is:value16, v is:value16
slot_index is:3, subslot_index is:5
bmap can insert into this node
it->topbits=98
it->topbits=98
slot_index is:3, subslot_index is:5
find key!
val is:value17, v is:value17
slot_index is:6, subslot_index is:1
bmap can insert into this node
it->topbits=6
it->topbits=6
slot_index is:6, subslot_index is:1
find key!
val is:value18, v is:value18
slot_index is:6, subslot_index is:6
bmap can insert into this node
it->topbits=70
it->topbits=70
slot_index is:6, subslot_index is:6
find key!
val is:value19, v is:value19
slot_index is:6, subslot_index is:1
--->bmap can not insert into this node
it->topbits=70
slot_index is:6, subslot_index is:1
find key!
val is:value20, v is:value20
slot_index is:2, subslot_index is:1
bmap can insert into this node
it->topbits=70
it->topbits=70
slot_index is:2, subslot_index is:1
find key!
val is:value21, v is:value21
slot_index is:5, subslot_index is:2
bmap can insert into this node
it->topbits=-115
it->topbits=-115
slot_index is:5, subslot_index is:2
find key!
val is:value22, v is:value22
slot_index is:5, subslot_index is:7
--->bmap can not insert into this node
it->topbits=-115
slot_index is:5, subslot_index is:7
find key!
val is:value23, v is:value23
slot_index is:0, subslot_index is:4
bmap can insert into this node
it->topbits=17
it->topbits=17
slot_index is:0, subslot_index is:4
find key!
val is:value24, v is:value24
slot_index is:5, subslot_index is:3
--->bmap can not insert into this node
bmap can insert into this node
it->topbits=8
it->topbits=8
slot_index is:5, subslot_index is:3
find key!
val is:value25, v is:value25
slot_index is:7, subslot_index is:2
--->bmap can not insert into this node
it->topbits=6
slot_index is:7, subslot_index is:2
find key!
val is:value26, v is:value26
slot_index is:6, subslot_index is:7
bmap can insert into this node
it->topbits=-58
it->topbits=-58
slot_index is:6, subslot_index is:7
find key!
val is:value27, v is:value27
slot_index is:0, subslot_index is:2
bmap can insert into this node
it->topbits=21
it->topbits=21
slot_index is:0, subslot_index is:2
find key!
val is:value28, v is:value28
slot_index is:1, subslot_index is:1
bmap can insert into this node
it->topbits=2
it->topbits=2
slot_index is:1, subslot_index is:1
find key!
val is:value29, v is:value29
slot_index is:0, subslot_index is:4
--->bmap can not insert into this node
bmap can insert into this node
it->topbits=16
it->topbits=16
slot_index is:0, subslot_index is:4
find key!
val is:value30, v is:value30
slot_index is:7, subslot_index is:1
--->bmap can not insert into this node
bmap can insert into this node
it->topbits=2
it->topbits=2
slot_index is:7, subslot_index is:1
find key!
val is:value31, v is:value31
slot_index is:6, subslot_index is:1
--->bmap can not insert into this node
bmap can insert into this node
it->topbits=2
it->topbits=2
slot_index is:6, subslot_index is:1
find key!
val is:value32, v is:value32
slot_index is:3, subslot_index is:5
--->bmap can not insert into this node
it->topbits=98
slot_index is:3, subslot_index is:5
find key!
val is:value33, v is:value33
slot_index is:7, subslot_index is:5
bmap can insert into this node
it->topbits=38
it->topbits=38
slot_index is:7, subslot_index is:5
find key!
val is:value34, v is:value34
slot_index is:2, subslot_index is:4
bmap can insert into this node
it->topbits=86
it->topbits=86
slot_index is:2, subslot_index is:4
find key!
val is:value35, v is:value35
slot_index is:7, subslot_index is:1
--->bmap can not insert into this node
--->bmap can not insert into this node
it->topbits=2
slot_index is:7, subslot_index is:1
find key!
val is:value36, v is:value36
slot_index is:5, subslot_index is:0
--->bmap can not insert into this node
bmap can insert into this node
it->topbits=9
it->topbits=9
slot_index is:5, subslot_index is:0
find key!
val is:value37, v is:value37
slot_index is:0, subslot_index is:4
--->bmap can not insert into this node
--->bmap can not insert into this node
it->topbits=16
slot_index is:0, subslot_index is:4
find key!
val is:value38, v is:value38
slot_index is:4, subslot_index is:4
--->bmap can not insert into this node
it->topbits=118
slot_index is:4, subslot_index is:4
find key!
val is:value39, v is:value39
destruction function is invoked!
root@ubuntu:~/zz/map#
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK