std::list / std::forward_list ― 連結リスト各要素が独立したノードで、前後のポインタでつながっている構造が連結リスト。std::list は双方向、std::forward_list は単方向です。途中への挿入／削除が O(1)（ただし挿入位置の反復子を持っていれば）という強みがありますが、現代のマシンではキャッシュ効率の悪さで vector に負けることが多く、実戦での出番は限定的。本章では「どんな仕組みか」と「いつ使うべきか」を整理します。
lst[i] のようなランダムアクセス不可vector。list は特定用途だけsplice（リスト間の移動が O(1)）std::forward_list（単方向版）std::list の基本操作連結リストの代表。各要素がノードで、前後のポインタで繋がっています。
lst.push_back(x) / lst.push_front(x) ― 両端追加（どちらも O(1)）lst.pop_back() / lst.pop_front()lst.insert(it, x) ― it の手前に挿入（O(1)）lst.erase(it) ― it の要素を削除（O(1)）lst.size() / lst.empty() / lst.front() / lst.back()lst[i] や lst.at(i) は書けません。i 番目の要素が欲しければ std::next(lst.begin(), i) で反復子を進める必要があり、これは O(i)。
教科書には「list は中間挿入が O(1) で速い」と書かれますが、実測では vector のほうが速いことがほとんどです。理由は 2 つ。
各ノードはヒープ上にバラバラに配置されます。ノード間を移動するたびにキャッシュミスが起き、現代 CPU のキャッシュ階層の恩恵を受けられません。vector は連続領域なので、まとめてキャッシュに乗って高速。
list の「中間挿入 O(1)」は反復子を持っている前提。もし「i 番目に挿入したい」なら反復子を i 回進める必要があり、結局 O(n)。vector の insert(v.begin() + i, x) も O(n) なので、計算量だけ見ると差は無い。
new）ため、実測では vector が 3〜10 倍速いケースも珍しくありません。それでも list を選ぶ価値がある場面は 3 つ。
splice ― 別のリストから O(1) で要素を移動splice はリスト間でノードの所有権をポインタの付け替えだけで移せます。大量要素の移動が O(1) というのは vector では絶対に真似できない芸当。
vector は再確保（push_back で容量超過など）が起きると全要素がコピーされ、既存の反復子／ポインタはすべて無効化されます。list は各ノードが独立しているので、別のノードをいくら追加・削除しても、既存の反復子は生き続ける。
vector は拡張時に全要素をムーブ／コピーします。巨大な状態を持つ型（100MB のバッファを抱えたオブジェクトなど）を大量に入れる場合、list だとコピーが一切発生しない利点があります。ただし現代では大抵 std::unique_ptr を vector に入れる設計で解決します。
splice か「反復子が無効化されては困る」の具体的な理由が出てきたときにだけ検討するコンテナです。
std::forward_list（単方向リスト）std::list は双方向（前後の両方のポインタ）ですが、std::forward_list は前方のポインタのみ。各ノードのメモリが少しコンパクトになる代わりに、後ろに戻ることや size() の O(1) が犠牲になります。
| 項目 | std::list | std::forward_list |
|---|---|---|
| ポインタ | 前後両方 | 前のみ |
size() | O(1) | 提供されない（O(n) で自分で数える） |
push_front | O(1) | O(1) |
push_back | O(1) | 提供されない（末尾を知らない） |
| 反復子 | 双方向（++ / --） | 前方のみ（++ のみ） |
| メモリ／ノード | ポインタ 2 つ分多い | 少しコンパクト |
std::list すら使う頻度が低いので、forward_list は「こんなのもある」程度の認識で十分です。
2 問。
std::list<int> lst について、できない（提供されない）ものは？lst.push_back(10)lst.push_front(10)lst[3]（インデックスアクセス）lst.erase(it)std::list は連結リストなのでランダムアクセスができません。lst[i] も lst.at(i) もコンパイルエラー。i 番目が欲しければ std::next(lst.begin(), i) で反復子を進める必要があり、これは O(i)。std::list を選ぶ明確な理由になるのは？splice で別のリストから大量要素を O(1) で移したい