std::sort排序结果不符合自定义contains比较关系的问题

问题根源 #

你用contains作为std::sort的比较谓词，违反了std::sort要求的**严格弱序（Strict Weak Ordering）**规则，导致排序行为未定义，结果自然不符合预期。

严格弱序必须满足三个核心条件：

• 非自反性：对任意元素x，comp(x,x)必须返回false。但你的contains(x,x)显然返回true，直接违反这一点。
• 不对称性：如果comp(a,b)为true，那么comp(b,a)必须为false。这一点若contains逻辑正确（a包含b则b不包含a，除自身外）是满足的，但自反性的问题已经足以导致排序混乱。
• 传递性：如果comp(a,b)和comp(b,c)为true，那么comp(a,c)必须为true。这一点若contains逻辑正确（a包含b、b包含c则a包含c）是满足的，但前两个条件的违反已经让算法无法正常工作。

解决方案 #

你需要调整比较谓词，使其满足严格弱序，同时实现“包含者排在被包含者前”的需求：

修正后的排序代码 #

std::sort(
    result.begin(), result.end(), []( const auto& p1, const auto& p2 )
    {
        const auto& pocket1 = std::get<0>(p1);
        const auto& pocket2 = std::get<0>(p2);
        
        const bool p1_contains_p2 = pocket1.contains(pocket2);
        const bool p2_contains_p1 = pocket2.contains(pocket1);

        // p1真包含p2，p1排前面
        if (p1_contains_p2 && !p2_contains_p1) {
            return true;
        }
        // p2真包含p1，p1不能排前面
        else if (p2_contains_p1 && !p1_contains_p2) {
            return false;
        }
        // 互不包含或相等时，用稳定字段排序（比如文件名，可根据实际替换）
        else {
            return std::get<1>(p1) < std::get<1>(p2);
        }
    } );

关键调整说明 #

1. 明确真包含关系：只在p1完全包含p2且p2不包含p1时，让p1排在前面，避免自反性问题。
2. 解决自反性：当元素相等（互相包含）时，通过额外字段比较确保comp(x,x)返回false。
3. 处理互不包含场景：对互不包含的元素，用稳定的规则（如文件名、ID）排序，避免算法因无法判断顺序产生未定义行为。

针对最小复现示例的适配 #

如果是模拟的contains逻辑，同样遵循上述规则：

• 先判断A是否真包含B，是则A排前；
• 再判断B是否真包含A，是则A不排前；
• 最后用元素标识（如数字值）排序，确保严格弱序。

这样就能保证排序结果符合你的预期：3在最前，33在除30、31外的元素前，32在2前，10在26、27前。

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