C++中字符串表示超大整数的自定义排序比较器异常问题

在C++中对存储超大整数（10^6位）的string类型vector执行升序排序时，自定义比较器能正确处理不同位数的数字，但同位数数字排序失败（例如无法正确排列"82"和"44"）。示例代码及运行结果如下：

#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);

bool comp(const string &left, const string &right)
{
    if (left.size() < right.size())
    {
        return true;
    }
    if (left.size() > right.size())
    {
        return false;
    }

    for (unsigned long int i = 0; i < left.size(); i++)
    {
        if (left[i] > (right[i]))
        {
            // left is bigger
            return false;
        }
    }
    // left is smaller or equal
    return true;
}

int main(void)
{
    vector<string> str_nums = {"82", "44", "131", "2"};

    sort(str_nums.begin(), str_nums.end(), comp);

    for (string e : str_nums)
    {
        cout << e << endl;
    }
    return 0;
}

运行输出：

2
82
44
131

问题原因 #

你的比较器在处理同位数字符串时存在两个逻辑缺陷：

• 未及时返回left小于right的情况：当某个位置的字符left[i] < right[i]时，没有立即返回true（表示left应该排在right前面），而是继续循环后续字符，导致错误判断。比如比较"44"和"82"时，第一个字符'4' < '8'，但代码未处理该情况，继续比较第二个字符'4' > '2'，最终返回false，让排序逻辑误以为"44"不应该排在"82"前面。
• 相等元素返回true违反严格弱排序规则：当left和right完全相等时，返回true，这不符合C++sort要求的严格弱排序（comp(a,a)必须返回false），会导致排序行为未定义。

修正后的比较器 #

bool comp(const string &left, const string &right)
{
    if (left.size() != right.size())
    {
        return left.size() < right.size();
    }

    for (size_t i = 0; i < left.size(); i++)
    {
        if (left[i] != right[i])
        {
            return left[i] < right[i];
        }
    }
    // 两个字符串完全相等，返回false符合严格弱排序
    return false;
}

修正后运行结果 #

2
44
82
131

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