C++のstd::list::sort()でリストをソートする方法

C++標準ライブラリによるソートの概要

この記事では、C++の標準ライブラリを活用して配列や連結リスト（リンクリスト）をソートする方法について解説します。C++にはさまざまな用途に対応する多数のライブラリが標準で用意されており、ソート機能もその一つです。

std::list::sort()は、リストの要素を昇順に並べ替えるメンバ関数です。この関数は安定ソート（stable sort）であるため、値が等しい要素同士の相対的な順序は保持されます。要素の比較には、デフォルトでoperator<が使用されます。

サンプルコード

#include <iostream>
#include <list>
using namespace std;
int main(void) {
    list<int> l = {1, 4, 2, 5, 3};
    cout << "ソート前のリストの内容" << endl;
    for (auto it = l.begin(); it != l.end(); ++it)
        cout << *it << endl;
    l.sort();
    cout << "ソート後のリストの内容" << endl;
    for (auto it = l.begin(); it != l.end(); ++it)
        cout << *it << endl;
    return 0;
}

実行結果

ソート前のリストの内容
1
4
2
5
3
ソート後のリストの内容
1
2
3
4
5

補足：計算量と応用

std::list::sort()の計算量はO(n log n)です。リンクリストはランダムアクセスができないため、std::sort()をそのまま適用することはできませんが、std::listは独自のsort()メンバ関数を提供しており、内部でマージソートを用いて効率的にソートを行います。

また、降順でソートしたい場合は、比較関数としてstd::greater<int>()を引数に指定することも可能です。