list

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

C++のstd::listは、双方向リンクリストとして実装されており、sortメンバー関数を使用してソートできます。

デフォルトでは、operator<を用いて要素を昇順にソートしますが、カスタムの比較関数を指定することも可能です。

クラスや構造体を含むstd::listをソートする場合、operator<をオーバーロードするか、比較関数を提供する必要があります。

これにより、特定のメンバ変数に基づいてオブジェクトをソートすることができます。

目次から探す

std::listのソート方法
クラス/構造体を含むstd::listのソート
応用例
まとめ

std::listのソート方法

ソートの必要性と目的

C++のプログラミングにおいて、データを効率的に管理するためには、データの順序を整えることが重要です。

特に、std::listのようなコンテナを使用する場合、データをソートすることで以下のような利点があります。

検索の効率化: ソートされたデータは、二分探索などの効率的な検索アルゴリズムを適用できるため、検索時間を短縮できます。
データの整合性: ソートすることで、データの一貫性や整合性を保つことができ、後続の処理が容易になります。
可読性の向上: ソートされたデータは、視覚的に理解しやすく、デバッグやメンテナンスがしやすくなります。

std::list::sortメソッドの使い方

std::listには、リスト内の要素をソートするためのメソッドsortが用意されています。

このメソッドは、リスト内の要素を昇順に並べ替えます。

デフォルトでは、要素の<演算子を使用して比較を行います。

以下に、std::list::sortメソッドの基本的な使い方を示します。

#include <iostream>
#include <list>
int main() {
    // 整数のリストを作成
    std::list<int> numbers = {5, 2, 9, 1, 3};
    // リストをソート
    numbers.sort();
    // ソートされたリストを出力
    for (int number : numbers) {
        std::cout << number << " ";
    }
    return 0;
}

1 2 3 5 9

この例では、整数のリストを作成し、sortメソッドを使用して昇順に並べ替えています。

ソート後、リストの要素を順に出力しています。

ソートのための比較関数の作成

std::list::sortメソッドは、カスタムの比較関数を受け取ることもできます。

これにより、デフォルトの<演算子ではなく、独自の基準で要素を比較してソートすることが可能です。

以下に、カスタム比較関数を使用したソートの例を示します。

#include <iostream>
#include <list>
// カスタム比較関数
bool customCompare(int a, int b) {
    // 降順にソートするための比較
    return a > b;
}
int main() {
    // 整数のリストを作成
    std::list<int> numbers = {5, 2, 9, 1, 3};
    // カスタム比較関数を使用してリストをソート
    numbers.sort(customCompare);
    // ソートされたリストを出力
    for (int number : numbers) {
        std::cout << number << " ";
    }
    return 0;
}

9 5 3 2 1

この例では、customCompareという関数を定義し、降順にソートするために使用しています。

sortメソッドにこの関数を渡すことで、リストの要素が降順に並べ替えられます。

クラス/構造体を含むstd::listのソート

クラス/構造体の定義

std::listは、クラスや構造体のオブジェクトを格納することができます。

これにより、複雑なデータ構造を扱うことが可能です。

まずは、クラスや構造体を定義してみましょう。

#include <iostream>
#include <list>
#include <string>
// 人を表す構造体
struct Person {
    std::string name; // 名前
    int age;          // 年齢
    // コンストラクタ
    Person(std::string n, int a) : name(n), age(a) {}
};

この例では、Personという構造体を定義しています。

この構造体は、名前と年齢を持つ人を表現します。

比較演算子のオーバーロード

クラスや構造体をソートするためには、比較演算子をオーバーロードする方法があります。

これにより、std::list::sortメソッドがデフォルトで使用する<演算子をカスタマイズできます。

#include <iostream>
#include <list>
#include <string>
// 人を表す構造体
struct Person {
    std::string name;
    int age;
    Person(std::string n, int a) : name(n), age(a) {}
    // 年齢で比較するための演算子オーバーロード
    bool operator<(const Person& other) const {
        return age < other.age;
    }
};

この例では、<演算子をオーバーロードして、Personオブジェクトを年齢で比較するようにしています。

カスタム比較関数の作成

比較演算子をオーバーロードする代わりに、カスタム比較関数を作成することもできます。

これにより、より柔軟なソート基準を設定できます。

#include <iostream>
#include <list>
#include <string>
// 人を表す構造体
struct Person {
    std::string name;
    int age;
    Person(std::string n, int a) : name(n), age(a) {}
};
// 名前で比較するカスタム関数
bool compareByName(const Person& a, const Person& b) {
    return a.name < b.name;
}

この例では、compareByNameという関数を定義し、Personオブジェクトを名前で比較するようにしています。

std::list::sortでのカスタム比較関数の使用

カスタム比較関数を使用して、std::listをソートする方法を示します。

#include <iostream>
#include <list>
#include <string>
// 人を表す構造体
struct Person {
    std::string name;
    int age;
    Person(std::string n, int a) : name(n), age(a) {}
};
// 名前で比較するカスタム関数
bool compareByName(const Person& a, const Person& b) {
    return a.name < b.name;
}
int main() {
    // Personオブジェクトのリストを作成
    std::list<Person> people = {
        Person("Alice", 30),
        Person("Bob", 25),
        Person("Charlie", 35)
    };
    // カスタム比較関数を使用してリストをソート
    people.sort(compareByName);
    // ソートされたリストを出力
    for (const Person& person : people) {
        std::cout << person.name << " (" << person.age << ")" << std::endl;
    }
    return 0;
}

Alice (30)
Bob (25)
Charlie (35)

この例では、compareByName関数を使用して、Personオブジェクトのリストを名前順にソートしています。

std::list::sortメソッドにカスタム関数を渡すことで、任意の基準でソートが可能です。

応用例

複数の基準でのソート

std::listをソートする際に、複数の基準を用いることができます。

例えば、まず年齢でソートし、年齢が同じ場合は名前でソートする、といった方法です。

#include <iostream>
#include <list>
#include <string>
// 人を表す構造体
struct Person {
    std::string name;
    int age;
    Person(std::string n, int a) : name(n), age(a) {}
};
// 年齢で比較し、同じ場合は名前で比較するカスタム関数
bool compareByAgeThenName(const Person& a, const Person& b) {
    if (a.age == b.age) {
        return a.name < b.name;
    }
    return a.age < b.age;
}
int main() {
    // Personオブジェクトのリストを作成
    std::list<Person> people = {
        Person("Alice", 30),
        Person("Bob", 25),
        Person("Charlie", 30),
        Person("David", 25)
    };
    // カスタム比較関数を使用してリストをソート
    people.sort(compareByAgeThenName);
    // ソートされたリストを出力
    for (const Person& person : people) {
        std::cout << person.name << " (" << person.age << ")" << std::endl;
    }
    return 0;
}

Bob (25)
David (25)
Alice (30)
Charlie (30)

この例では、年齢でソートし、年齢が同じ場合は名前でソートしています。

std::listの部分ソート

std::listの一部だけをソートすることは直接的にはできませんが、イテレータを使って部分的にソートすることが可能です。

std::listはランダムアクセスができないため、部分ソートにはstd::vectorなどの他のコンテナを一時的に使用することが一般的です。

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
int main() {
    // 整数のリストを作成
    std::list<int> numbers = {5, 2, 9, 1, 3, 8, 7};
    // 部分ソートする範囲を指定
    auto start = std::next(numbers.begin(), 2);
    auto end = std::next(numbers.begin(), 5);
    // 部分をベクターにコピー
    std::vector<int> sublist(start, end);
    // 部分をソート
    std::sort(sublist.begin(), sublist.end());
    // ソートされた部分をリストに戻す
    std::copy(sublist.begin(), sublist.end(), start);
    // リストを出力
    for (int number : numbers) {
        std::cout << number << " ";
    }
    return 0;
}