STLのlistコンテナでソートを実装するC++プログラム

この記事では、C++のSTL（標準テンプレートライブラリ）に含まれるlistコンテナを使用して、要素の追加・並べ替え・表示を行うメニュー式プログラムを実装します。

使用する主な関数

使用する関数:
    l.push_back() = リストの末尾に要素を追加します。
    l.sort()      = リストの要素を昇順に並べ替えます。
    ※ l は list オブジェクトです。

push_back()は引数で渡した値をリストの終端に追加する関数です。また、sort()はstd::listのメンバ関数として用意されており、呼び出すだけで内部のすべての要素を昇順にソートできます。std::listは双方向連結リストとして実装されているためランダムアクセスには不向きですが、独自のsort()メンバ関数を持っており、計算量O(n log n)で効率的に並べ替えが行えます。

サンプルコード

#include <iostream>
#include <list>
#include <string>
#include <cstdlib>
using namespace std;

int main() {
    list<int> l;
    list<int>::iterator it;
    int c, i;

    while (1) {
        cout << "1.リストに要素を挿入する" << endl;
        cout << "2.リストを表示する" << endl;
        cout << "3.終了する" << endl;
        cout << "選択してください: ";
        cin >> c;

        switch (c) {
            case 1:
                cout << "挿入する値を入力してください: ";
                cin >> i;
                l.push_back(i);
                break;
            case 2:
                l.sort();
                cout << "リストの要素: ";
                for (it = l.begin(); it != l.end(); it++)
                    cout << *it << " ";
                cout << endl;
                break;
            case 3:
                exit(1);
                break;
            default:
                cout << "無効な選択です" << endl;
        }
    }
    return 0;
}

実行結果

1.リストに要素を挿入する
2.リストを表示する
3.終了する

選択してください: 1
挿入する値を入力してください: 7
1.リストに要素を挿入する
2.リストを表示する
3.終了する

選択してください: 1
挿入する値を入力してください: 10
1.リストに要素を挿入する
2.リストを表示する
3.終了する

選択してください: 1
挿入する値を入力してください: 6
1.リストに要素を挿入する
2.リストを表示する
3.終了する

選択してください: 1
挿入する値を入力してください: 4
1.リストに要素を挿入する
2.リストを表示する
3.終了する

選択してください: 2
リストの要素: 4 6 7 10
1.リストに要素を挿入する
2.リストを表示する
3.終了する

選択してください: 3

プログラムのポイント解説

• 要素の追加： push_back()により、入力した値がリストの末尾へ順番に格納されます。
• 並べ替え： 表示の直前にsort()を呼び出すことで、7・10・6・4の順に追加された要素が「4 6 7 10」と昇順に出力されます。
• イテレータによる走査： begin()からend()までイテレータを進めながら、リスト内の全要素を表示しています。
• 終了処理： 選択肢「3」が入力されるとexit(1)によってプログラムを終了します。

なお、C++11以降の環境では、範囲ベースfor文を使えば for (int x : l) cout << x << " "; のように、イテレータを明示的に扱わずにより簡潔に記述することも可能です。