因为之前写过一篇golang 数据类型分析的文章。包含slice、map、channel等。 想写一篇用其它语言实现golang数据类型的代码，于是选中map作为实验对象。 笔者之前写过5年的c++， 虽然 c++代码大概有3年没有写过了，但还是想试一试（可能是手痒痒。虽然写go很开心，但是也没有说对c++过河拆桥，偶尔还会想起以前gdb、makefile、linux kernel codeing、对照汇编指令集的日子）。
于是一边百度c++恢复功力，一边实现本文的代码，竟然大概用了2个小时。 目前实现的功能有：创建map(支持任意数据类型)、插入数据(自动扩容)、查询数据。数据删除和数据资源回收（在golang中是GC，在c++中就是析构函数对对象进行释放）后面有空再实现，时间不早准备休息了。关于c++百度的过程: 首先百度一下什么是类，尼玛? 结构体的元素默认是private的，而类的元素默认的public的。 好像得用模，模，模板? 绕不过去那就百度一把。 友元类? 我x，还好可以不用。 对[]操作符的重载? 纳尼，什么是重载??？这个不得不用一下，因为map需要想数组一样去索引。 用makefile还是用cmake好呢？思之再三没有想好。算了，单文件不如g++ filename吧，时间珍贵不要自己找事情，连-o都不用指定。就a.out吧。
目录结构：
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#