単方向リストクラス std::forward_list とは

std::forward_list とは C++ で標準に使用できる便利な単方向リストクラスでござるぞ。
「単方向リスト」とは、要素を格納するノードが次のノードへのポインタを持ち、どの位置への挿入・削除でも O(1) と高速に処理できるコンテナクラスだぞ。
※ 「コンテナクラス」とは、単一タイプ・データ構造の複数のデータを取り扱うためのクラスのことだぞ

双方向リストクラス std::list と比べると、前の要素へのポインタを持たない分、メモリ効率がよい。
また、何故か size() メンバ関数を持たないので、要素数を取得する場合は標準アルゴリズムの std::distance() を呼ばなくてはいけない。

vector, array, deque 等の配列様コンテナに比べると、任意の位置への要素の挿入・削除が O(1) と高速であるという長所がある。
その半面、ランダム・アクセスができず、任意の位置へのアクセスには O(N) の時間がかかってしまうという短所がある。

	ランダム・アクセス	任意位置への挿入・削除
vector, array, deque	O(1)	O(N)
forward_list, list	O(N)	O(1)

データ構造

std::forward_list のデータ構造の例を下図に示す。

std::vector との大きな違いは、各要素が独立したメモリ領域（これをノードと呼ぶ）に入っているという点である。 そしてそれらのノードはポインタにより順次リンクされている。

std::list は各ノードは前後への2つのポインタを持つが、forward_list はひとつだけである。
std::forward_list が、「単方向（リンク）」と呼ばれるのはそのためだ。

準備：インクルード

まずは、list を使うための準備について説明する。

list は C++標準ライブラリに含まれており、「#include <list>」を記述することで利用可能になる。

名前空間は「std」なので、使用の度に「std::」を前置するか、または「using namespace std;」を記述しておく。

#include <forward_list>       // ヘッダファイルインクルード
int main()
{
    std::forward_list<_int> lst;       // ローカル変数として、lst を生成
    .....
}

#include <forward_list>       // ヘッダファイルインクルード
using namespace std;         //  名前空間指定
int main()
{
    forward_list<int> lst;       // ローカル変数として、lst を生成
    .....
}

宣言・初期化

forward_list オブジェクトを宣言するには、空forward_listを宣言する、サイズを指定して宣言する、サイズと全てのデータを指定して宣言する、 元データを指定して宣言する、他のオブジェクトを元にして宣言する、のようにいくつもの方法がある。 本章ではそれらの方法を順次解説する。

ローカル変数またはグローバル変数として forward_list オブジェクトを宣言すると、オブジェクトが生成され利用可能になる。
これらはスコープを外れると自動的に破棄される。

通常のクラスなので new で生成し、delete で破棄することも可能だ。

単純な宣言

std::forward_list オブジェクトを生成するには「std::forward_list<型> オブジェクト名;」 と記述する。
オブジェクト名とは、宣言する単方向リストを識別するための名前のことだ。変数名と言ってもよい。 forward_list はクラスなので、それを実体化したものはオブジェクトまたはインスタンスと呼ばれる。
下記は、int 型の単方向リストdata を宣言している例だ。

    std::forward_list<int> lst;  //  int 型の単方向リスト lst の宣言

当然、型の部分はどんな型でも構わない。char や double や、自分で定義した構造体、クラスでもOKだ。
※ ただし、初期化時にデフォルトコンストラクタ、バッファ拡張時にコピーコンストラクタが呼ばれことがあるので、 それらがちゃんと定義されている必要がある。
また、vector などのコンテナクラスや string などを指定することも出来る。

「std::forward_list<型> オブジェクト名;」には要素数の指定が無いじゃないかと気づいた人は観察力がある。要素数の指定方法は次節で説明する。

このようにして宣言したオブジェクトの要素数は0だ。データを追加するには次の章で説明する push_front() などを使う。

< > は何だ？と思う人もいるかもしれない。これはC++のテンプレートという機能を使うための記法だ。
テンプレートを完全に理解するのは難易度が高いので、深く理解しようとすると先に進めなくなる。 深入りはせず、現在のところは取り扱うデータの型をこういう書き方で指定すると無条件で覚えてほしい。

要素数を指定した宣言

forward_list は後でサイズを増減させることが出来るが、あらかじめ要素数を指定してオブジェクトを作ることも出来る。
vector の場合、データ領域が連続しているために、データ領域が足りなくなった場合にメモリのアロケートとデータコピーが必要だ。 だが、forward_list は個々のデータ領域が独立なので、予め要素数を指定してオブジェクトを作るメリットは vector ほどは無い。
構文は「std::forward_list<型> オブジェクト名(要素数);」だ。

    std::forward_list<int> lst(123);  //  int 型で、初期要素数 123 の単方向リスト lst の宣言

配列では要素数を「[要素数]」で指定するが、forward_list では「(要素数)」で指定する。実はこれ、コンストラクタの引数なのである。

要素の初期化

要素数を指定するだけでなく、全要素の値を指定することも可能だ。
「std::forward_list<型> オブジェクト名(要素数, 値);」と記述すると、指定された数の要素を確保し、全ての要素を指定された値で初期化する。

    std::forward_list<int> lst(10, 5);      //  要素数10、全ての要素の値5 で初期化

上記の方法では、値が全て同じ場合でないと初期化できない。
「std::forward_list<型> オブジェクト名(型* first, 型* last);」と記述すると、first から last が指す先までのデータで単方向リストを初期化する。 厳密に言うと、last は最後の元データの次を指す。[first, last) の範囲を元に、単方向リストを初期化する。
通常配列でデータを指定し、それを元に単方向リストを構築出来る。

    int org_data[] = {4, 6, 5};      // 元データ
    std::forward_list<int> lst(org_data, org_data + 3);     // 元データから単方向リストを生成

配列末尾へのポインタは org_data + 3 と記述しているが、データ配列サイズが変わった時に、修正しなくてはならないので、危険だ。
C++0x（VS2010以上）で std::end(配列名) という関数が追加され、配列末尾へのポインタを返してくれるようになった。
これを使えば、上記は下記のように記述することが出来る。

    int org_data[] = {4, 6, 5};      // 元データ
    std::forward_list<int> lst(org_data, std::end(org_data));     // 元データから単方向リストを生成

実は上記の記述方法は古い書き方で、C++11（VS2013以上）から初期化子で初期値を直接指定可能になった。
「std::forward_list<型> オブジェクト名{値0, 値1, 値2, ... 値N-1};」と記述できる。

    std::forward_list<int> lst{4, 6, 5};     // データ列を指定して単方向リストを生成

こちらの方法の方が直感的で分かりやすく、行数も短い。C++11 が利用可能であれば、この記法を使うことを強く薦める。

※ ちなみに、「std::forward_list<型> オブジェクト名 = {値0, 値1, 値2, ... 値N-1};」と書いてもよい。

コピーコンストラクタ

コピーコンストラクタとは、同じ型のオブジェクトを渡され、それと同じ内容のオブジェクトを生成するコンストラクタのことである。
「std::forward_list<型> オブジェクト名(コピー元オブジェクト名);」と記述する。
当然ながら、コピー元オブジェクトと生成するオブジェクトは通常同じ型である。
※ 暗黙の型変換が可能な型であれば、コピー元オブジェクトとして指定可能ではある。

    std::forward_list<int> org{1, 2, 3};
    std::forward_list<int> x(org);      // コピーコンストラクタ

上記のコードは org をコピーするので {1, 2, 3} という値をもつ単方向リスト x を生成する。

※ 余談：forward_list オブジェクトの宣言方法は vector のそれと全く同一である。このように仕様に共通性があることを直交性があると言う。 直交性がある仕様は、ひとつ覚えると他にもすぐ使えて便利である。
だたし、後で出てくるが、ランダム・アクセスなど、forward_list と vector の仕様は完全に同一ではないので、例外的な部分はしっかり抑えておく必要はある。

演習問題：

1. char 型の単方向リスト str を宣言しなさい。show

    std::forward_list<char> str;

2. 要素数３の double 型の単方向リスト pos を宣言しなさい。show

    std::forward_list<double> pos(3);

3. char 型、値 'a'、要素数10の単方向リスト a を宣言するコードをビルドし、デバッガで中身を確認しなさい。 show

    std::forward_list<char> a(10, 'a');

4. double 型、1.1, 2.2, 3.3, 4.4 の4つの値をもつ単方向リスト d を宣言するコードをビルドし、デバッガで中身を確認しなさい。 show

    std::forward_list<double> d{1.1, 2.2, 3.3, 4.4};

5. コピーコンストラクタのサンプルコードをビルドし、デバッガで正しくコピーされていることを確認しなさい。 show

    std::forward_list<int> org{1, 2, 3};
    std::forward_list<int> x(org);      // コピーコンストラクタ

値の参照、代入

イテレータ

落胆する人もいるかもしれないが、forward_list には operator[](size_t) が無い。つまり lst の ix 番目の要素を lst[ix] で参照することが出来ない。
何故できないかと言うと、最初の方で書いたように、ix 番目のデータに移動するコストが O(N) と高いので、 コーダが安易にランダム・アクセスを行うコードを書いてパフォーマンスを低下させないよう、あえて operator[](size_t) が定義されていないのだ。

では、どうやって任意の箇所のデータを参照するかと言うと、イテレータ（iterator）というものを利用する。

イテレータとは抽象化されたポインタのことである。ポインタなので、要素を指していてイテレータ経由で要素の参照・修正が出来、別の要素に移動することが出来る。

もう少し具体的に言うと、begin() で先頭, end() で末尾の次の要素へのイテレータを取得でき、++ 演算子でイテレータを進めることができ （双方向リストと違い、-- 演算子でイテレータを戻すことは出来ない）、 * 演算子でイテレータが指す要素を参照することができる。
++ でひとつ移動でき、* で要素を参照できるという機能は通常のポインタと同じである。 が、内部的にはポインタと同じというわけではない。これが抽象化されたポインタと呼ばれる理由だ。

イテレータの型は std::forward_list<型>::iterator と記述する。少々めんどくさい。
たとえば、std::forward_list<int> lst の最初の要素を指すイテレータを取得したい場合は以下のように記述する。

    std::forward_list<int> lst;
    std::forward_list<int>::iterator itr = lst.begin();        // 最初の要素を指すイテレータ

イテレータ型の記述は少々長ったらしく面倒だが、C++0x（VS2010以上）からは auto で型推論が可能になったので、 上記は以下のように記述するのが普通である。

    std::forward_list<int> lst;
    auto itr = lst.begin();          //  最初の要素を指すイテレータ

イテレータが指すデータを参照する場合は、ポインタと同じ用に * 演算子を使用する。右辺値として記述すれば値を参照し、左辺値として書けば値の代入となる。

    std::forward_list<int> lst{1, 2, 3};
    auto itr = lst.begin();          //  最初の要素を指すイテレータ
    std::cout << *itr;               //  itr は最初の要素を指しているので 1 を表示
    *itr = 9;                    // 最初の要素を 9 に変更

forward_list オブジェクトが保持する全ての要素を表示するには、以下のように記述する。

    std::forward_list<int> lst;
    for(auto itr = lst.begin(); itr != lst.end(); ++itr) {
        std::cout << *itr << "\n";
    }

このような書き方は非常によく出てくるので、イディオムとして覚えておいて欲しい。

※ forward_list のイテレータは大小比較できないので、itr < lst.end() とは書けない。

itr を ix 番目のデータに移動するには、「itr = lst.begin();」で先頭データを指すようにしたのち、「++itr;」を ix 回繰り返す。
forward_list のイテレータは通常のポインタの様に「itr += ix;」で一度に移動することは出来ない。

演習問題：

1. int 型の要素 {1, 2, 3, 4, 5, 6, 7} を持つ、単方向リスト lst を宣言し、その内容を表示するコードを書きなさい。 show

    std::forward_list<int> lst{1, 2, 3, 4, 5, 6, 7};
    for(auto itr = lst.begin(); itr != lst.end(); ++itr)
        std::cout << *itr << "\n";

2. int 型の要素 {1, 2, 3, 4, 5, 6, 7} を持つ、単方向リスト lst を宣言し、その内容を全て0に設定するコードを書きなさい。 show

    std::forward_list<int> lst{1, 2, 3, 4, 5, 6, 7};
    for(auto itr = lst.begin(); itr != lst.end(); ++itr)
        *itr = 0;

3. int 型の要素 {3, 3, 3, 3, 3, 3, 3} を持つ、単方向リスト lst を宣言し、３番目の要素を123に書き換えるコードを書きなさい。 show

    std::forward_list<int> lst{3, 3, 3, 3, 3, 3, 3};
    auto itr = lst.begin();      //  itr は最初の要素を指す
    ++itr;       // itr は 2番目 を指す
    ++itr;       // itr は 3番目 を指す
    *itr = 123;

4. int 型の要素 {3, 3, 3, 3, 3, 3, 3} を持つ、単方向リスト lst を宣言し、最後の要素を123に書き換えるコードを書きなさい。 ただし、begin() を使用せず end() を使用しなさい。 show

    std::forward_list<int> lst{3, 3, 3, 3, 3, 3, 3};
    auto itr = lst.end();     // itr は最後の次の要素を指す
    --itr;     //  itr は最後の要素を指す
    *itr = 123;

5. const forward_list<int> & を引数にとり、その要素をすべて表示する関数 void print(const forward_list<int> &lst) を定義しなさい。 show

void print(const forward_list<int> &lst)
{
    for(auto itr = lst.begin(); itr != lst.end(); ++itr) {
        cout << *itr << " ";
    }
    cout << "\n";
}

要素の追加

• push_front(値)
• insert_after(イテレータ, 値) : iterator

データを先頭に追加するには push_front(値); を使う。

    std::forward_list<int> lst;       // 空の双方向リストを生成
    lst.push_front(987);     // 先頭に 987 を追加

双方向リストとは違い push_back() メンバ関数は無い。

push_front() の処理時間は O(1) で高速。O(式) は処理時間を表す数学的な記法。「ビッグ・オー記法」と呼ばれる。 O(1) は要素数に依らず常に一定時間で処理出来るという意味で、高速なのだ。

先頭以外の任意の場所にデータを挿入したい場合は insert_after(iterator, 値) を使う。
insert_after(iterator, 値) は、第1引数に値を追加する場所を指すイテレータを、第2引数に挿入する値を指定する。
イテレータは先に説明したものだ。ix 番目の直後に挿入するには begin() で先頭を取得し、++itr; を ix 回繰り返す。
そして、insert_after() は挿入したデータへのイテレータを返す。

list には insert(イテレータ, 値) があったが、forward_list にはそれが無い。list は双方向リンクなので、前のノードを簡単に取り出すことができるが、 forward_list は次のノードへの単方向リンクなので、直前のノードを取得することが出来ないために、このような仕様になっている。

例えば、データの値が 3 だったら、その直後に 0 を挿入するコードは以下のようになる。

    std::forward_list<int> lst{3, 4, 3, 2, 4, 3, 1};
    for(auto itr = lst.begin(); itr != lst.end(); ++itr) {
        if( *itr == 3 ) {
            itr = lst.insert_after(itr, 0);       // 3 の直後に 0 を挿入、itr は 0 を指す
        }
    }

慣れないと、少し混乱するかもしれないが、デバッガでトレースするなりしてしっかり理解して欲しい。

演習問題：

1. 空の int型 forward_list オブジェクトを生成し、先頭に 1 ～ 10 の値を順に挿入するコードを書きなさい。 show

    std::forward_list<int> lst;
    for(int i = 1; i <= 10; ++i)
        lst.push_front(i);

2. 先に示した 3 の前に 0 を挿入するコードをビルドし、デバッガで動作を確認しなさい。
3. 初期値 0 で、10個の int型 forward_list オブジェクトを生成し、[5] の位置の直後に 7 を挿入するコードを書きなさい。 show

    std::forward_list<int> lst(10, 0);
    auto itr = lst.begin();
    for(int i = 0; i < 5; ++i)
        ++itr;       // itr を先頭から５つ進める
    lst.insert_after(itr, 7);

4. 空の int型 forward_list オブジェクトを生成し、先頭に 0 を繰り返し追加するコードを書きなさい。 繰り返し回数が 10回、100回、1000回、10000回の場合の処理時間がどの程度かを計測しなさい。 show

※ 処理時間計測方法が分からない場合は、以下を参照してください。
手を動かしてさくさく理解する C/C++ 処理時間計測 入門

void listPushFront(int n)           //  n は繰り返し回数
{
    std::forward_list<int> lst;
    Timer tm;
    tm.restart();
    for (int i = 0; i < n; ++i) {
        lst.push_front(0);
    }
    auto dur = tm.elapsed();
    std::cout << "count = " << n << ", time = " << dur << "\n";
}
int main()
{
    cout << "forward_list.push_front():\n";
    listPushFront(10);
    listPushFront(100);
    listPushFront(1000);
    listPushFront(10000);
    return 0;
}

5. vector でも上記と同様のコードを書き、処理速度を比較しなさい。 show

void vectorPushFront(int n)          //  n は繰り返し回数
{
    std::vector<int> v;
    Timer tm;
    tm.restart();
    for (int i = 0; i < n; ++i) {
        v.insert(v.begin(), 0);
    }
    auto dur = tm.elapsed();
    std::cout << "count = " << n << ", time = " << dur << "\n";
}
int main()
{
    cout << "vector.push_front():\n";
    vectorPushFront(10);
    vectorPushFront(100);
    vectorPushFront(1000);
    vectorPushFront(10000);
    return 0;
}

要素の削除

• pop_front()
• erase_after(イテレータ) : iterator

最初の要素を削除したい場合は pop_front() を用いる。

    std::forward_list<int> lst{3, 1, 4, 1, 5};
    lst.pop_front();    //  先頭データ（この場合は 3）を削除

pop_front() の処理時間は O(1) と高速である。

先頭以外の任意の位置の要素を削除したい場合は erase_after(iterator) を使用する。

    std::forward_list<int> lst{3, 1, 9, 4};
    auto itr = lst.begin();
    ++itr;               // 2番目の要素に移動
    lst.erase_after(itr);       //  3番目の要素（9）を削除

erase() は削除した要素の次の要素へのイテレータを返す。
（上記の例だと、消した 9 の次の要素である 4 を指すイテレータを返す）

削除処理を図示すると下図の様になる。

削除前：

削除後：

std::vector の様に、削除された場所以降のデータを前にずらすのではなく、ポインタを付け替えるだけだ。 だから、削除処理が、要素数に依らず O(1) と定数時間で可能なのだ。

演習問題：

1. pop_front() で先頭を削除するコードを書き、デバッガで実行し、先頭データが削除されたことを確認しなさい。 show

    std::forward_list<int> lst{3, 1, 4, 1};
    lst.pop_front();

2. {3, 1, 4, 1} の要素をもつ単方向リスがあるとき、erase_after() で 3 番目の要素（4）を削除し、本当に削除されたことを確認するコードを書き、実行してみなさい。 show

    std::forward_list<int> lst{3, 1, 4, 1};
    auto itr = lst.begin();
    ++itr;       // 1 まで進める
    lst.erase_after(itr);
    for(auto itr = lst.begin(); itr != lst.end(); ++itr) {
        std::cout << *itr << "\n";
    }

3. 要素数1万個の std::forward_list<char> lst を作り、lst が空になるまで pop_front() で要素を削除する時間を計測しなさい。 要素数が、10万個、100万個と増えると、処理時間が何倍になるか計測しなさい。 show
4. 上記と同じことを vector で計測し（ヒント：vector には pop_front が無いので v.erase(v.begin()）を使用しなさい）、 forward_list の計測結果と比較しなさい。
5. forward_list<int>&, int を引数にとり、limit 未満の要素をすべて削除する関数
   void eraseLessThan(forward_list<int>& lst, int limit) を定義し、 テストしなさい。
   ヒント：empty(), front() は使用してよいものとする。
   例：limit = 4 の場合：{3, 1, 1, 4, 1, 5, 5, 5, 3, 1, 6} → {4, 5, 5, 5, 6} // 4 未満の要素を削除
   例：limit = 7 の場合：{1, 1, 1, 1, 5, 5, 5, 6} → {} // 7 未満の要素を削除 → 空になる
   例：limit = 0 の場合：{} → {} // 空のリストでコールしても大丈夫なことを確認するように！ show

void eraseLessThan(forward_list<int>& lst, int limit)
{
    while (!lst.empty() && lst.front() < limit) {     //  最初の要素が limit 未満の場合
        lst.pop_front();
    }
    if (lst.empty()) return;
    auto prev = lst.begin();
    auto itr = prev;
    ++itr;
    while( itr != lst.end() ) {
        if( *itr < limit ) {
            itr = lst.erase_after(prev);
        } else {
            prev = itr;
            ++itr;
        }
    }
}

6. forward_list<int>& を引数にとり、連続する要素が同じ値だった場合は、最初の要素以外を削除する関数 void uniq(forward_list<int>&lst) を定義し、 テストしなさい。
   ヒント：empty() は使用してよいものとする。
   例：{3, 1, 1, 4, 1, 5, 5, 5, 6} → {3, 1, 4, 1, 5, 6} // 1, 5 が連続しているので、最初以外を削除
   例：{1, 1, 1, 1, 5, 5, 5, 6} → {1, 5, 6} // 1, 5 が連続しているので、最初以外を削除
   例：{} → {} // 空のリストでコールしても大丈夫なことを確認するように！ show

void uniq(forward_list<int>&lst)
{
    if (lst.empty()) return;
    auto prev = lst.begin();
    auto itr = prev;
    ++itr;
    while( itr != lst.end() ) {
        if( *itr == *prev ) {     // 直前の値と同じだった場合
            itr = lst.erase_after(prev);
        } else {
            prev = itr;       // イテレータを前に進める
            ++itr;
        }
    }
}

要素のソート sort

標準アルゴリズムには std::sort(first, last) が用意されているのだが、引数に渡すイテレータはランダム・アクセス可能なものでないといけない。 残念なことに std::forward_list のイテレータはランダム・アクセス可能ではないので、std::sort() を利用することが出来ない。

下記は、ビルド時エラーとなる。

    std::forward_list<int> lst= {3, 1, 1, 4, 1, 5, 5, 5, 6};
    std::sort(lst.begin(), lst.end());        //  ビルド時エラー

それでは困る場合もあるので、sort() が forward_list のメンバ関数として用意されている。

使い方はいたって簡単、sort() を呼ぶだけだ。

    std::forward_list<int> lst= {3, 1, 1, 4, 1, 5, 5, 5, 6};
    lst.sort();

ただし、注意事項としては、forward_list 要素の型が大小比較できる（operator<() が定義されている）必要がある。 POD や string であれば既に定義されているが、自分で作った型の場合は operator<() をちゃんと定義しよう。

以下は、operator<() が定義されていないのでエラーになる。

class MyClass {
public:
    int _a;
};
int main() {
    std::forward_list<MyClass> lst;
    lst に値を設定;
    lst.sort();          // ビルドエラーになる
    return 0;
}

下記のように、operator<() を定義してあげるとエラーはなくなる。

class MyClass {
public:
    bool operator<(const MyClass &rhs) const
    {
        return _a < rhs._a;
    }
public:
    int _a;
};

演習問題：

1. forward_list<int> 型のオブジェクトを {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5} で初期化し、sort() でソートするコードを書きなさい。
2. forward_list<string> 型のオブジェクトを {"hoge", "xyzzz", "xyz", "abc", "a"} で初期化し、sort() でソートするコードを書きなさい。
3. operaor<() を定義しない MyClass の例をビルドし、エラーが出ることを確認しなさい。
4. operaor<() を定義した MyClass の例をビルドし、エラーが出なくなることを確認しなさい。

その他のメンバ関数

オブジェクトが空かどうかを判定

• empty() : bool

「bool empty()」は双方向リストが空かどうかを判定する関数。
std::list<int> lst; に対して、lst.empty() と書くと、lst が空ならば true を、空でなければ false を返す。

    std::forward_list<int> lst;
    if( lst.empty() )
        std::cout << "empty.\n";
    else
        std::cout << "not empty.\n";
    std::forward_list<int> lst2{1, 2, 3};
    if( lst2.empty() )
        std::cout << "empty.\n";
    else
        std::cout << "not empty.\n";

リストの先頭要素を取得

• front()

「front()」は先頭要素の値を返す関数。「*(lst.begin())」と記述するのと同等。

    std::forward_list<int> lst{1, 2, 3};
    std::cout << lst.front() << "\n";     //  先頭の 1 が表示される

オブジェクトの状態を変更

• clear()
• resize(サイズ)
• resize(サイズ, 値)
• swap(forward_list &)
• remove(値)
• reverse()
• sort()

「clear()」は双方向リストを空にする関数。
サイズを0にする。vector とは違い、要素を delete し、メモリが解放される。

    std::forward_list<int> lst{3, 1, 4};
    lst.clear();     //  要素をクリア

「resize(サイズ)」は、単方向リストを指定サイズにする。サイズが増える場合は、型のデフォルト値が用いられる。
「resize(サイズ、値)」は、単方向リストを指定サイズにする。サイズが増える場合は、指定値が用いられる。

    forward_list<int> lst{3, 1, 4, 1, 5};
    lst.resize(3);
    for(auto x : lst) cout << x << " ";
    cout << "\n";
    lst.resize(5);
    for(auto x : lst) cout << x << " ";
    cout << "\n";

「lst.swap(lst2)」は lst の内容と lst2 の内容を入れ替える。

    forward_list<int> lst1{3, 1, 4, 1, 5};
    forward_list<int> lst2{9, 8, 7};
    lst1.swap(lst2);
    cout << "lst1: ";
    for(auto x : lst1) cout << x << " ";
    cout << "\n";
    cout << "lst2: ";
    for(auto x : lst2) cout << x << " ";
    cout << "\n";

「remove(値)」は、指定値の要素を全て削除する。forward_list は list と違い、イテレータの指す先を削除単純に削除出来ず、 指定値の要素を削除するのが面倒なので、このメンバ関数が存在する。

「reverse()」は単方向リスト要素の順序を逆にする。単方向リストのイテレータは std::reverse(first, last) に渡すことが出来ないので、このメンバ関数が存在する。

    forward_list<int> lst{3, 1, 4, 1, 5};
    lst.remove(1);
    for(auto x : lst) cout << x << " ";
    cout << "\n";

要素をソートする需要は大きいが、forward_list のイテレータは std::sort(first, last) に渡すことが出来ないので、「sort()」メンバ関数が存在する。

    forward_list<int> lst{5, 1, 4, 1, 3};
    lst.sort();
    for(auto x : lst) cout << x << " ";
    cout << "\n";

演習問題：

1. std::list<int> lst; に対して、empty() をコールし、結果が正しいことを確認しなさい。 show

    std::list<int> lst;
    cout << lst.empty() << "\n";

2. std::list<int> lst{3, 1, 4}; に対して、empty() をコールし、結果が正しいことを確認しなさい。 show

    std::list<int> lst{3, 1, 4};
    cout << lst.empty() << "\n";

3. std::list<int> lst{3, 1, 4}; に対して、front() をコールし、結果が正しいことを確認しなさい。 show

    std::list<int> lst{3, 1, 4};
    cout << lst.front() << "\n";

4. std::list<int> lst{3, 1, 4}; に対して、clear() をコールし、empty() が正しい値を返すことを確認しなさい。 show

    std::list<int> lst{3, 1, 4};
    lst.clear();
    cout << lst.empty() << "\n";

5. std::list<int> lst{3, 1, 4}, lst2{9, 8}; を宣言し、swap で中身を入れ替えるコードを書きなさい。 show

    std::list<int> lst{3, 1, 4};
    std::list<int> lst2{9, 8};
    lst.swap(lst2);

6. std::list<int> lst{3, 1, 4, 1, 5}; に対して、remove(1) をコールして 1 を削除し、結果を確認しなさい。 show

    std::list<int> lst{3, 1, 4, 1, 5};
    lst.remove(1);
    for(auto itr = lst.begin(); itr != end(); ++itr) {
        std::cout << *itr << "\n";
    }

アルゴリズム

実は C++ には結構便利なアルゴリズムがいくつも用意されている。
参照：http://www.cplusplus.com/reference/algorithm/

ここでは、forward_list に対してよく使うかもしれないアルゴリズムを2つだけ簡単に説明する

• accumulate()
• distance(first, last)

「accumulate(オブジェクト名.begin(), オブジェクト名.end(), init)」は、双方向リストの最初から最後まで、要素を積算（全加算）するものだ。 最後の引数は初期値で、通常は0を指定する。
なお、accumulate を利用するには「#include <numeric>」が必要。

#include <numeric>
.....
    std::forward_list<int> lst{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::cout << std::accumulate(lst.begin(), lst.end(), 0) << "\n";

一部を積算したい場合は、「accumulate(first, last, 0)」の様にイテレータで範囲を指定する。

「distance(first, last)」は、first から last までの距離、すなわち要素数を返す。forward_list には何故か size() メンバ関数が無いので、 要素数を取得したい場合はこの関数を使用しなくてはいけない。

    std::forward_list<int> lst(123);      // 123個の要素をもつ単方向リストを生成
    std::cout << std::distance(lst.begin(), lst.end()) << "\n";       // 123 が表示される

演習問題：

1. 要素数1万個の双方向リストを作成し、各要素を [0, 99] の範囲でランダムに設定し、accumulate() を使い、それらの合計を求め表示しなさい。 show

#include <numeric>
.....
    std::forward_list<int> lst(10000);
    for(auto itr = lst.begin(); itr != lst.end(); ++itr)
        *itr = rand() % 100;
    std::cout << std::accumulate(lst.begin(), lst.end(), 0) << "\n";

2. 上記処理時間を std::vector を使った場合と比較しなさい。 show

#include <numeric>
.....
    std::vector<int> lst(10000);
    for(auto itr = lst.begin(); itr != lst.end(); ++itr)
        *itr = rand() % 100;
    std::cout << std::accumulate(lst.begin(), lst.end(), 0) << "\n";

3. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} の要素数10個の双方向リストを作成し、内容を表示したのち、 reverse() で要素を逆順にして、内容を表示しなさい。 show

    std::forward_list lst{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    for (auto itr = lst.begin(); itr != lst.end(); ++itr) {
        std::cout << *itr << " ";
    }
    std::cout << "\n";
    reverse(lst.begin(), lst.end());
    for (auto itr = lst.begin(); itr != lst.end(); ++itr) {
        std::cout << *itr << " ";
    }
    std::cout << "\n";

参考

---

　

最近更新したページ

人気のページ

関連ページ

• C++ 動的配列クラス std::vector 入門
• C++ 双方向リストクラス std::list 入門
• C++ マップクラス std::map 入門
• C++ 文字列クラス std::string 入門
• C++ 乱数 std::random 入門
• C/C++ 処理時間計測 入門
• C/C++ static 修飾子 入門
• JavaScript 配列入門