前两天提出的那个数据结构已经写程序实现. 发现不如我需要的理想, 今天又熬通宵做新的了.
首先说说我的需求: 我需要一个映射表, 好象 std::map 那 『More』
11 - 回复 | (2920) | 11 | 2016-10-14 05:11:04
aaaaaaa - 回复 | (2876) | aaa | 2016-02-22 04:20:07
补充一些粗略的测试结果 :)花了一通宵把前面的想法实现了. 自己写的简单的二叉排序树 + 一个可延展的数组 实现的一个字符串映射表.
30 万的随机字符串插入, 插入速度略快于 std::map 查找速度还是比 std::map 快一倍左右。
二叉排序树的容量为 16K 字节, 大约可以容纳为1千多个节点. (超过容量, 数里的内容将序列化到数组中)
不过因为字符串是均匀的随机的, 所以插入二叉排序树不会使之过于畸形。尚未测试畸形数据(比如按次序插入)的情况.