c++ - 如何对 std::list 的一部分进行排序？

Question

#include <iostream>
#include <list>
#include <algorithm>

int main()
{
    std::list<int> numbers = {1, 3, 0, -8, 5, 3, 1};
    auto positionInMiddle = std::find(numbers.begin(), numbers.end(), -8);

    std::sort(positionInMiddle, numbers.end()); // This doesn't work,
                                                // Needs random access iterator.

    numbers.sort(); // This sorts the entire list.

    for (int i : numbers)
        std::cout << i << std::endl;
    return 0;
}

我可以使用一些技巧吗？例如，如果有一种方法可以交换列表中的两个节点，那么我可以使用合并排序。

Answer 1

列表具有恒定的时间插入和删除，因此使用spliceto sort 制作一个临时列表是非常快速的插入方式（不幸的是，在复制元素时仍然是线性的）：

#include <iostream>
#include <list>
#include <algorithm>

int main()
{
    std::list<int> numbers = {1, 3, 0, -8, 5, 3, 1};
    auto positionInMiddle = std::find(numbers.begin(), numbers.end(), -8);

    std::list<int> temp;
    temp.splice(temp.end(), numbers, positionInMiddle, numbers.end());
    temp.sort();
    numbers.splice(numbers.end(), temp, temp.begin(), temp.end());

    for (int i : numbers)
        std::cout << i << std::endl;
    return 0;
}

Answer 2

您不能使用 std::sort 对 std::list 进行排序，因为 std::sort 要求迭代器是随机访问的，而 std::list 迭代器只是双向的。

但是， std::list 有一个成员函数 sort 可以对其进行排序：