std::list の基本的な操作方法

C++の標準テンプレートライブラリ（STL）に含まれる std::list は、双方向連結リストとして実装されています。要素の挿入や削除が高速である一方で、ランダムアクセスには適さないという特徴があります。

1. インスタンス化と要素の操作

#include <iostream>
#include <list>
#include <algorithm>

int main() {
    // コンテナの初期化
    std::list<int> sequence = {10, 20, 30};
    std::list<int> buffer(5, 100); // 100を5個持つリスト

    // 要素の追加
    sequence.push_front(5);   // 先頭に追加
    sequence.push_back(40);   // 末尾に追加

    // 任意の場所への挿入
    auto pos = sequence.begin();
    std::advance(pos, 2); 
    sequence.insert(pos, 15); // 3番目の位置に15を挿入

    // 要素の削除
    sequence.pop_front();      // 先頭を削除
    sequence.erase(sequence.begin()); // イテレータが指す要素を削除
    sequence.remove(100);      // 値が100の要素をすべて削除

    // リストの走査
    for (const auto& val : sequence) {
        std::cout << val << " ";
    }
    
    return 0;
}

2. 高度なメンバ関数

std::list には、連結リストの特性を活かした独自のアルゴリズムがメンバ関数として提供されています。

• sort(): 要素を昇順または降順に並べ替えます。計算量は $O(n \log n)$ です。
• merge(): 2つのソート済みリストを統合します。
• unique(): 連続した重複要素を取り除きます（事前にソートが必要）。
• reverse(): 要素の順序を反転させます。
• splice(): 他のリストから要素を移動させます（コピーは発生しません）。

3. イテレータの無効化ルール

std::list は、ベクタ（std::vector）とは異なり、要素の挿入や削除を行っても、削除された要素を指すイテレータ以外は無効になりません。この特性は、リストを操作しながら要素を管理するアルゴリズムにおいて非常に有用です。

標準ライブラリと手動実装の比較

自前で struct Node を定義して連結リストを実装する場合と、std::list を使用する場合の主な違いは以下の通りです。

実装の対比例：大量データの追加

STLを使用する場合、メモリの動的確保やポインタの繋ぎ変えを意識する必要がありません。

// STLを使用した場合（簡潔で安全）
std::list<int> stl_values;
for (int i = 0; i < 50000; ++i) {
    stl_values.push_back(i);
}

// 手動実装の場合（メモリリークやポインタ操作ミスのリスク）
struct Item {
    int val;
    Item* next;
    Item(int v) : val(v), next(nullptr) {}
};

Item* root = nullptr;
Item* current = nullptr;
for (int i = 0; i < 50000; ++i) {
    Item* newItem = new Item(i);
    if (!root) {
        root = newItem;
        current = newItem;
    } else {
        current->next = newItem;
        current = newItem;
    }
}
// この後、全てのノードをdeleteするループも記述しなければならない

手動実装が求められる特殊なケース

基本的には std::list が推奨されますが、以下のような特定の状況では自作のデータ構造が必要になることがあります。

• メモリプールの利用: 特定のメモリ領域にノードを配置し、アロケーションコストを極限まで抑えたい場合。
• 特殊な連結方式: 複数のリストを跨ぐイントルーシブ・リスト（Intrusive List）や、XOR連結リストなどの特殊な構造が必要な場合。
• ロックフリー構造: マルチスレッド環境で高いパフォーマンスを発揮する非ブロッキングなリストを実装する場合。