c++ - stable_sort 不保持元素的顺序

Question

我有一个 std::vector of Object，Object 可以是 Empty 或 NotEmpty(这是一个内部状态，Object 本身总是有效的)。

我想按内部状态对 vector 进行排序，同时保持排序前的相对顺序。

理论上(除非我遗漏了什么)我只需要检查比较函数的第一个元素的内部状态:

    // i want to keep the NonEmptys first
    std::stable_sort(vec.begin(), vec.end(), [](const auto& first, const auto& second)
    {
        return first.getStatus() != Status::Empty;
    });

问题是这与排序前的顺序不同，事实上，如果我再次排序，它只会颠倒 NonEmptys 的顺序。

我阅读了严格的弱排序，并尝试了几个比较函数，结果总是相同(即使两个 Empty 都返回 false 也尝试过)。

提前致谢。

Answer 1

传递给 std::stable_sort 的比较器没有形成有效的排序。例如，如果我们有 object1和 object2都为空，则 object1 < object2 和 object2 < object1 (使用你的比较器)。这不适用于标准排序功能。

你真正想要的是 std::stable_partition :

std::stable_partition(vec.begin(), vec.end(), [](const auto& object)
{
    return object.getStatus() != Status::Empty;
});