forward_list

[C++] forward_listをソートする方法「クラス型/構造体のソートも解説」

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

forward_listは、C++の標準ライブラリで提供される単方向リストです。メモリ効率が良く、挿入や削除が高速ですが、ランダムアクセスができないため、ソートには工夫が必要です。

ソートにはforward_list::sortメンバ関数を使用します。この関数はデフォルトで昇順にソートしますが、カスタム比較関数を渡すことでクラス型や構造体のソートも可能です。

クラス型や構造体をソートする際は、比較演算子をオーバーロードするか、ラムダ式を用いて比較基準を指定します。

目次から探す

forward_listのソート方法
クラス型/構造体のソート
forward_listのソートの応用例
まとめ

forward_listのソート方法

ソートの必要性

forward_listは、シングルリンクリストとして実装されており、メモリ効率が良いデータ構造です。

しかし、データを効率的に検索したり、特定の順序で処理したりするためには、ソートが必要になることがあります。

ソートされたリストは、検索や挿入、削除の操作をより効率的に行うことができ、アルゴリズムのパフォーマンスを向上させることができます。

ソートアルゴリズムの選択

forward_listをソートする際には、以下のようなアルゴリズムを選択することが考えられます。

アルゴリズム名	特徴
マージソート	安定ソートであり、リンクリストに適している
クイックソート	高速だが、リンクリストには不向き
バブルソート	簡単だが、効率が悪い

forward_listには、std::list::sortを利用するのが一般的です。

これは、リンクリストに特化したソートアルゴリズムで、効率的に動作します。

std::sortを使ったソート

std::sortは、ランダムアクセス可能なコンテナに対して使用されるため、forward_listには直接使用できません。

しかし、forward_listの要素を一時的にvectorにコピーしてからstd::sortを使用する方法があります。

#include <iostream>
#include <forward_list>
#include <vector>
#include <algorithm>
int main() {
    // forward_listの定義
    std::forward_list<int> flist = {3, 1, 4, 1, 5, 9, 2};
    // forward_listをvectorにコピー
    std::vector<int> vec(flist.begin(), flist.end());
    // vectorをソート
    std::sort(vec.begin(), vec.end());
    // ソートされたvectorをforward_listに戻す
    flist.assign(vec.begin(), vec.end());
    // 結果を表示
    for (int n : flist) {
        std::cout << n << " ";
    }
    return 0;
}

1 1 2 3 4 5 9

この方法では、forward_listの要素を一時的にvectorにコピーするため、メモリの追加使用が発生しますが、std::sortの高速なソートアルゴリズムを利用できます。

std::list::sortを使ったソート

std::list::sortは、forward_listには直接使用できませんが、forward_listをlistに変換してからソートすることが可能です。

#include <iostream>
#include <forward_list>
#include <list>
int main() {
    // forward_listの定義
    std::forward_list<int> flist = {3, 1, 4, 1, 5, 9, 2};
    // forward_listをlistに変換
    std::list<int> lst(flist.begin(), flist.end());
    // listをソート
    lst.sort();
    // ソートされたlistをforward_listに戻す
    flist.assign(lst.begin(), lst.end());
    // 結果を表示
    for (int n : flist) {
        std::cout << n << " ";
    }
    return 0;
}

1 1 2 3 4 5 9

この方法では、listのsortメソッドを利用することで、forward_listを効率的にソートできます。

listはリンクリストに特化したソートアルゴリズムを持っているため、forward_listのソートに適しています。

クラス型/構造体のソート

クラス型/構造体の定義

forward_listをクラス型や構造体でソートする場合、まずはソート対象となるクラスや構造体を定義する必要があります。

以下は、Personという名前の構造体を定義した例です。

#include <string>
struct Person {
    std::string name;  // 名前
    int age;           // 年齢
    // コンストラクタ
    Person(const std::string& n, int a) : name(n), age(a) {}
};

この構造体は、nameとageという2つのメンバを持ち、コンストラクタで初期化できるようになっています。

比較関数の実装

クラス型や構造体をソートするためには、比較関数を実装する必要があります。

この関数は、2つのオブジェクトを比較し、ソートの基準を提供します。

以下は、ageを基準にソートするための比較関数の例です。

bool compareByAge(const Person& a, const Person& b) {
    return a.age < b.age;  // 年齢を基準に昇順でソート
}

この関数は、aの年齢がbの年齢より小さい場合にtrueを返します。

これにより、std::sortやlist::sortで使用することができます。

ソートの実装例

forward_listにクラス型や構造体を格納し、ソートする実装例を示します。

ここでは、listを使用してソートを行います。

#include <iostream>
#include <forward_list>
#include <list>
#include <string>
// Person構造体の定義
struct Person {
    std::string name;
    int age;
    Person(const std::string& n, int a) : name(n), age(a) {}
};
// 比較関数の定義
bool compareByAge(const Person& a, const Person& b) {
    return a.age < b.age;
}
int main() {
    // forward_listにPersonオブジェクトを追加
    std::forward_list<Person> flist = {
        Person("Alice", 30),
        Person("Bob", 25),
        Person("Charlie", 35)
    };
    // forward_listをlistに変換
    std::list<Person> lst(flist.begin(), flist.end());
    // listをソート
    lst.sort(compareByAge);
    // ソートされたlistをforward_listに戻す
    flist.assign(lst.begin(), lst.end());
    // 結果を表示
    for (const auto& person : flist) {
        std::cout << person.name << ": " << person.age << "歳" << std::endl;
    }
    return 0;
}

Bob: 25歳
Alice: 30歳
Charlie: 35歳

この例では、Person構造体のageを基準にソートを行っています。

listのsortメソッドに比較関数compareByAgeを渡すことで、ageに基づいたソートが実現されています。

ソート後、forward_listに戻して結果を表示しています。

forward_listのソートの応用例

カスタム比較関数を使ったソート

forward_listのソートでは、カスタム比較関数を使用することで、特定の条件に基づいたソートを行うことができます。

以下は、Person構造体のnameを基準にソートするカスタム比較関数を使用した例です。

#include <iostream>
#include <forward_list>
#include <list>
#include <string>
// Person構造体の定義
struct Person {
    std::string name;
    int age;
    Person(const std::string& n, int a) : name(n), age(a) {}
};
// 名前を基準にソートする比較関数
bool compareByName(const Person& a, const Person& b) {
    return a.name < b.name;  // 名前を基準に昇順でソート
}
int main() {
    // forward_listにPersonオブジェクトを追加
    std::forward_list<Person> flist = {
        Person("Alice", 30),
        Person("Bob", 25),
        Person("Charlie", 35)
    };
    // forward_listをlistに変換
    std::list<Person> lst(flist.begin(), flist.end());
    // listを名前でソート
    lst.sort(compareByName);
    // ソートされたlistをforward_listに戻す
    flist.assign(lst.begin(), lst.end());
    // 結果を表示
    for (const auto& person : flist) {
        std::cout << person.name << ": " << person.age << "歳" << std::endl;
    }
    return 0;
}

Alice: 30歳
Bob: 25歳
Charlie: 35歳

この例では、nameを基準に昇順でソートしています。

カスタム比較関数を使用することで、任意の基準でソートが可能です。

複数条件でのソート

複数の条件を組み合わせてソートすることも可能です。

以下は、ageを優先し、同じ年齢の場合はnameでソートする例です。

#include <iostream>
#include <forward_list>
#include <list>
#include <string>
// Person構造体の定義
struct Person {
    std::string name;
    int age;
    Person(const std::string& n, int a) : name(n), age(a) {}
};
// 複数条件でソートする比較関数
bool compareByAgeAndName(const Person& a, const Person& b) {
    if (a.age == b.age) {
        return a.name < b.name;  // 年齢が同じ場合は名前でソート
    }
    return a.age < b.age;  // 年齢を基準に昇順でソート
}
int main() {
    // forward_listにPersonオブジェクトを追加
    std::forward_list<Person> flist = {
        Person("Alice", 30),
        Person("Bob", 25),
        Person("Charlie", 30)
    };
    // forward_listをlistに変換
    std::list<Person> lst(flist.begin(), flist.end());
    // listを複数条件でソート
    lst.sort(compareByAgeAndName);
    // ソートされたlistをforward_listに戻す
    flist.assign(lst.begin(), lst.end());
    // 結果を表示
    for (const auto& person : flist) {
        std::cout << person.name << ": " << person.age << "歳" << std::endl;
    }
    return 0;
}

Bob: 25歳
Alice: 30歳
Charlie: 30歳

この例では、まずageでソートし、同じ年齢の場合はnameでソートしています。

ソート後のforward_listの操作

ソート後のforward_listは、様々な操作を行うことができます。

例えば、特定の条件に合致する要素を削除したり、要素を追加したりすることが可能です。

#include <iostream>
#include <forward_list>
#include <string>
// Person構造体の定義
struct Person {
    std::string name;
    int age;
    Person(const std::string& n, int a) : name(n), age(a) {}
};
int main() {
    // forward_listにPersonオブジェクトを追加
    std::forward_list<Person> flist = {
        Person("Alice", 30),
        Person("Bob", 25),
        Person("Charlie", 35)
    };
    // 年齢が30以上の要素を削除
    flist.remove_if([](const Person& p) { return p.age >= 30; });
    // 結果を表示
    for (const auto& person : flist) {
        std::cout << person.name << ": " << person.age << "歳" << std::endl;
    }
    return 0;
}