C++如何实现字符串的自然数比较算法

字符串排序里有个经典“反直觉”场景：`"10"` 比 `"2"` 小，这事儿搁谁身上都觉得别扭。原因很简单，默认的字典序比较是按字符一位一位算的，`'1'` 的 ASCII 码本来就比 `'2'` 小，所以 `"10" < "2"` 成立。——但人类脑子里的排序，应该是 10 大于 2 才对。 这种“把连续数字当成一个整体数值来比较”的排序方式，就叫自然数比较（natural sort）。C++ 标准库？抱歉，没这个函数。得自己动手，或者找第三方库帮忙。 ### ? 为什么默认的 `std::string::operator<` 不行？ 说白了，`std::string::operator<` 就是按字符编码一位一位比。`"10"` 和 `"2"` 比较时，先比 `'1'` 和 `'2'`，自然 `"10"` 更小。但人类直觉是 `10 > 2`，这矛盾就来了。 所谓自然数比较，就是要让数字部分按数值大小比，而不是按字符逐位比。C++ 标准库不提供现成函数，必须自己实现或借助第三方逻辑。 ### ? 核心思路：分段 + 识数 把字符串切成“纯数字段”和“非数字段”交替的序列，然后逐段比较：数字段转成 `int` 或 `long long` 比数值，非数字段按字典序比。关键在于怎么切——不能简单拿 `isdigit()` 划界，得把连续的数字当成一个整体。 实际操作时，别看那些花里胡哨的方案，最靠谱的还是自己手写一个扫描器： - 用双指针扫描，遇到数字开头就持续读取直到非数字，提取子串并转成整数（注意溢出，推荐 `std::stoll` 或手动解析） - 非数字段直接用 `std::string_view` 或 `substr` 提取，避免频繁构造临时对象 - 比较时先看段类型：数字对数字比数值，字符串对字符串逐字符比。如果一个是数字段另一个是非数字段呢？通常数字段排在前面（你可以按需求调整规则，但多数场景下 `"123abc"` 会排在 `"abc"` 前） - 下面是一个可参考的逻辑片段： ```brush:php;toolbar:false; while (i < a.size() && j < b.size()) { if (std::isdigit(a[i]) && std::isdigit(b[j])) { auto [n1, ni] = parse_number(a, i); auto [n2, nj] = parse_number(b, j); if (n1 != n2) return n1 < n2; i = ni; j = nj; } else if (!std::isdigit(a[i]) && !std::isdigit(b[j])) { // 字符串段逐字符比 while (i < a.size() && j < b.size() && !std::isdigit(a[i]) && !std::isdigit(b[j])) { if (a[i] != b[j]) return a[i] < b[j]; ++i; ++j; } } else { // 一数字一非数字：数字段排前面（如 "abc123" < "abcdef" → false，但 "123abc" < "abc" → true） return std::isdigit(a[i]) && !std::isdigit(b[j]); } } ``` ### ? 实战翻车点：你以为写好了，其实到处都是坑 自然排序听起来简单，但实测翻车概率不低。整理几个常见问题： - **前导零问题**：`"a1"` 和 `"a01"` 应该是等价的（数值都是 1），但要小心解析的时候没跳过前导零再算长度，可能导致段边界判断出错。好消息是 `stoll("01")` 返回 1，所以用标准转换函数问题不大。 - **空字符串或全数字字符串**：比如 `"123"` vs `"45"`，或者 `"a1"` vs `"a"`。这种情况要处理好边界：一段结束另一段还有剩余时，必须判断剩余部分是不是数字段。比如 `"a1"` vs `"a"`，后者没有数字段，理论上应该更小。 - **负数怎么办**？标准自然排序通常不处理负号。如果输入里有 `"-5"` 和 `"-10"`，直接用 `stoll` 会得出 -5 > -10，这符合数值逻辑。但多数自然排序约定是把负号当成普通字符，或者干脆忽略符号。具体怎么做，得看需求。 - **大数溢出**：`long long` 也不是万能的。如果数字可能超出它范围，可以改用字符串比较：先比长度，长者数值大；长度相同再逐字符比。性能会降一点，但安全了。 ### ? 能不能偷懒？标准库、Boost、Qt 呢？ C++ 标准库？抱歉，不给力。`std::locale` 不支持自然排序，`std::collate` 只做本地化字典序，帮不上忙。 Boost 呢？`Boost.StringAlgorithms` 也没有内置 natural sort。搜一圈会发现，最轻量方案还是自己手写——20 到 30 行核心逻辑够了，而且可控性强。 如果项目里已经用了 ICU 或 Qt，可以试试 `QLocale::compare` 并启用 `QLocale::NumericalMode`。但为了一个排序功能引入那么大依赖，不划算。 顺便提一句，真正麻烦的是嵌套结构，比如路径 `"log_100_v2.txt"` vs `"log_99_v10.txt"`，或者遇到 Unicode 数字字符（像全角数字），这些就超出基础自然排序的范畴了。真要处理，得先做预归一化，或者直接上专用库。