QP-Trie来自于 https://fanf.livejournal.com/137283.html

原始实现只支持\0结尾的数据，所以一个key不会是另一个key的前缀。参考 https://github.com/sdleffler/qp-trie-rs 进行改进，支持任意字符串数据。

一些实现细节，与原始C版本以及qp-trie-rs的对比

1. 使用了c++17的variant代替union。跟原始C语言版比起来，每个节点增加了额外字节消耗(variant中用于标识类型的字段)

2. 我之前仿照qp-trie-rs，在branch中用一个vector存放twigs。这样会额外引入16字节的空间消耗。后来还是用了原版c实现的方式，自己搞了个简单的动态数组，为了简化实现，从位域index中借用10比特作为动态数组的size和capacity。这样只能存储最长2^36字节的字符串，不过也够用了。现在一个branch固定消耗16字节，和C 版本一样

3. 由于使用了variant，节点不再是trivially_copyable，所以动态数组不能用realloc以及memove，与C版本比性能会有一定损失

4. 原始C语言版本只支持C风格字符串char*作为key。这里为了通用性，只要是满足std::is_convertible<std::string_view, T>的类型T都可以作为key。比如std::string或者是实现了operator std::string_view()的自定义类型。但是代价是增加了叶子结点的大小(由于实际存储的Node是variant<Leaf, Branch>，所有节点大小都会增加)。

5. 据上所述，以char*作为key时，节点大小最小(在我的机器上：sizeof(Leaf)==8, sizeof(Branch)==16, sizeof(Node)==max(8, 16)+8==24)

6. char*为key和原版比起来，存在一个问题：在内部逻辑中，统一用std::string_view处理key，会根据key构造一些std::string_view的临时对象。char*转string_view会调用strlen，所以和std::string作为key相比，性能会有一定损失。

7. 使用了hat-trie( https://github.com/Tessil/hat-trie )的测试程序进行初步测试。数据用了wikipedia 20200801的标题集合, shuf打乱顺序。和hat-trie作者给出的结果类似，qp-trie在这种大量前缀概率高的短字符串场景下表现不理想。

   a. 和哈希表类结构相比： 插入耗时是std::unordered_map和htrie_map的3倍左右，查询耗时是他们的5倍左右，内存消耗比std::unordered_map的略低，是hat-trie的3倍多。原因是这种大量前缀概率高的短字符串场景下，qp-trie的压缩数组带来的空间收益不明显，而且动态数组会频繁扩容，产生大量的小内存的申请和释放。由于前缀概率高，导致分支层次变得很深，相比哈希表，一次查询会引起更多次寻址

   b. 和平衡树类结构相比： 插入和查询性能比std::map略高，内存消耗大致类似。

   没有测试前缀查找功能，不过从原理上看，qp-trie的前缀查找性能应该会有不错的表现。

TODO

• 实现迭代器
• 实现非递归遍历，优化前缀查找性能
• 实现KV功能
• set和map类型定义
• Trie的拷贝构造和移动构造
• 更详细的benchmark