如何从std::vector<std::string>移除嵌套路径？关于std::unique的疑问

你的思路方向是对的，但用std::unique确实存在风险——虽然你的谓词满足对称性，但std::unique的核心是处理等价重复元素，标准并未明确规定它会保留等价组中的哪一个元素（尽管多数实现会保留第一个，但依赖这个行为不够稳健）。更关键的是，当路径排序后，我们的需求其实是保留父路径、剔除所有子路径，用std::unique的等价判断逻辑并不完全匹配这个需求。

正确实现方式 #

利用排序后父路径会排在所有子路径之前的字典序特性，我们可以手动遍历筛选，逻辑更清晰且无实现依赖：

std::vector<std::string> paths = getPaths();

// 按字典序排序，确保父路径在子路径之前
std::sort(paths.begin(), paths.end());

// 原地筛选，保留非子路径条目
auto last_keep = paths.begin();
for (auto it = std::next(last_keep); it != paths.end(); ++it) {
    // 检查当前路径是否是上一个保留路径的子目录
    // 注意：要确保父路径以路径分隔符结尾，避免误判（比如"root/dir"和"root/dir2"）
    if (!it->starts_with(*last_keep)) {
        *++last_keep = std::move(*it);
    }
}
// 移除多余元素
paths.erase(std::next(last_keep), paths.end());

关键细节说明 #

• 排序的必要性：字典序排序后，所有子路径必然紧跟在对应的父路径之后，我们只需要和上一个保留的父路径对比即可，无需遍历所有已保留路径，效率更高。
• 路径分隔符的处理：如果你的路径存在不带结尾/的情况（比如root/dir1），需要先统一处理路径格式（比如给所有路径加上结尾/），避免出现root/dir1被误判为root/dir12的父路径这种情况。
• 原地修改的优势：使用原地筛选避免额外内存开销，std::move也能减少字符串拷贝的成本。

原代码的问题分析 #

你的原代码中，std::unique会把互为父子的路径视为等价元素，只保留每组等价元素中的一个。但如果标准库实现选择保留等价组的最后一个元素（虽然极少出现，但标准未禁止），就会导致子路径被保留、父路径被删除的错误结果。手动筛选的方式完全规避了这个风险。

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