[C++] forward_listでクラス型を扱う方法

2025-04-14更新日: 2025-04-14

forward_listは、C++の標準ライブラリに含まれるシングルリンクリストを実装するコンテナです。メモリ効率が良く、特に挿入や削除が頻繁に行われる場合に適しています。

クラス型をforward_listで扱うには、まずクラスのオブジェクトをリストに格納します。クラスはコピー可能である必要がありますが、ムーブセマンティクスを利用することで効率的に操作できます。

また、forward_listは双方向イテレータをサポートしていないため、逆方向の操作には注意が必要です。

目次から探す

C/C++を使った求人

読み込み中…

クラス型をforward_listで扱う準備

forward_listは、シングルリンクリストを実装するためのC++標準ライブラリのコンテナです。

このコンテナを使用してクラス型のオブジェクトを扱うためには、まずクラスの定義とその基本的なメンバ関数を実装する必要があります。

クラスの定義

まず、forward_listで扱うクラスを定義します。

ここでは、Personというクラスを例にします。

このクラスは、名前と年齢を持つシンプルなクラスです。

#include <iostream>
#include <string>
// Personクラスの定義
class Person {
public:
    std::string name; // 名前
    int age;          // 年齢
    // コンストラクタ
    Person(const std::string& name, int age) : name(name), age(age) {}
};

コンストラクタとデストラクタの実装

クラスを使用する際には、コンストラクタとデストラクタの実装が重要です。

コンストラクタはオブジェクトの初期化を行い、デストラクタはオブジェクトが破棄される際にリソースを解放します。

// Personクラスのコンストラクタとデストラクタ
class Person {
public:
    std::string name;
    int age;
    // コンストラクタ
    Person(const std::string& name, int age) : name(name), age(age) {
        std::cout << "Personオブジェクトが作成されました: " << name << std::endl;
    }
    // デストラクタ
    ~Person() {
        std::cout << "Personオブジェクトが破棄されました: " << name << std::endl;
    }
};

コピーコンストラクタとムーブコンストラクタ

forward_listでクラス型を扱う際には、コピーコンストラクタとムーブコンストラクタの実装も考慮する必要があります。

これにより、オブジェクトのコピーやムーブが適切に行われます。

// Personクラスのコピーコンストラクタとムーブコンストラクタ
class Person {
public:
    std::string name;
    int age;
    // コンストラクタ
    Person(const std::string& name, int age) : name(name), age(age) {}
    // コピーコンストラクタ
    Person(const Person& other) : name(other.name), age(other.age) {
        std::cout << "コピーコンストラクタが呼ばれました: " << name << std::endl;
    }
    // ムーブコンストラクタ
    Person(Person&& other) noexcept : name(std::move(other.name)), age(other.age) {
        std::cout << "ムーブコンストラクタが呼ばれました: " << name << std::endl;
    }
};

このように、forward_listでクラス型を扱うためには、クラスの基本的な定義とメンバ関数の実装が必要です。

これにより、forward_listにクラス型のオブジェクトを安全に格納し、操作することができます。

forward_listの基本操作

forward_listは、シングルリンクリストを実装するための軽量なコンテナで、特にメモリ効率が求められる場面で有用です。

ここでは、forward_listの基本的な操作について説明します。

要素の追加

forward_listに要素を追加する方法として、push_frontとemplace_frontがあります。

push_frontの使い方

push_frontは、リストの先頭に要素を追加します。

既存の要素は後ろにシフトされます。

#include <iostream>
#include <forward_list>
// forward_listに要素を追加する例
int main() {
    std::forward_list<int> numbers;
    numbers.push_front(10); // 先頭に10を追加
    numbers.push_front(20); // 先頭に20を追加
    for (int num : numbers) {
        std::cout << num << " "; // 出力: 20 10
    }
    return 0;
}

この例では、push_frontを使ってリストの先頭に要素を追加しています。

emplace_frontの使い方

emplace_frontは、オブジェクトを直接構築してリストの先頭に追加します。

コンストラクタの引数を渡すことができ、オーバーヘッドを減らすことができます。

#include <iostream>
#include <forward_list>
#include <string>
// forward_listにオブジェクトを追加する例
int main() {
    std::forward_list<std::string> words;
    words.emplace_front("World"); // 先頭に"World"を追加
    words.emplace_front("Hello"); // 先頭に"Hello"を追加
    for (const auto& word : words) {
        std::cout << word << " "; // 出力: Hello World
    }
    return 0;
}

この例では、emplace_frontを使って文字列オブジェクトを直接構築しています。

要素の削除

forward_listから要素を削除する方法として、pop_frontとremoveがあります。

pop_frontの使い方

pop_frontは、リストの先頭の要素を削除します。

#include <iostream>
#include <forward_list>
// forward_listから要素を削除する例
int main() {
    std::forward_list<int> numbers = {10, 20, 30};
    numbers.pop_front(); // 先頭の10を削除
    for (int num : numbers) {
        std::cout << num << " "; // 出力: 20 30
    }
    return 0;
}

この例では、pop_frontを使ってリストの先頭の要素を削除しています。

removeの使い方

removeは、指定した値と一致するすべての要素を削除します。

#include <iostream>
#include <forward_list>
// forward_listから特定の要素を削除する例
int main() {
    std::forward_list<int> numbers = {10, 20, 30, 20};
    numbers.remove(20); // すべての20を削除
    for (int num : numbers) {
        std::cout << num << " "; // 出力: 10 30
    }
    return 0;
}

この例では、removeを使ってリストからすべての20を削除しています。

要素のアクセス

forward_listの要素にアクセスする方法として、frontとイテレータの利用があります。

frontの使い方

frontは、リストの先頭の要素を参照します。

#include <iostream>
#include <forward_list>
// forward_listの先頭要素にアクセスする例
int main() {
    std::forward_list<int> numbers = {10, 20, 30};
    std::cout << "先頭の要素: " << numbers.front() << std::endl; // 出力: 先頭の要素: 10
    return 0;
}

この例では、frontを使ってリストの先頭の要素にアクセスしています。

イテレータの利用

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

#include <iostream>
#include <forward_list>
// forward_listの要素にイテレータでアクセスする例
int main() {
    std::forward_list<int> numbers = {10, 20, 30};
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " "; // 出力: 10 20 30
    }
    return 0;
}

この例では、イテレータを使ってリストのすべての要素にアクセスしています。

イテレータは、begin()とend()を使って取得します。

forward_listでのクラス型の操作

forward_listを使用してクラス型のオブジェクトを操作することは、基本的なデータ型を扱う場合と似ていますが、クラス特有の操作が必要になることがあります。

ここでは、クラスオブジェクトの挿入、削除、検索について説明します。

クラスオブジェクトの挿入

クラスオブジェクトをforward_listに挿入するには、push_frontやemplace_frontを使用します。

emplace_frontは、オブジェクトを直接構築するため、効率的です。

#include <iostream>
#include <forward_list>
#include <string>
// Personクラスの定義
class Person {
public:
    std::string name;
    int age;
    Person(const std::string& name, int age) : name(name), age(age) {}
};
// forward_listにクラスオブジェクトを挿入する例
int main() {
    std::forward_list<Person> people;
    people.emplace_front("Alice", 30); // 先頭にAliceを追加
    people.emplace_front("Bob", 25);   // 先頭にBobを追加
    for (const auto& person : people) {
        std::cout << person.name << " (" << person.age << ") "; // 出力: Bob (25) Alice (30)
    }
    return 0;
}

この例では、emplace_frontを使ってPersonオブジェクトを直接構築し、リストに挿入しています。

クラスオブジェクトの削除

クラスオブジェクトをforward_listから削除するには、removeを使用します。

removeは、指定した条件に一致するすべてのオブジェクトを削除します。

#include <iostream>
#include <forward_list>
#include <string>
// Personクラスの定義
class Person {
public:
    std::string name;
    int age;
    Person(const std::string& name, int age) : name(name), age(age) {}
    // 等価演算子のオーバーロード
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};
// forward_listからクラスオブジェクトを削除する例
int main() {
    std::forward_list<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Alice", 30}};
    people.remove({"Alice", 30}); // すべてのAlice (30)を削除
    for (const auto& person : people) {
        std::cout << person.name << " (" << person.age << ") "; // 出力: Bob (25)
    }
    return 0;
}

この例では、removeを使ってPersonオブジェクトを削除しています。

Personクラスに等価演算子をオーバーロードすることで、removeが正しく動作します。

クラスオブジェクトの検索

クラスオブジェクトをforward_list内で検索するには、イテレータを使用してリストを走査し、条件に一致するオブジェクトを見つけます。

#include <iostream>
#include <forward_list>
#include <string>
// Personクラスの定義
class Person {
public:
    std::string name;
    int age;
    Person(const std::string& name, int age) : name(name), age(age) {}
};
// forward_list内でクラスオブジェクトを検索する例
int main() {
    std::forward_list<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
    auto it = std::find_if(people.begin(), people.end(), [](const Person& person) {
        return person.name == "Bob";
    });
    if (it != people.end()) {
        std::cout << "見つかりました: " << it->name << " (" << it->age << ")" << std::endl; // 出力: 見つかりました: Bob (25)
    } else {
        std::cout << "見つかりませんでした" << std::endl;
    }
    return 0;
}

この例では、std::find_ifを使ってPersonオブジェクトを検索しています。

ラムダ式を使用して、検索条件を指定しています。

forward_listの応用例

forward_listは、シンプルなリンクリスト構造を持つため、特定の操作において効率的です。

ここでは、クラス型のオブジェクトをforward_listで扱う際の応用例として、ソート、フィルタリング、マージについて説明します。

クラス型のソート

forward_listでクラス型のオブジェクトをソートするには、sortメソッドを使用します。

クラスに比較演算子を定義することで、ソートの基準を指定できます。

#include <iostream>
#include <forward_list>
#include <string>
// Personクラスの定義
class Person {
public:
    std::string name;
    int age;
    Person(const std::string& name, int age) : name(name), age(age) {}
    // 年齢で比較するための演算子オーバーロード
    bool operator<(const Person& other) const {
        return age < other.age;
    }
};
// forward_listでクラス型をソートする例
int main() {
    std::forward_list<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
    people.sort(); // 年齢でソート
    for (const auto& person : people) {
        std::cout << person.name << " (" << person.age << ") "; // 出力: Bob (25) Alice (30) Charlie (35)
    }
    return 0;
}

この例では、operator<をオーバーロードして年齢でソートしています。

クラス型のフィルタリング

forward_listでクラス型のオブジェクトをフィルタリングするには、remove_ifを使用します。

条件に一致する要素を削除することで、フィルタリングを実現します。

#include <iostream>
#include <forward_list>
#include <string>
// Personクラスの定義
class Person {
public:
    std::string name;
    int age;
    Person(const std::string& name, int age) : name(name), age(age) {}
};
// forward_listでクラス型をフィルタリングする例
int main() {
    std::forward_list<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
    people.remove_if([](const Person& person) {
        return person.age < 30; // 30歳未満の人を削除
    });
    for (const auto& person : people) {
        std::cout << person.name << " (" << person.age << ") "; // 出力: Alice (30) Charlie (35)
    }
    return 0;
}

この例では、remove_ifを使って30歳未満のPersonオブジェクトを削除しています。

クラス型のマージ

forward_listでクラス型のオブジェクトをマージするには、mergeメソッドを使用します。

マージするリストはソートされている必要があります。

#include <iostream>
#include <forward_list>
#include <string>
// Personクラスの定義
class Person {
public:
    std::string name;
    int age;
    Person(const std::string& name, int age) : name(name), age(age) {}
    // 年齢で比較するための演算子オーバーロード
    bool operator<(const Person& other) const {
        return age < other.age;
    }
};
// forward_listでクラス型をマージする例
int main() {
    std::forward_list<Person> group1 = {{"Alice", 30}, {"Charlie", 35}};
    std::forward_list<Person> group2 = {{"Bob", 25}, {"David", 40}};
    group1.sort();
    group2.sort();
    group1.merge(group2); // マージ
    for (const auto& person : group1) {
        std::cout << person.name << " (" << person.age << ") "; // 出力: Bob (25) Alice (30) Charlie (35) David (40)
    }
    return 0;
}

この例では、group1とgroup2を年齢でソートした後、mergeを使ってマージしています。

マージ後、group2は空になります。

forward_listのパフォーマンス

forward_listは、シングルリンクリストとして設計されており、特定の操作において効率的なパフォーマンスを発揮します。

ここでは、forward_listのメモリ使用量の最適化と時間計算量について考察します。

メモリ使用量の最適化

forward_listは、シングルリンクリストとして実装されているため、listと比較してメモリ使用量が少なくなります。

これは、各ノードが次のノードへのポインタのみを持つためです。

メモリ使用量を最適化するためのポイントは以下の通りです。

ノードのオーバーヘッドが少ない: forward_listは、各ノードが次のノードへのポインタのみを持つため、listのように前後のポインタを持つダブルリンクリストよりもメモリ効率が良いです。
小さなデータセットに適している: メモリ使用量を最小限に抑えたい場合や、データセットが小さい場合にforward_listは有効です。
メモリの断片化を防ぐ: forward_listは連続したメモリブロックを必要としないため、メモリの断片化を防ぐことができます。

時間計算量の考察

forward_listの操作における時間計算量は、他のコンテナと比較して異なる特性を持ちます。

以下に、主な操作の時間計算量を示します。

操作	時間計算量	説明
`push_front`	O(1)	先頭に要素を追加する操作は定数時間で行えます。
`pop_front`	O(1)	先頭の要素を削除する操作も定数時間で行えます。
`insert_after`	O(1)	指定した位置の後に要素を挿入する操作は定数時間で行えます。
`remove`	O(n)	指定した値を持つ要素を削除する操作はリスト全体を走査する必要があります。
`sort`	O(n log n)	リストをソートする操作は一般的にn log nの時間がかかります。
`merge`	O(n)	2つのソート済みリストをマージする操作は線形時間で行えます。