C++でSTLのlist（リスト）を操作するプログラムの実装方法

std::listは、非連続（連続していない）メモリ領域への要素配置を許容するシーケンスコンテナです。vectorと比較すると要素の走査はやや遅いものの、目的の位置さえ特定できれば、そこへの挿入・削除が非常に高速に行える点が大きな特徴です。内部は双方向リンクリストとして実装されており、先頭・末尾への追加や削除も定数時間で処理できます。

使用する主なメンバ関数

本プログラムでは、main() 関数から以下のメンバ関数を呼び出しています。

l.resize()      = リストのサイズを変更します。
l.push_front()  = リストの先頭に要素を追加します。
l.remove()      = 指定した値を持つ要素をすべて削除します。
l.unique()      = 隣接する重複要素を削除します。
l.reverse()     = リストの要素の並びを反転させます。
l.front()       = リストの先頭要素を返します。

サンプルコード

次のプログラムは、メニュー形式でリストに対する各種操作（挿入・削除・表示など）を対話的に試せるサンプルです。

#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<<"4.末尾の要素を削除"<<endl;
        cout<<"5.リストの先頭要素を表示"<<endl;
        cout<<"6.リストの末尾要素を表示"<<endl;
        cout<<"7.リストのサイズを表示"<<endl;
        cout<<"8.リストのサイズを変更"<<endl;
        cout<<"9.指定した値の要素を削除"<<endl;
        cout<<"10.重複する値を削除"<<endl;
        cout<<"11.要素の順序を反転"<<endl;
        cout<<"12.リストを表示"<<endl;
        cout<<"13.終了"<<endl;
        cout<<"番号を選択してください: ";
        cin>>c;
        switch(c) {
            case 1:
                cout<<"先頭に挿入する値を入力: ";
                cin>>i;
                l.push_front(i);
            break;
            case 2:
                cout<<"末尾に挿入する値を入力: ";
                cin>>i;
                l.push_back(i);
            break;
            case 3:
                i= l.front();
                l.pop_front();
                cout<<"要素 "<<i<<" を削除しました"<<endl;
            break;
            case 4:
                i= l.back();
                l.pop_back();
                cout<<"要素 "<<i<<" を削除しました"<<endl;
            break;
            case 5:
                cout<<"リストの先頭要素: ";
                cout<<l.front()<<endl;
            break;
            case 6:
                cout<<"リストの末尾要素: ";
                cout<<l.back()<<endl;
            break;
            case 7:
                cout<<"リストのサイズ: "<<l.size()<<endl;
            break;
            case 8:
                cout<<"新しいリストのサイズを入力: ";
                cin>>i;
                if (i <= l.size())
                    l.resize(i);
                else
                    l.resize(i, 0);
            break;
            case 9:
                cout<<"削除する要素の値を入力: ";
                cin>>i;
                l.remove(i);
            break;
            case 10:
                l.unique();
                cout<<"重複する項目を削除しました"<<endl;
            break;
            case 11:
                l.reverse();
                cout<<"リストを反転しました"<<endl;
            break;
            case 12:
                cout<<"リストの要素: ";
                for (it = l.begin(); it != l.end(); it++)
                    cout<<*it<<" ";
                cout<<endl;
            break;
            case 13:
                exit(1);
            break;
            default:
                cout<<"正しい番号を選択してください"<<endl;
        }
    }
return 0;
}

実行結果

以下は実際の実行例です。各操作の後にはメニューが再度表示されますが、ここでは省略しています。

1.先頭に要素を挿入
2.末尾に要素を挿入
3.先頭の要素を削除
4.末尾の要素を削除
5.リストの先頭要素を表示
6.リストの末尾要素を表示
7.リストのサイズを表示
8.リストのサイズを変更
9.指定した値の要素を削除
10.重複する値を削除
11.要素の順序を反転
12.リストを表示
13.終了

番号を選択してください: 1
先頭に挿入する値を入力: 1

番号を選択してください: 1
先頭に挿入する値を入力: 2

番号を選択してください: 3
要素 2 を削除しました

番号を選択してください: 4
要素 1 を削除しました

番号を選択してください: 2
末尾に挿入する値を入力: 5

番号を選択してください: 1
先頭に挿入する値を入力: 6

番号を選択してください: 1
先頭に挿入する値を入力: 7

番号を選択してください: 12
リストの要素: 7 6 5

番号を選択してください: 1
先頭に挿入する値を入力: 5

番号を選択してください: 1
先頭に挿入する値を入力: 4

番号を選択してください: 12
リストの要素: 4 5 7 6 5

番号を選択してください: 10
重複する項目を削除しました

番号を選択してください: 5
リストの先頭要素: 4

番号を選択してください: 11
リストを反転しました

番号を選択してください: 12
リストの要素: 5 6 7 5 4

番号を選択してください: 13

ポイント：unique() の動作に注意

上記の実行例では、unique() を呼び出してもリストの内容（4 5 7 6 5）が変化していません。これは、unique() が削除するのは「隣接する」重複要素のみだからです。離れた位置にある同じ値（この例では先頭付近の 5 と末尾の 5）は削除されません。すべての重複を取り除きたい場合は、あらかじめ sort() でソートしてから unique() を呼び出すのが一般的な手法です。