C++のSTLには、forward_listという便利なコンテナがあります。
この記事では、forward_listの基本的な使い方から、実際にサンプルコードを交えて詳しく解説していきます。
forward_listとは
forward_listは、C++のSTL(Standard Template Library)に含まれるシンプルなリスト構造のコンテナです。
リスト構造とは、データを順序付けして格納するためのデータ構造であり、forward_listは単方向リストと呼ばれる種類のリストです。
forward_listは、要素を先頭から順番に辿っていくことができますが、逆方向へのアクセスはできません。
そのかわりに、要素の挿入や削除が高速に行えるという特徴があります。
forward_listの基本的な使い方
forward_listの宣言と初期化
forward_listを使用するためには、以下のようにヘッダーファイルをインクルードします。
#include <forward_list>
また、forward_listはテンプレートクラスであるため、以下のように型名を指定して宣言します。
std::forward_list<int> flist;
上記の例ではint型を要素として持つ空のforward_listオブジェクトflistを宣言しています。
また、以下のように初期値を指定して宣言することもできます。
std::forward_list<int> flist = {1, 2, 3};
上記の例では{1, 2, 3}という初期値を持つint型要素からなるforward_listオブジェクトflistを宣言しています。
要素の追加
forward_listに要素を追加する方法はいくつかあります。最も基本的な方法はpush_front()関数を使用する方法です。この関数は先頭に新しい要素を追加します。
std::forward_list<int> flist = {1, 2, 3};
flist.push_front(10);
上記の例では、先頭に要素を追加することによってflistの中身が{10, 1, 2, 3}になります。
また、insert_after()関数を使用することで任意位置に要素を追加することもできます。この関数は挿入したい位置の直前のイテレーターと挿入したい値を引数に取ります。
#include <iostream>
#include <forward_list>
int main() {
std::forward_list<int> flist = { 1, 2, 4 };
auto it = flist.begin();
it++;
flist.insert_after(it, 30);
for (auto it : flist) {
std::cout << it << std::endl;
}
return 0;
}
1
2
30
4上記の例では、1番目(先頭は0番目)の要素(2)の後に30を挿入しています。
要素の削除
erase_after()関数やremove()関数等を使用することで、forward_listから要素を削除することが出来ます。
erase_after()関数は指定した位置(直前)、もしくは指定子た位置から次の位置まで範囲内にある全ての要素を削除します。
remove()関数は指定した値に一致する全ての要素を削除します。
#include <iostream>
#include <forward_list>
int main() {
std::forward_list<int> flist = { 1, 2, 3, 4, 5 };
auto it = flist.begin();
it++;
flist.erase_after(it);
//値が4の要素を削除
flist.remove(4);
for (auto it : flist) {
std::cout << it << std::endl;
}
return 0;
}
1
2
5上記の例ではerase_after()関数でイテレーターitが示す位置の要素2が削除され、その後remove()関数で値が4の要素がすべて削除されます。
要素検索
find()関数やcount()関数等を使用することで、指定した値や条件に一致する要素が存在するかどうか調べることが出来ます。
find()関数は指定した値に一致する最初(先頭)のイテレーターへポインター変換し返します。
見つからなかった場合はend()イテレーターへポインター変換し返します。
count()関数は指定した値に一致する全て(カウント)された回数分だけ整数型変換し返します。
#include <iostream>
#include <forward_list>
int main() {
std::forward_list<int> flist = { 1, 2, 3, 2, 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;
}
int count_num = std::count(flist.begin(), flist.end(), 2);
std::cout << "2の個数： " << count_num << std::endl;
return 0;
}
3 が見つかりました: 3
Count: 2上記例ではfind()関数で3という値が含まれるかどうか調べて、あった場合あ3 が見つかりましたと表示しています。
その後、2という値が何回含まれているかカウントした結果、2個見つかったのでCount: 2と表示しています。
forward_listの高度な使い方
イテレータの利用
forward_listには、begin()とend()メソッドを使用してイテレータを取得することができます。
イテレータを使用することで、forward_list内の要素にアクセスしたり、変更したりすることができます。
#include <iostream>
#include <forward_list>
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;
// イテレータを使用して要素を変更
auto it = flist.begin();
++it;
// 1番目(先頭は0番目)の要素を変更
*it = 10;
// 変更後の要素を表示
for (auto n : flist) {
std::cout << n << " ";
}
}
1 2 3 4 5
1 10 3 4 5要素のソート
forward_listにはsort()メソッドがあります。
このメソッドを使用することで、forward_list内の要素を昇順または降順に並び替えることができます。
#include <iostream>
#include <forward_list>
int main()
{
std::forward_list<int> flist = { 5, 3, 1, 4, 2 };
// 昇順にソート
flist.sort();
// ソート後の要素を表示
for (auto n : flist) {
std::cout << n << " ";
}
std::cout << std::endl;
// 降順にソート
flist.sort(std::greater<int>());
// ソート後の要素を表示
for (auto n : flist) {
std::cout << n << " ";
}
}
1 2 3 4 5
5 4 3 2 1降順にソートしたい場合は、sort関数にstd::greater<型名>()を渡すことで行なえます。
要素の反転
reverse()メソッドを使用することで、forward_list内の要素の順序を逆転させることができます。
#include <iostream>
#include <forward_list>
int main()
{
std::forward_list<int> flist = { 1, 3, 5, 2, 4, 6 };
// 反転前の要素を表示
for (auto n : flist) {
std::cout << n << " ";
}
std::cout << std::endl;
// 要素を反転させる
flist.reverse();
// 反転後の要素を表示
for (auto n : flist) {
std::cout << n << " ";
}
}
1 3 5 2 4 6
6 4 2 5 3 1要素の結合
merge()メソッドは、2つ以上のリスト(または範囲)から新しいリスト(または範囲)を作成します。
#include <iostream>
#include <forward_list>
int main()
{
std::forward_list<int> list1 = {1, 3, 5};
std::forward_list<int> list2 = {2, 4};
list1.merge(list2);
for(auto i: list1)
std::cout<<i<<" ";
}
1 2 3 4 5結合する元のforward_listが両方とも昇順でソートされていた場合、結合時に自動的にソートされるようになっています。
元のforward_listがソート済みであれば、結合後にソートする必要はありません。
forward_listの注意点
forward_listを使用する際には、以下のような注意点があります。
要素の削除によるメモリの解放
forward_listは、要素を削除するときにその要素が占めていたメモリを解放します。
しかし、この処理は他のSTLコンテナと比較して非常に効率的ではありません。
forward_listは、各要素が次の要素へのポインタしか持っていないため、要素を削除する際に前後の要素とのつながりを再構築する必要があります。
その関係で、forward_listで大量の要素を削除する場合は処理時間が長くなるため、要素を削除する場合は注意しましょう。
要素の検索の効率
forward_listは単方向リストであるため、逆方向から辿ることができません。
そのため、逆方向から検索を行う場合やランダムアクセスを行う場合には適していません。
また、検索速度もvectorやdequeなど他のSTLコンテナと比較して遅くなる傾向がありますので、検索処理やランダムアクセスする場合は、forward_listを使うべきではありません。
他のSTLコンテナとの比較
forward_listは他のSTLコンテナと比較して特定用途以外ではパフォーマンス面で劣ることが多くあります。例えばvectorやdequeではランダムアクセスや挿入・削除操作も高速に行えますし、listでは双方向アクセスも可能です。ただし、forward_listは単方向リストであるためメモリ使用量が少なく済みますし、一部操作(先頭へ追加・削除)では高速です。使用目的に応じて適切なSTLコンテナを選択することが重要です。
