MENU
  1. ホーム
  2. C++
  3. STL
  4. コンテナ
  5. forward_list
  6. 【C++】std::forward_listの使い方について解説

【C++】std::forward_listの使い方について解説

forward_list

この記事では、C++の標準ライブラリに含まれるstd::forward_listについて詳しく解説します。

std::forward_listは単方向リスト(シングルリンクリスト)を実装したコンテナで、メモリ効率が高く、特に挿入や削除操作が頻繁に行われる場合に有利です。

この記事を読むことで、std::forward_listの基本的な使い方や操作方法、応用的な使い方、そしてパフォーマンスについて理解することができます。

初心者の方でもわかりやすいように、サンプルコードとその実行結果を交えながら解説していきますので、ぜひ最後までご覧ください。

目次から探す

std::forward_listとは

std::forward_listの概要

std::forward_listは、C++標準ライブラリに含まれるコンテナの一つで、単方向リスト(シングルリンクリスト)を実装しています。

単方向リストは、各要素が次の要素へのポインタを持つことで構成されており、前方向にのみ走査が可能です。

これに対して、双方向リスト(ダブルリンクリスト)は各要素が前後の要素へのポインタを持ち、前後両方向に走査が可能です。

std::forward_listは、メモリ効率が高く、特に挿入や削除操作が頻繁に行われる場合に有利です。

これは、要素の追加や削除がリストの途中であっても一定時間で行えるためです。

std::forward_listとstd::listの違い

std::forward_listとstd::listの主な違いは、以下の通りです：

  • リンクの方向：
  • std::forward_listは単方向リストであり、各要素は次の要素へのポインタを持つのみです。
  • std::listは双方向リストであり、各要素は前後の要素へのポインタを持ちます。
  • メモリ使用量：
  • std::forward_listは各要素が次の要素へのポインタを一つだけ持つため、メモリ使用量が少なくなります。
  • std::listは各要素が前後の要素へのポインタを持つため、メモリ使用量が多くなります。
  • 操作の効率：
  • std::forward_listは前方向にのみ走査が可能であり、特定の位置へのアクセスが効率的ではありません。
  • std::listは前後両方向に走査が可能であり、特定の位置へのアクセスが比較的効率的です。

std::forward_listの利点と欠点

利点：

  1. メモリ効率：
  • std::forward_listは各要素が次の要素へのポインタを一つだけ持つため、メモリ使用量が少なくなります。
  1. 挿入と削除の効率：
  • リストの途中であっても、要素の追加や削除が一定時間で行えるため、挿入と削除の操作が効率的です。
  1. シンプルな構造：
  • 単方向リストのシンプルな構造により、実装が簡単であり、特定の用途に対して最適化しやすいです。

欠点：

  1. 前方向にのみ走査可能：
  • std::forward_listは前方向にのみ走査が可能であり、特定の位置へのアクセスが効率的ではありません。
  1. ランダムアクセスが非効率：
  • リストの途中の要素にアクセスするためには、先頭から順に走査する必要があるため、ランダムアクセスが非効率です。
  1. 機能の制限：
  • std::listに比べて提供される機能が少なく、特定の操作がサポートされていない場合があります。

以上のように、std::forward_listは特定の用途に対して非常に有効なコンテナですが、その特性を理解し、適切な場面で使用することが重要です。

次のセクションでは、std::forward_listの基本的な使い方について詳しく解説します。

std::forward_listの基本的な使い方

std::forward_listの宣言と初期化

デフォルトコンストラクタ

std::forward_listを使うためには、まずその宣言と初期化方法を理解する必要があります。

デフォルトコンストラクタを使うと、空のリストが作成されます。

#include <forward_list>
#include <iostream>
int main() {
    std::forward_list<int> flist;
    std::cout << "リストの初期化が完了しました。" << std::endl;
    return 0;
}

初期化リストを使ったコンストラクタ

初期化リストを使うと、リストを特定の値で初期化することができます。

#include <forward_list>
#include <iostream>
int main() {
    std::forward_list<int> flist = {1, 2, 3, 4, 5};
    for (int n : flist) {
        std::cout << n << " ";
    }
    std::cout << std::endl;
    return 0;
}

このコードを実行すると、リストの要素が順に出力されます。

イテレータを使ったコンストラクタ

イテレータを使って、他のコンテナからstd::forward_listを初期化することもできます。

#include <forward_list>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::forward_list<int> flist(vec.begin(), vec.end());
    for (int n : flist) {
        std::cout << n << " ";
    }
    std::cout << std::endl;
    return 0;
}

要素の追加と削除

push_frontとemplace_front

std::forward_listでは、要素をリストの先頭に追加するためにpush_frontとemplace_frontを使用します。

#include <forward_list>
#include <iostream>
int main() {
    std::forward_list<int> flist = {2, 3, 4};
    flist.push_front(1); // 先頭に1を追加
    flist.emplace_front(0); // 先頭に0を追加
    for (int n : flist) {
        std::cout << n << " ";
    }
    std::cout << std::endl;
    return 0;
}

pop_front

pop_frontを使うと、リストの先頭要素を削除することができます。

#include <forward_list>
#include <iostream>
int main() {
    std::forward_list<int> flist = {1, 2, 3, 4, 5};
    flist.pop_front(); // 先頭の1を削除
    for (int n : flist) {
        std::cout << n << " ";
    }
    std::cout << std::endl;
    return 0;
}

insert_afterとemplace_after

insert_afterとemplace_afterを使うと、指定した位置の後に要素を追加することができます。

#include <forward_list>
#include <iostream>
int main() {
    std::forward_list<int> flist = {1, 3, 4};
    auto it = flist.begin();
    flist.insert_after(it, 2); // 1の後に2を追加
    flist.emplace_after(it, 1); // 1の後に1を追加
    for (int n : flist) {
        std::cout << n << " ";
    }
    std::cout << std::endl;
    return 0;
}

erase_after

erase_afterを使うと、指定した位置の後の要素を削除することができます。

#include <forward_list>
#include <iostream>
int main() {
    std::forward_list<int> flist = {1, 2, 3, 4, 5};
    auto it = flist.begin();
    flist.erase_after(it); // 2を削除
    for (int n : flist) {
        std::cout << n << " ";
    }
    std::cout << std::endl;
    return 0;
}

要素のアクセス

frontメソッド

frontメソッドを使うと、リストの先頭要素にアクセスすることができます。

#include <forward_list>
#include <iostream>
int main() {
    std::forward_list<int> flist = {1, 2, 3, 4, 5};
    std::cout << "先頭要素: " << flist.front() << std::endl;
    return 0;
}

イテレータを使ったアクセス

イテレータを使って、リストの要素に順にアクセスすることができます。

#include <forward_list>
#include <iostream>
int main() {
    std::forward_list<int> flist = {1, 2, 3, 4, 5};
    for (auto it = flist.begin(); it != flist.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    return 0;
}

以上が、std::forward_listの基本的な使い方に関する解説です。

次のセクションでは、std::forward_listの操作について詳しく見ていきます。

std::forward_listの操作

要素の検索

findメソッド

std::forward_listでは、標準ライブラリのアルゴリズムを使って要素を検索することができます。

例えば、std::findを使って特定の要素を検索する方法を見てみましょう。

#include <iostream>
#include <forward_list>
#include <algorithm> // std::find
int main() {
    std::forward_list<int> flist = {1, 2, 3, 4, 5};
    // 要素3を検索
    auto it = std::find(flist.begin(), flist.end(), 3);
    if (it != flist.end()) {
        std::cout << "要素3が見つかりました: " << *it << std::endl;
    } else {
        std::cout << "要素3が見つかりませんでした" << std::endl;
    }
    return 0;
}

このコードでは、std::findを使ってstd::forward_list内の要素3を検索しています。

見つかった場合はその要素を出力し、見つからなかった場合は見つからなかった旨を出力します。

countメソッド

std::forward_list内の特定の要素の出現回数を数えるには、std::countを使用します。

#include <iostream>
#include <forward_list>
#include <algorithm> // std::count
int main() {
    std::forward_list<int> flist = {1, 2, 3, 2, 4, 2, 5};
    // 要素2の出現回数を数える
    int count = std::count(flist.begin(), flist.end(), 2);
    std::cout << "要素2の出現回数: " << count << std::endl;
    return 0;
}

このコードでは、std::countを使ってstd::forward_list内の要素2の出現回数を数えています。

要素のソート

sortメソッド

std::forward_listの要素をソートするには、sortメソッドを使用します。

デフォルトでは昇順にソートされます。

#include <iostream>
#include <forward_list>
int main() {
    std::forward_list<int> flist = {5, 3, 1, 4, 2};
    // 要素を昇順にソート
    flist.sort();
    std::cout << "ソート後のリスト: ";
    for (int n : flist) {
        std::cout << n << " ";
    }
    std::cout << std::endl;
    return 0;
}

このコードでは、sortメソッドを使ってstd::forward_listの要素を昇順にソートしています。

uniqueメソッド

uniqueメソッドを使うと、連続する重複要素を削除することができます。

ただし、リストはソートされている必要があります。

#include <iostream>
#include <forward_list>
int main() {
    std::forward_list<int> flist = {1, 2, 2, 3, 3, 3, 4, 5, 5};
    // 連続する重複要素を削除
    flist.unique();
    std::cout << "重複要素削除後のリスト: ";
    for (int n : flist) {
        std::cout << n << " ";
    }
    std::cout << std::endl;
    return 0;
}

このコードでは、uniqueメソッドを使って連続する重複要素を削除しています。

要素の逆順

reverseメソッド

reverseメソッドを使うと、std::forward_listの要素を逆順にすることができます。

#include <iostream>
#include <forward_list>
int main() {
    std::forward_list<int> flist = {1, 2, 3, 4, 5};
    // 要素を逆順にする
    flist.reverse();
    std::cout << "逆順後のリスト: ";
    for (int n : flist) {
        std::cout << n << " ";
    }
    std::cout << std::endl;
    return 0;
}

このコードでは、reverseメソッドを使ってstd::forward_listの要素を逆順にしています。

要素の削除

removeメソッド

removeメソッドを使うと、特定の値を持つ要素を削除することができます。

#include <iostream>
#include <forward_list>
int main() {
    std::forward_list<int> flist = {1, 2, 3, 2, 4, 2, 5};
    // 要素2を削除
    flist.remove(2);
    std::cout << "要素2削除後のリスト: ";
    for (int n : flist) {
        std::cout << n << " ";
    }
    std::cout << std::endl;
    return 0;
}

このコードでは、removeメソッドを使ってstd::forward_list内の要素2をすべて削除しています。

remove_ifメソッド

remove_ifメソッドを使うと、特定の条件を満たす要素を削除することができます。

#include <iostream>
#include <forward_list>
int main() {
    std::forward_list<int> flist = {1, 2, 3, 4, 5};
    // 偶数の要素を削除
    flist.remove_if([](int n) { return n % 2 == 0; });
    std::cout << "偶数要素削除後のリスト: ";
    for (int n : flist) {
        std::cout << n << " ";
    }
    std::cout << std::endl;
    return 0;
}

このコードでは、remove_ifメソッドを使ってstd::forward_list内の偶数の要素をすべて削除しています。

以上が、std::forward_listの操作に関する基本的な使い方です。

これらのメソッドを活用することで、効率的にリストの操作を行うことができます。

std::forward_listの応用

カスタムコンパレータを使ったソート

std::forward_listでは、デフォルトのソートメソッドに加えて、カスタムコンパレータを使用して要素をソートすることができます。

カスタムコンパレータを使うことで、特定の条件に基づいてリストを並べ替えることが可能です。

以下に、カスタムコンパレータを使ったソートの例を示します。

#include <iostream>
#include <forward_list>
#include <algorithm>
// カスタムコンパレータ
bool customCompare(int a, int b) {
    return a > b; // 降順にソート
}
int main() {
    std::forward_list<int> flist = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    // カスタムコンパレータを使ってソート
    flist.sort(customCompare);
    // 結果を表示
    for (int n : flist) {
        std::cout << n << " ";
    }
    return 0;
}

このコードでは、customCompare関数を使用して、リストを降順にソートしています。

実行結果は以下の通りです。

9 6 5 5 4 3 2 1 1

カスタム条件を使った削除

std::forward_listでは、カスタム条件を使って要素を削除することも可能です。

remove_ifメソッドを使用して、特定の条件に一致する要素をリストから削除します。

以下に、カスタム条件を使った削除の例を示します。

#include <iostream>
#include <forward_list>
// カスタム条件
bool isOdd(int n) {
    return n % 2 != 0; // 奇数を削除
}
int main() {
    std::forward_list<int> flist = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    // カスタム条件を使って削除
    flist.remove_if(isOdd);
    // 結果を表示
    for (int n : flist) {
        std::cout << n << " ";
    }
    return 0;
}

このコードでは、isOdd関数を使用して、リストから奇数の要素を削除しています。

実行結果は以下の通りです。

4 2 6

std::forward_listを使ったアルゴリズムの実装

単方向リストのマージ

std::forward_listを使って、2つのリストをマージすることができます。

mergeメソッドを使用すると、2つのリストを1つに結合し、ソートされた状態を保つことができます。

以下に、単方向リストのマージの例を示します。

#include <iostream>
#include <forward_list>
int main() {
    std::forward_list<int> flist1 = {1, 3, 5, 7};
    std::forward_list<int> flist2 = {2, 4, 6, 8};
    // リストをマージ
    flist1.merge(flist2);
    // 結果を表示
    for (int n : flist1) {
        std::cout << n << " ";
    }
    return 0;
}

このコードでは、flist1とflist2をマージして、1つのソートされたリストにしています。

実行結果は以下の通りです。

1 2 3 4 5 6 7 8

単方向リストの分割

std::forward_listを使って、リストを特定の条件に基づいて分割することも可能です。

以下に、リストを分割する例を示します。

#include <iostream>
#include <forward_list>
int main() {
    std::forward_list<int> flist = {1, 2, 3, 4, 5, 6, 7, 8};
    std::forward_list<int> evenList;
    std::forward_list<int> oddList;
    // リストを分割
    for (int n : flist) {
        if (n % 2 == 0) {
            evenList.push_front(n); // 偶数リストに追加
        } else {
            oddList.push_front(n); // 奇数リストに追加
        }
    }
    // 偶数リストを表示
    std::cout << "Even List: ";
    for (int n : evenList) {
        std::cout << n << " ";
    }
    std::cout << std::endl;
    // 奇数リストを表示
    std::cout << "Odd List: ";
    for (int n : oddList) {
        std::cout << n << " ";
    }
    return 0;
}

このコードでは、元のリストを偶数と奇数のリストに分割しています。

実行結果は以下の通りです。

Even List: 8 6 4 2 
Odd List: 7 5 3 1

以上が、std::forward_listの応用的な使い方です。

カスタムコンパレータやカスタム条件を使った操作、そしてリストのマージや分割といったアルゴリズムの実装方法を理解することで、std::forward_listをより効果的に活用できるようになります。

std::forward_listのパフォーマンス

メモリ使用量

std::forward_listは単方向リスト(シングルリンクリスト)として実装されており、各要素は次の要素へのポインタを持っています。

このため、std::list(ダブルリンクリスト)と比較してメモリ使用量が少なくなります。

std::listでは各要素が前後の要素へのポインタを持つため、メモリ使用量が増加します。

以下に、std::forward_listとstd::listのメモリ使用量の違いを示す簡単な例を示します。

#include <iostream>
#include <forward_list>
#include <list>
int main() {
    std::forward_list<int> flist = {1, 2, 3, 4, 5};
    std::list<int> dlist = {1, 2, 3, 4, 5};
    std::cout << "Size of std::forward_list: " << sizeof(flist) << " bytes" << std::endl;
    std::cout << "Size of std::list: " << sizeof(dlist) << " bytes" << std::endl;
    return 0;
}

このコードを実行すると、std::forward_listの方がstd::listよりもメモリ使用量が少ないことが確認できます。

操作の時間計算量

std::forward_listの操作の時間計算量は以下の通りです：

操作説明時間計算量
要素の追加(push_front, emplace_front)O(1)
要素の削除(pop_front)O(1)
要素の挿入(insert_after, emplace_after)挿入位置が既に分かっている場合O(1)
要素の削除(erase_after)削除位置が既に分かっている場合O(1)
要素の検索O(n)
要素のソートO(n log n)
要素の逆順O(n)

以下に、std::forward_listの操作の時間計算量を示す例を示します。

#include <iostream>
#include <forward_list>
#include <algorithm>
int main() {
    std::forward_list<int> flist = {5, 3, 1, 4, 2};
    // 要素の追加
    flist.push_front(0);
    // 要素の削除
    flist.pop_front();
    // 要素のソート
    flist.sort();
    // 要素の逆順
    flist.reverse();
    // 要素の検索
    auto it = std::find(flist.begin(), flist.end(), 3);
    if (it != flist.end()) {
        std::cout << "Element found: " << *it << std::endl;
    } else {
        std::cout << "Element not found" << std::endl;
    }
    return 0;
}

std::forward_listの最適な使用シーン

std::forward_listは以下のようなシーンで最適です：

  • メモリ効率が重要な場合: std::forward_listはメモリ使用量が少ないため、メモリ効率が重要なアプリケーションに適しています。
  • 頻繁に要素を追加・削除する場合: std::forward_listは要素の追加・削除がO(1)で行えるため、頻繁に要素を追加・削除する操作が多い場合に適しています。
  • 順次アクセスが主な場合: std::forward_listは単方向リストであるため、順次アクセスが主な操作である場合に適しています。

一方で、ランダムアクセスが必要な場合や、前後の要素へのアクセスが頻繁に必要な場合には、std::vectorやstd::listの方が適していることがあります。

以上のように、std::forward_listは特定のシーンで非常に有用なデータ構造ですが、使用する際にはその特性を理解し、適切な場面で利用することが重要です。

まとめ

std::forward_listの利点の再確認

std::forward_listは、C++標準ライブラリに含まれる単方向リストのコンテナです。

以下に、std::forward_listの主な利点を再確認します。

  1. メモリ効率:

std::forward_listは単方向リストであるため、各ノードが次のノードへのポインタを1つだけ持ちます。

これにより、双方向リスト(std::list)に比べてメモリ使用量が少なくなります。

  1. 高速な挿入と削除:

単方向リストの特性上、リストの先頭や特定の位置への要素の挿入や削除が高速に行えます。

特に、リストの先頭への操作はO(1)の時間計算量で行えます。

  1. シンプルな構造:

std::forward_listはシンプルな構造を持ち、実装が比較的簡単です。

これにより、特定の用途において効率的に利用できます。

std::forward_listを使う際の注意点

一方で、std::forward_listを使用する際にはいくつかの注意点があります。

以下にその主な点を挙げます。

  1. ランダムアクセスができない:

std::forward_listは単方向リストであるため、ランダムアクセスができません。

特定の要素にアクセスするためには、リストの先頭から順に辿る必要があります。

これにより、アクセス時間がO(n)となる場合があります。

  1. 双方向の操作ができない:

std::forward_listは単方向リストであるため、後ろ向きの操作(例えば、前の要素に戻る操作)ができません。

これにより、特定のアルゴリズムや操作が制限されることがあります。

  1. サイズの取得が遅い:

std::forward_listはサイズを保持していないため、サイズを取得するためにはリスト全体を走査する必要があります。

これにより、サイズの取得がO(n)の時間計算量となります。

  1. 特定の操作が制限される:

std::forward_listは単方向リストであるため、std::listやstd::vectorに比べて利用できる操作が制限されることがあります。

例えば、リストの末尾への挿入や削除が効率的に行えない場合があります。

以上の利点と注意点を理解した上で、std::forward_listを適切に利用することで、効率的なプログラムを作成することができます。

用途に応じて、他のコンテナ(std::vectorやstd::listなど)との使い分けを検討することが重要です。

目次に戻る

当サイトはリンクフリーです。出典元を明記していただければ、ご自由に引用していただいて構いません。

forward_list

関連記事

関連する記事はまだ見つかりませんでした。

目次から探す