std::sort无法正确排序pair向量问题排查

问题重现 #

要对std::pair<int, int>类型的vector按第一个元素与第二个元素的比值排序，使用std::sort后结果不符合预期：

初始比较器代码 #

bool comparator(const std::pair<int, int> &item1, const std::pair<int, int> &item2)
{
    return (item1.first / item1.second) < (item2.first / item2.second);
}

排序调用代码 #

int main()
{
    std::vector<std::pair<int, int>> items = {{4, 5}, {1, 4}, {3, 5}, {6, 7}, {8, 8}};
    std::sort(items.begin(), items.end(), comparator);
    for (auto item : items)
        std::cout << item.first << ", " << item.second << "\n";
    
    return 0;
}

实际输出 #

8, 8
4, 5
1, 4
3, 5
6, 7

期望输出 #

8, 8
6, 7
4, 5
3, 5
1, 4

尝试修改比较器为以下代码后，结果仍错误：

return (double)(item1.first / item1.second) > (double)(item2.first / item2.second);

错误输出：

4, 5
1, 4
3, 5
6, 7
8, 8

问题原因 #

1. 整数除法截断问题：所有操作数都是int类型，执行item1.first / item1.second时会触发整数除法，直接舍弃小数部分。比如4/5=0、6/7=0、3/5=0、1/4=0，只有8/8=1，导致大部分元素的比值被判定为相等，std::sort的排序逻辑完全混乱。
2. 错误的类型转换时机：修改后的比较器中，先执行了整数除法再转double，比如item1.first / item1.second先得到0，再转成0.0，本质上和之前的问题一样，只是把整数结果转成了浮点数，并没有解决小数丢失的问题。

解决方案 #

方案1：提前转换为浮点数计算比值 #

将其中一个操作数先转换为double，触发浮点数除法，保留小数部分。因为期望是降序排列，所以用>比较：

bool comparator(const std::pair<int, int> &item1, const std::pair<int, int> &item2)
{
    // 先转double再做除法，避免整数截断
    double ratio1 = static_cast<double>(item1.first) / item1.second;
    double ratio2 = static_cast<double>(item2.first) / item2.second;
    return ratio1 > ratio2;
}

方案2：交叉相乘避免浮点数精度问题 #

如果担心浮点数精度误差（比如数值过大时），可以用交叉相乘的方式（仅适用于所有元素的第二个值为正数的场景，否则需额外处理符号）：
因为a/b > c/d 等价于 a*d > c*b（当b、d均为正数时），这样全程用整数运算，无精度损失：

bool comparator(const std::pair<int, int> &item1, const std::pair<int, int> &item2)
{
    // 注意：需确保item1.second和item2.second均为正数，否则要调整符号判断
    return static_cast<long long>(item1.first) * item2.second > static_cast<long long>(item2.first) * item1.second;
}

注：这里用long long是为了避免整数溢出，比如当两个int相乘超过int范围时，会导致溢出错误。

修正后运行结果 #

两种方案都能得到期望输出：

8, 8
6, 7
4, 5
3, 5
1, 4

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