C++如何实现字符串的快速行级去重(Set法)

在处理大文本文件的行级去重时，很多人第一反应就是上 std::set，觉得“丢进去自动就去重了，多省事”。这种想法看起来简单，但在实践中容易踩坑——std::set 确实能去重，但它会自作主张按字典序排序，把你原来的顺序打乱得一干二净。而且如果没处理好换行残留、空行、尾随空白之类的问题，同一行文本可能会被识别成两个不同的字符串。

为什么用 std::set 做行级去重容易出错

直接把每行字符串往 std::set 里一塞，看起来是去重了，但实际效果跟你想的可能差了十万八千里。问题在于 std::set 只保证“集合里没有重复元素”，却不保证“输出的顺序跟输入一样”——它内部按红黑树排序，输出时自然按照字母顺序排好了。而所谓的“行级去重”，通常要求你按输入的顺序，保留第一次出现的行。

更要命的是换行符问题。用 getline 读取时，虽然它会把换行符截掉，但 Windows 文件里的 有时候会残留下来，或者文件末尾的空行也可能导致逻辑上相同的行被当成两个不同的字符串。这还没算空行要不要保留、空白符要不要统一这类业务逻辑的坑。

• std::set 自动排序，打乱原始行序，不能直接用于“保持首次出现顺序”的去重。
• 未清理的 会导致 Linux 下读入的 Windows 文件中同一行被识别为两个不同字符串。
• 空行是否保留、空白符是否忽略，std::set 本身不帮你做这些判断。

用 std::set + std::vector 组合实现保序去重

核心思路很直接：用 std::set 做快速的查重，用 std::vector 记录首次出现的行，从而保证顺序。每次读一行，先尝试往 set 里插入，插入时会返回一个 pair，其中 bool 为 true 表示这是第一次出现的新元素——这时才把它 push 到 vector 里。

std::set seen;
std::vector unique_lines;
std::string line;
while (std::getline(std::cin, line)) {
    // 清理常见换行残留
    if (!line.empty() && line.back() == '\r') {
        line.pop_back();
    }
    auto [_, is_new] = seen.insert(line);
    if (is_new) {
        unique_lines.push_back(line);
    }
}

这里有几个细节需要注意。一是 seen.insert(line) 是 O(log n) 的查重操作，比线性遍历 vector 要快得多，几千到几万行的场景下性能完全够用。二是从 C++17 开始可以用结构化绑定 auto [_, is_new] 来解包返回值，看起来很清爽；如果是 C++11 或 C++14，需要写成 auto ret = seen.insert(...); if (ret.second) {...}。三是清理 这步不能省，尤其是处理从 Windows 传来的日志文件时，少了这步可能会多出一堆“看起来一样但实际不一样”的行。

性能瓶颈在哪？什么时候该换 std::unordered_set

当行数超过 10 万时，std::set 的 O(log n) 累积起来确实会有点吃力，这时候 std::unordered_set 的均摊 O(1) 更占优势。但话说回来，unordered_set 也不是银弹：哈希计算有额外开销，内存占用更高，最坏情况下还会退化为 O(n)。

• 小数据（<10万行）时，std::set 和 unordered_set 的差距不明显，但 set 更省内存。
• 大数据（>100k 行）且内存充足时，优先用 std::unordered_set，记得用 seen.reserve(100000) 预留容量，避免频繁 rehash 拖慢性能。
• 如果字符串极长（比如每行几 KB），哈希计算本身就会成为瓶颈，这时候反而 std::set 更稳。

别忘了边界：空行、全空白行、超长行

真实日志或配置文件里，空行和仅含空格/tab 的行到底算不算“重复”？std::set 默认把空串 "" 和 " " 当成不同的字符串，但业务上可能需要统一归一化。这里才是真正的难点所在——技术实现本身很简单，但“重复”的定义得你自己想清楚。

• 若需忽略空白行：if (line.find_first_not_of(" \t") == std::string::npos) continue;
• 若需折叠空白：std::regex_replace(line, std::regex("\\s+"), " ")（注意正则替换会有额外的性能损耗）。
• 超长行（>1MB）可能触发 std::getline 分配失败，建议加长度检查或改用缓冲读取。

说句实在话，真正难的不是写对那几行 insert，而是搞清你的“重复”定义到底是什么——是字节完全一致，还是语义等价。这个判断一旦错，后面所有优化都是白搭。