如何在BTreeSet<PathBuf>中稳健查询指定目录下的所有文件路径？

要高效查询规范化BTreeSet<PathBuf>中所有位于指定规范化目录下的文件路径，最稳健的方式是利用BTreeSet的range方法，通过构造精准的字典序区间过滤目标路径，核心思路如下：

核心逻辑 #

Path的Ord实现基于字节字典序，所有位于目标目录下的路径（包括子目录中的文件）都会以带结尾分隔符的目录路径作为前缀。我们只需构造两个边界：

• 起始边界：目标目录路径（确保以路径分隔符结尾，保证子路径都以它为前缀）
• 结束边界：起始边界的字典序后继路径（所有目标路径都会小于这个边界）

具体实现 #

1. 构造起始边界 #

通过directory.join("")确保目录路径以分隔符结尾，避免因原目录路径是否带分隔符导致的匹配问题：

use std::path::{Path, PathBuf};
use std::collections::BTreeSet;
use std::ops::Bound::{Included, Excluded};

let set: BTreeSet<PathBuf> = /* 你的规范化文件路径集合 */;
let directory: &Path = /* 你的规范化目录路径 */;

// 构造起始边界：确保路径以分隔符结尾
let start = directory.join("");

2. 构造结束边界 #

通过修改起始路径的字节序列，生成字典序中最小的、比起始路径大的路径，确保所有目标路径都落在起始边界和结束边界之间：

use std::ffi::OsStr;

fn get_upper_bound(path: &Path) -> PathBuf {
    let os_bytes = path.as_os_str().as_bytes();
    let mut upper_bytes = os_bytes.to_vec();
    
    // 从后往前找第一个可递增的字节，处理极端的0xFF字节情况
    let mut i = upper_bytes.len();
    while i > 0 {
        i -= 1;
        if upper_bytes[i] < 0xFF {
            upper_bytes[i] += 1;
            break;
        }
        upper_bytes[i] = 0;
    }
    
    // 处理所有字节都是0xFF的极端场景（合法路径中几乎不会出现）
    if i == 0 && upper_bytes[0] == 0 {
        upper_bytes.push(0);
    }
    
    OsStr::from_bytes(&upper_bytes).into()
}

let upper = get_upper_bound(&start);

3. 查询目标路径 #

使用range方法获取区间内的所有路径：

// 获取所有位于目标目录下的文件路径
let files_in_directory: Vec<_> = set.range(Included(&start)..Excluded(&upper)).collect();

关键注意事项 #

• 必须保证输入的目录路径和集合中的文件路径都是规范化的（无..、无重复分隔符等），否则会导致匹配错误。
• 该方法的时间复杂度为O(log n + k)（n为集合大小，k为匹配的路径数量），比遍历整个集合检查starts_with（O(n)）高效得多。
• 跨平台兼容性：该逻辑基于字节字典序，在Unix和Windows系统中均有效（Windows下规范化路径已统一大小写，不会影响匹配）。

内容的提问来源于stack exchange，提问作者nnnmmm