【C++】STLのforward_list（単方向リンクリスト）を実装して操作する方法

forward_listとは？listとの違いを解説

C++の標準テンプレートライブラリ（STL）に含まれる std::forward_list は、単方向リンクリスト（片方向連結リスト）を実装したシーケンスコンテナです。

同じくリンクリスト構造を持つ std::list は「次の要素」と「前の要素」の両方を追跡できる双方向リストであるのに対し、forward_list は「次の要素」へのポインタのみを保持します。この設計により、各要素あたりのメモリ消費量を抑えられます。

その一方で、forward_list には次のような制約がある点に注意が必要です。

• ランダムアクセス不可： 個々の要素へ直接アクセスできず、必ず先頭から順に辿る必要がある
• 逆方向の走査不可： 後方へ向かってイテレートすることができない
• 効率的な操作は先頭付近に限定される： 挿入・削除が高速なのは先頭周辺のみ

本プログラムで使用する主なメンバ関数

サンプルコード

以下は、メニュー形式で forward_list の各操作を対話的に試せるプログラムです。

#include <iostream>
#include <forward_list>
#include <cstdlib>
using namespace std;

int main() {
    forward_list<int> fl;
    forward_list<int>::iterator it;
    int c, n;

    while (1) {
        cout << "1.先頭に要素を挿入" << endl;
        cout << "2.先頭の要素を削除" << endl;
        cout << "3.forward_listの先頭要素を表示" << endl;
        cout << "4.forward_listのサイズ変更" << endl;
        cout << "5.指定した値の要素を削除" << endl;
        cout << "6.重複要素を削除" << endl;
        cout << "7.要素の順序を反転" << endl;
        cout << "8.forward_listの内容を表示" << endl;
        cout << "9.終了" << endl;
        cout << "選択してください: ";
        cin >> c;

        switch (c) {
            case 1:
                cout << "先頭に挿入する値を入力: ";
                cin >> n;
                fl.push_front(n);
                break;
            case 2:
                n = fl.front();
                fl.pop_front();
                cout << "要素 " << n << " を削除しました" << endl;
                break;
            case 3:
                cout << "forward_listの先頭要素: " << fl.front() << endl;
                break;
            case 4:
                cout << "新しいサイズを入力: ";
                cin >> n;
                if (n <= fl.max_size())
                    fl.resize(n);
                else
                    fl.resize(n, 0);
                break;
            case 5:
                cout << "削除する値を入力: ";
                cin >> n;
                fl.remove(n);
                break;
            case 6:
                fl.unique();
                cout << "重複要素を削除しました" << endl;
                break;
            case 7:
                fl.reverse();
                cout << "forward_listを反転しました" << endl;
                break;
            case 8:
                cout << "forward_listの要素: ";
                for (it = fl.begin(); it != fl.end(); it++)
                    cout << *it << " ";
                cout << endl;
                break;
            case 9:
                exit(1);
                break;
            default:
                cout << "無効な選択です" << endl;
        }
    }
    return 0;
}

コードのポイント解説

• resize()：サイズを拡張する際、新しく追加される要素は第2引数を省略すると 0（int型のデフォルト値）で初期化されます。
• remove()：指定した値に一致する「すべての」要素が削除される点に注意してください。
• unique()：削除対象は「隣接する」重複のみです。ソートされていないリストの場合、離れた位置にある重複は残るため注意しましょう。

実行例

1.先頭に要素を挿入
2.先頭の要素を削除
3.forward_listの先頭要素を表示
4.forward_listのサイズ変更
5.指定した値の要素を削除
6.重複要素を削除
7.要素の順序を反転
8.forward_listの内容を表示
9.終了

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

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

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

選択してください: 8
forward_listの要素: 2 2 3

選択してください: 6
重複要素を削除しました

選択してください: 8
forward_listの要素: 2 3

選択してください: 3
forward_listの先頭要素: 2

選択してください: 4
新しいサイズを入力: 5

選択してください: 8
forward_listの要素: 2 3 0 0 0

選択してください: 5
削除する値を入力: 2

選択してください: 8
forward_listの要素: 3 0 0 0 0

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

選択してください: 7
forward_listを反転しました

選択してください: 8
forward_listの要素: 0 0 0 0 3 9

選択してください: 4
新しいサイズを入力: 3

選択してください: 8
forward_listの要素: 0 0 0

選択してください: 99
無効な選択です

選択してください: 9

実行結果の読み方

この実行例から、次の動作が確認できます。

• push_front() は常に先頭へ要素を追加するため、挿入順と逆の並びになる
• resize(5) で拡張された分は自動的に 0 で埋められる
• remove(2) を実行すると、一致する値 2 がすべて削除される
• reverse() を呼ぶと要素の並びが完全に反転する
• 範囲外の番号（99など）を入力すると「無効な選択です」と表示され、メニューに戻る

まとめ

forward_list はメモリ効率に優れ、先頭への挿入・削除を高速に行いたい場面で特に有用なコンテナです。ただし、ランダムアクセスや双方向の走査が必要なケースには不向きなため、そのような要件がある場合は list や vector など、目的に応じたコンテナを使い分けることが重要です。