unordered_tire/README.md

C++ 无序字典树，字典树提供索引，值节点通过双向链表相连。

描述

目标：

1. 替换 unordered_map。
2. 获取特定前缀的子集合。
3. 使用接近 STL 库。
4. 优秀的查找速度。
5. 尽可能少的内存占用。

迭代器：

1. 迭代器快速遍历，但无法拿到 Key。
2. 树迭代器遍历字典树，可以拿到 Key。

思路

时间

1. 字典树提供索引功能.
2. 通过位图 bitmap 优化后继节点的析构。

空间

1. 在认识字典树的前提下, 通过 "2^8=2^4*2^4" 优化后继节点的数量。将 8 比特拆分为两个 4 比特，使得 (256个指针+其它部分) 变成 (16个指针+其它部分)*2。如果将字符流认作 8bits 为单位的字节流也可以正常运作。