C++ STL のフォワード リスト
転送リスト コンテナは以下の実装を提供します 単一リンクリスト データ構造。データは、各要素がシーケンス内の次の要素を指す不連続メモリに保存されます。これにより、要素の位置がわかれば、挿入と削除がより速くなります。
構文
フォワードリストは次のように定義されます std::forward_list 内部のクラステンプレート < forward_list > ヘッダファイル。
forward_list
フロリダ;
どこ
- た: 前方リスト内の要素のデータ型。
- フ： 転送リストに割り当てられた名前。
宣言と初期化
以下の例に示すように、forward_list はいくつかの方法で宣言および初期化できます。
C++ #include using namespace std ; void printFL ( forward_list < int >& fl ) { for ( auto i : fl ) cout < < i < < ' ' ; cout < < 'n' ; } int main () { // Creating an empty forward_list forward_list < int > fl1 ; // Creating a forward_list with // default value forward_list < int > fl2 ( 3 4 ); // Creating a forward_list from an // initializer list forward_list < int > fl3 = { 1 5 3 4 }; printFL ( fl2 ); printFL ( fl3 ); return 0 ; }
出力
4 4 4 1 5 3 4
例： 上記のプログラムでは、次の 3 つの方法でフォワード リストを単純に初期化しています。
- 声明 forward_list
FL1 整数の空の前方リストを作成します。 - 声明 forward_list
fl2(34) サイズ 3 で各要素が 4 である前方リストを作成します。 - 声明 forward_list
fl3 = {1 5 3 4} 前方リストを作成し、初期化リストの要素を使用して初期化します。
基本操作
フォワード リストに対して実行できる基本的な操作は次のとおりです。
1. 要素へのアクセス
配列やベクトルなどのインデックスを使用して前方リストの要素にアクセスすることはできません。リストにアクセスするには、リストの先頭から目的の位置まで順番に移動する必要があります。これは増分することで実行できます 始める（） イテレータですが、使用する方が良いです 次（） または 前進（） 関数。
ただし、リストの最初の要素には次の方法で簡単にアクセスできます。 フロント（） 方法。
例：
C++ #include using namespace std ; int main () { forward_list < int > fl = { 1 5 3 4 }; // Access the first element cout < < fl . front () < < endl ; // Access third element auto it = next ( fl . begin () 2 ); cout < < * it ; return 0 ; }
出力
1 3
例： 上記のプログラムでは、最初の要素は次を使用して出力されます。 フロント（） 方法。 3 番目の要素にアクセスするには 次（） イテレータを先頭から 2 位置移動するために使用され、 *それ イテレータを逆参照するために使用されます。
2. 要素の挿入
次を使用して要素を前方リストに挿入できます。 挿入後() 関数。要素を挿入する後に反復子が必要です。ただし、前面での高速挿入はサポートされています。 プッシュ_フロント() 方法。
例：
C++ #include using namespace std ; int main () { forward_list < int > fl = { 5 4 }; // Inserting Element at front fl . push_front ( 1 ); // Insert 3 after the second element auto it = fl . begin (); advance ( it 1 ); fl . insert_after ( it 3 ); for ( auto x : fl ) cout < < x < < ' ' ; return 0 ; }
出力
1 5 3 4
説明： このプログラムでは、forward_list の最初の要素が、 プッシュ_フロント() 関数。次に、反復子が作成され、次のコマンドを使用して 1 つ前に移動されます。 前進（） 関数。その後の要素は 5 を使用して 2 番目の要素の後に挿入されます。 挿入後() 関数。
3. 要素の更新
既存の要素の値は、それらにアクセスして次のコマンドを使用するだけで変更できます。 代入演算子 新しい値を割り当てます。
例：
C++ #include using namespace std ; int main () { forward_list < int > fl = { 1 5 3 4 }; // Updating first element fl . front () = 111 ; cout < < fl . front () < < endl ; // Updating third element auto it = next ( fl . begin () 2 ); * it = 333 ; cout < < * it ; return 0 ; }
出力
111 333
4. 要素の検索
前方リストには要素を検索するためのメンバー関数がありませんが、 探す（） 与えられた値を見つけるアルゴリズム。
例 :
C++ #include using namespace std ; int main () { forward_list < int > fl = { 1 5 3 4 }; // Finding 3 auto it = find ( fl . begin () fl . end () 3 ); if ( it != fl . end ()) cout < < * it ; else cout < < 'Element not Found' ; return 0 ; }
出力
3
5. トラバース
前方リストは次を使用して走査できます。 始める（） そして 終わり（） ループを持つ反復子を使用しますが、前方にのみ移動でき、後方には移動できません。
例：
C++ #include using namespace std ; int main () { forward_list < int > fl = { 1 5 3 4 }; // Traversing using range-based for loop for ( auto i : fl ) cout < < i < < ' ' ; cout < < endl ; return 0 ; }
出力
1 5 3 4
6. 要素の削除
前方リストでは、次を使用して指定された位置にある要素を削除できます。 消去後() 方法。このメソッドは、反復子をターゲット要素の 1 つ前の位置に移動します。を使用すると前からの高速削除が可能です ポップフロント() 方法。
例：
C++ #include using namespace std ; int main () { forward_list < int > fl = { 1 5 3 4 }; // Delete first element fl . pop_front (); // Delete third element auto it = fl . begin (); advance ( it 1 ); fl . erase_after ( it ); for ( auto x : fl ) cout < < x < < ' ' ; return 0 ; }
出力
5 3
7. フォワードリストのサイズ
forward_list には組み込みの size() 関数がありません。サイズを確認するには、ループで走査するか、std:: distance を使用して要素を手動でカウントする必要があります。
C++ #include #include #include using namespace std ; int main () { forward_list < int > flist = { 10 20 30 40 }; //Calculate size by counting elements using std:: distance int size = distance ( flist . begin () flist . end ()); cout < < 'Size of forward_list: ' < < size < < endl ; return 0 ; }
出力
Size of forward_list: 4
8. 空()
forward_list が空かどうかを確認するために使用されます。
リストが空の場合は true を返し、そうでない場合は false を返し、コンテナーにデータがないかどうかを迅速に確認できます。
#include #include using namespace std ; int main () { forward_list < int > flist ; if ( flist . empty ()) { cout < < 'The forward_list is empty.' < < endl ; } flist . push_front ( 10 ); if ( ! flist . empty ()) { cout < < 'The forward_list is not empty.' < < endl ; } return 0 ; }
出力
The forward_list is empty. The forward_list is not empty.
時間計算量
以下の表は、フォワード リストでの上記の操作の時間計算量を示しています。
| 手術 | 時間計算量 |
|---|---|
| 最初の要素にアクセスする | ○(1) |
| アクセスn 番目 要素 | の上） |
| 前に挿入 | ○(1) |
| 特定の位置の後に挿入 | の上） |
| 最初の要素を削除 | ○(1) |
| 特定の位置以降を削除 | の上） |
| トラバーサル | の上） |
フォワードリストとリストの比較
| 特徴 | forward_list | リスト |
|---|---|---|
| リンクされたリストの種類 | 単一リンクリスト | 二重リンクリスト |
| トラバーサル | 前進のみトラバース可能 | 前方にも後方にも横断可能 |
| メモリ使用量 | 使用するメモリが少なくなります (ノードごとにポインターが 1 つだけ) | より多くのメモリを使用します (ノードごとに 2 つのポインター) |
| 挿入・削除 | 高速な挿入と削除（ただし、指定された位置以降のみ） | どこでも (位置の前または後) 迅速な挿入と削除 |
| サポートされている機能 | リストに比べて制限がある (size() なし、逆反復子なし) | size() reverse() 双方向反復子を含む、より完全なインターフェイス。 |
| | | |
