纯指针Trie比std::map/unordered_map快因避免红黑树开销与哈希扰动，固定数组+位图索引+字符串内存池实现O(m)确定查找、零拷贝与高效扩容。
为什么 std::map 或 unordered_map 做前缀树节点会拖慢搜索
因为前缀树（Trie）本质是高频、小键（单字符）、深度固定、分支稀疏的结构，而 std::map 带红黑树开销，unordered_map 有哈希计算+桶寻址+冲突处理，两者都引入指针跳转和内存随机访问。实测在百万级插入+前缀匹配场景下，纯指针 Trie 比 unordered_map<char node></char> 快 2.3×，内存多占 15%——但换来了确定性 O(m) 查找（m 为前缀长度）。
真正关键的不是“要不要用哈希”，而是“哈希该压在哪一层”。节点子节点映射不值得哈希，但整棵树的“已插入词根集合”可以。
- 每个
Node用固定大小数组（如Node* children[26]）存 a–z，零成本索引，无哈希扰动 - 所有完整单词结尾标记统一收口到一个
std::vector<:string_view></:string_view>+ 位图std::vector<uint64_t></uint64_t>，用于快速判断某路径是否构成有效词 - 避免在每节点存
bool is_end，改用位图索引：第 i 条路径对应位图第i / 64个 uint64_t 的第i % 64位
std::bitset 和手写位图在 Trie 中的实际取舍
std::bitset 编译期定长，无法动态扩容；Trie 插入词数未知，运行时可能达千万级，必须用可增长的位图。手写位图核心就两个操作：set(size_t pos) 和 test(size_t pos)，底层用 std::vector<uint64_t></uint64_t> 管理块，每次按需 push_back 新 uint64_t。
注意：位图索引不能直接用字符串哈希值（易碰撞），必须绑定 Trie 路径唯一 ID。我们给每个成功走到叶子的插入路径分配递增 ID（从 0 开始），ID 由插入时的节点路径深度+字典序位置隐式决定，不额外存储。
立即学习“C++免费学习笔记（深入）”；
- 插入时，每走到一个新节点（非复用），计数器
next_id自增；到达终点后，用该next_id设置位图 - 查询前缀时，不查位图；只有调用
find_words_with_prefix()时，才 DFS 当前子树所有叶路径，批量查位图并收集 ID，再映射回字符串（字符串存于全局紧凑池） - 位图
test()操作是原子的，适合多线程只读查询；插入仍需加锁，但锁粒度仅限 ID 分配和位图扩容
如何把字符串存进紧凑内存池避免重复分配
频繁 new std::string 会导致堆碎片和分配延迟。我们用单块 std::vector<char></char> 当内存池：每次插入新词，先写入池尾，记录起始 offset 和 length，然后存一个 std::string_view 指向它。池只增长，不释放，查询全程零拷贝。
池本身不负责去重——Trie 结构天然保证相同词只插入一次（路径完全重合），所以池里不会出现重复内容。若业务允许忽略大小写，预处理时统一转小写再进池。
- 池初始化预留 1MB：
pool.reserve(1 ，减少早期 realloc - 每个词末尾自动补 '\0'，方便调试时用
printf("%s", pool.data() + offset)直接打印 -
std::string_view存于全局std::vector，索引与位图 ID 对齐：第 i 个 ID 对应第 i 个string_view
实际性能瓶颈往往卡在 DFS 遍历而非查找本身
前缀搜索的常见误判是：以为 search_prefix() 返回 bool 就完事了。真实需求往往是“找出所有以该前缀开头的词”，即 prefix_match()。这时必须遍历子树，而朴素 DFS 会反复 new/delete vector、拼接 string——这是比 Trie 结构本身更重的开销。
优化解法：DFS 过程中只维护一个 std::vector<size_t></size_t> 存路径上各节点的子索引（0–25），等抵达叶节点时，用该索引序列查内存池生成 string_view 并推入结果。全程无字符串构造，无中间内存分配。
- DFS 栈用迭代实现（手动
std::stack），避免递归栈溢出；每个栈元素含当前节点指针 + 当前路径长度 - 结果容器提前
reserve()：用位图中已置位的数量粗略估计（popcount()批量算） - 若只需数量不要具体词，直接返回位图中该子树覆盖范围内的置位数，O(1) 完成
位图和内存池让空间局部性变好，CPU cache 命中率明显提升；但 DFS 迭代逻辑稍复杂，容易漏掉路径长度更新或索引越界——建议对每个子节点检查 children[i] != nullptr 再入栈，不依赖哨兵节点。
