2 
#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;
}

使用できるトリックはありますか？たとえば、リスト内の 2 つのノードを交換するメソッドがあれば、mergesort を使用できます。

4

2 に答える 2

4

リストには一定時間の挿入と削除があるため、splice並べ替えを使用して一時リストを作成すると、挿入が非常に高速になります（残念ながら、要素のコピーでは依然として線形です）。

#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;
}
于 2013-08-06T08:08:49.317 に答える
-2

std::sort を使用して std::list をソートすることはできません。これは、std::sort では反復子がランダム アクセスである必要があり、std::list 反復子は双方向のみであるためです。

ただし、 std::list には、並べ替えを行うメンバー関数 sort があります。

于 2013-08-06T09:41:34.457 に答える