Trie树比std::string::find更适合文件名前缀搜索，因其将路径按字符建树实现O(L)前缀查找，而后者需O(N×M)全量扫描；Trie应只存文件名或路径片段，配合小写化、智能过滤与索引回查以提升效率。
为什么 Trie 树比 std::string::find 更适合文件名前缀搜索
因为文件名搜索（比如输入 "log" 就列出 "logfile.txt"、"logging.cpp"）本质是**前缀匹配**，而 std::string::find 每次都要遍历整个字符串，对成百上千个路径做全量扫描，O(N×M) 复杂度很快卡顿。Trie 树把所有路径按字符拆解建树，查 "log" 只需走 3 层节点，时间复杂度降到 O(L)，L 是前缀长度。
注意：Trie 这里只存**文件名或路径片段**（如 "src/main.cpp" 可拆为 "src"、"main.cpp" 单独插入），不建议把完整绝对路径一股脑塞进去——否则 "/home/user/project/a.cpp" 和 "/tmp/a.cpp" 在根节点就分叉，失去共享前缀优势。
- 实际插入时，推荐用
std::filesystem::path::filename().string()提取纯文件名 - 若需支持路径层级搜索（如输
"src/m"匹配"src/main.cpp"），则按/分割后逐段插入，每段末尾加一个唯一分隔标记（如'/'字符） - 大小写敏感？默认建议小写化存储 + 查询，用
std::tolower遍历转换，避免依赖 locale
如何手写一个轻量级 Trie 节点（不依赖 Boost 或第三方）
核心只要两个成员：子节点映射和结束标记。别用 std::map<char node></char> —— 查找慢；改用 std::array<:unique_ptr>, 256></:unique_ptr> 直接索引 ASCII，空间换时间。中文路径？先 UTF-8 编码转字节再插（单字节处理），或改用 std::unordered_map<uint8_t std::unique_ptr>></uint8_t>。
struct TrieNode {
std::array<std::unique_ptr<TrieNode>, 256> children;
bool is_end = false; // 表示此处是一个完整文件名结尾
};
插入逻辑很简单：对每个字符 c，算出 static_cast<uint8_t>(c)</uint8_t> 当下标，检查是否为空，为空就 new；最后设 is_end = true。注意别漏掉空字符校验（如文件名含 '\0' 的极少见情况，可提前过滤）。
立即学习“C++免费学习笔记（深入）”；
- 内存安全：全部用
std::unique_ptr，析构自动释放，不用手写递归 delete - 不存具体文件路径——只在
is_end == true的节点额外挂一个std::vector<size_t></size_t>存原始文件列表索引（避免重复存字符串） - 构建完 Trie 后，原始文件名数组用
std::vector<:string></:string>保存一份，查询结果靠索引回查
搜索函数怎么写才能返回匹配的完整路径列表
搜索不是只返回“有没有”，而是要拿到所有匹配项对应的原始路径。所以得实现一个 searchPrefix(const std::string& prefix)，它返回 std::vector<size_t></size_t>（即文件数组下标），再由调用方去查真实路径。
过程分两步：先走前缀路径（失败直接返回空 vector），再从终点节点开始 DFS 收集所有 is_end 为 true 的子树路径。DFS 时不需要拼字符串，因为路径信息不在 Trie 上——你只需要在 DFS 过程中记录当前深度（即已匹配长度），一旦遇到 is_end，就把当前节点关联的索引加入结果。
std::vector<size_t> searchPrefix(const std::string& prefix) {
auto* node = root.get();
for (char c : prefix) {
uint8_t idx = static_cast<uint8_t>(c);
if (!node->children[idx]) return {};
node = node->children[idx].get();
}
std::vector<size_t> result;
collectEndIndices(node, result); // DFS 收集
return result;
}
- 如果要求“模糊匹配”（如通配符
"*.log"），Trie 不适合直接做——应先用 Trie 快速筛出所有以".log"结尾的候选，再用std::regex二次过滤 - 搜索响应快的关键：DFS 过程中不做字符串拼接、不 new 临时对象，只推索引
- 并发安全？这个 Trie 是只读结构（构建完不再修改），多线程搜索无需锁；若需动态增删，得加读写锁，但文件搜索场景通常构建一次用很久
实际扫描目录时，哪些路径该进 Trie、哪些该跳过
盲目把所有路径都插进去，会拖慢构建速度、撑大内存，还污染搜索结果。关键原则：**只索引用户真正想搜的内容**。
- 跳过系统隐藏文件：名字以
'.'开头（如".git"、".DS_Store"），用p.filename().string()[0] == '.'判断 - 跳过过大文件（比如 >100MB 的视频/ISO）：它们几乎不会被“按名搜索”，且
std::filesystem::file_size()调用开销小，值得加一层过滤 - 符号链接？默认不跟随（
std::filesystem::is_symlink(p)），避免循环引用；若需支持，加个深度限制（如最多跟 3 层） - 编码问题：遇到
std::filesystem::directory_iterator抛std::filesystem::filesystem_error（常见于权限不足或损坏路径），捕获后跳过，别让整个扫描中断
Trie 构建是离线过程，但容易被忽略的一点是：文件名中的 Unicode 组合字符（如带重音的 é）在 UTF-8 下占多个字节，直接按字节塞进 256 元素数组会错位。真要支持，得先用 ICU 或 C++20 <charconv></charconv> 做 Unicode 码点归一化，否则搜索 "cafe" 就找不到 "café" —— 这种细节，往往等用户反馈了才意识到。
