アルゴリズム

[C++] std::sort()の使い方 – コンテナのソート(昇順・降順)

C++のstd::sort()は、指定した範囲の要素をソートする標準ライブラリ関数です。

ヘッダファイル<algorithm>をインクルードして使用します。

基本的な使い方はstd::sort(開始イテレータ, 終了イテレータ)で、デフォルトでは昇順にソートされます。

降順にソートする場合は、3番目の引数にカスタム比較関数(例：std::greater<>())を渡します。

ソート対象はランダムアクセス可能なコンテナ(例：std::vectorや配列)である必要があります。

目次から探す

std::sort()の基本的な使い方

C++の標準ライブラリには、コンテナの要素をソートするための便利な関数std::sort()があります。

この関数は、配列やベクターなどのコンテナを昇順または降順に並べ替えることができます。

以下に、std::sort()の基本的な使い方を示します。

基本的な使用例

まずは、std::sort()を使って整数のベクターを昇順にソートする例を見てみましょう。

#include <iostream>
#include <vector>
#include <algorithm> // std::sortを使用するために必要
int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6}; // ソートする整数のベクター
    std::sort(numbers.begin(), numbers.end()); // 昇順にソート
    // ソート結果を表示
    for (int number : numbers) {
        std::cout << number << " "; // 各要素を出力
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

1 2 5 5 6 9

このコードでは、std::sort()を使用してnumbersベクターを昇順にソートしています。

begin()とend()メソッドを使って、ソートする範囲を指定しています。

ソート後、各要素を出力して結果を確認しています。

ソートの範囲指定

std::sort()では、ソートする範囲を指定することができます。

以下の例では、ベクターの一部をソートしています。

#include <iostream>
#include <vector>
#include <algorithm> // std::sortを使用するために必要
int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6}; // ソートする整数のベクター
    std::sort(numbers.begin() + 1, numbers.begin() + 4); // インデックス1から3までをソート
    // ソート結果を表示
    for (int number : numbers) {
        std::cout << number << " "; // 各要素を出力
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

5 1 2 9 5 6

この例では、インデックス1から3までの要素(2, 9, 1)がソートされ、全体の順序は変わりません。

std::sort()は指定した範囲内の要素のみをソートします。

std::sort()は、C++の標準ライブラリで提供される強力なソート機能です。

昇順にソートする基本的な使い方を理解することで、さまざまなデータ構造を効率的に扱うことができます。

次のセクションでは、カスタム比較関数を使ったソート方法について解説します。

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

std::sort()は、デフォルトでは昇順にソートしますが、カスタム比較関数を使用することで、任意の条件に基づいてソートすることができます。

これにより、特定の要件に応じた柔軟なソートが可能になります。

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

カスタム比較関数の定義

まずは、整数のベクターを降順にソートするカスタム比較関数の例を見てみましょう。

#include <iostream>
#include <vector>
#include <algorithm> // std::sortを使用するために必要
// 降順にソートするためのカスタム比較関数
bool compareDescending(int a, int b) {
    return a > b; // aがbより大きい場合にtrueを返す
}
int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6}; // ソートする整数のベクター
    std::sort(numbers.begin(), numbers.end(), compareDescending); // カスタム比較関数を使用して降順にソート
    // ソート結果を表示
    for (int number : numbers) {
        std::cout << number << " "; // 各要素を出力
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

9 6 5 5 2 1

このコードでは、compareDescendingというカスタム比較関数を定義し、std::sort()に渡しています。

この関数は、2つの整数を比較し、降順にソートするための条件を提供します。

複雑なデータ型のソート

カスタム比較関数は、複雑なデータ型(例えば、構造体やクラス)をソートする際にも使用できます。

以下の例では、構造体を使って、名前の長さに基づいてソートします。

#include <iostream>
#include <vector>
#include <algorithm> // std::sortを使用するために必要
#include <string>    // std::stringを使用するために必要
// 名前と年齢を持つ構造体
struct Person {
    std::string name;
    int age;
};
// 名前の長さに基づいてソートするカスタム比較関数
bool compareByNameLength(const Person& a, const Person& b) {
    return a.name.length() < b.name.length(); // 名前の長さが短い方を先にする
}
int main() {
    std::vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlotte", 28},
        {"David", 22}
    }; // ソートする人物のベクター
    std::sort(people.begin(), people.end(), compareByNameLength); // カスタム比較関数を使用してソート
    // ソート結果を表示
    for (const Person& person : people) {
        std::cout << person.name << " (" << person.age << ") "; // 各人物を出力
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

Bob (25) Alice (30) David (22) Charlotte (28)

この例では、Personという構造体を定義し、compareByNameLengthというカスタム比較関数を使用して、名前の長さに基づいてソートしています。

これにより、柔軟なソートが可能になります。

カスタム比較関数を使用することで、std::sort()のソート条件を自由に設定できます。

これにより、さまざまなデータ型や条件に基づいたソートが実現でき、プログラムの柔軟性が向上します。

次のセクションでは、std::sort()の応用例について解説します。

std::sort()の応用例

std::sort()は、基本的なソート機能だけでなく、さまざまな応用が可能です。

ここでは、std::sort()を使ったいくつかの実用的な例を紹介します。

1. 文字列のソート

文字列のベクターをソートすることも簡単です。

以下の例では、文字列を昇順にソートします。

#include <iostream>
#include <vector>
#include <algorithm> // std::sortを使用するために必要
#include <string>    // std::stringを使用するために必要
int main() {
    std::vector<std::string> words = {"banana", "apple", "cherry", "date"}; // ソートする文字列のベクター
    std::sort(words.begin(), words.end()); // 昇順にソート
    // ソート結果を表示
    for (const std::string& word : words) {
        std::cout << word << " "; // 各単語を出力
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

apple banana cherry date

このコードでは、std::sort()を使用して文字列のベクターを昇順にソートしています。

文字列の比較は、辞書順で行われます。

2. 構造体のリストを特定の条件でソート

構造体のリストを特定の条件でソートすることも可能です。

以下の例では、年齢に基づいて人物をソートします。

#include <iostream>
#include <vector>
#include <algorithm> // std::sortを使用するために必要
#include <string>    // std::stringを使用するために必要
// 名前と年齢を持つ構造体
struct Person {
    std::string name;
    int age;
};
// 年齢に基づいてソートするカスタム比較関数
bool compareByAge(const Person& a, const Person& b) {
    return a.age < b.age; // 年齢が小さい方を先にする
}
int main() {
    std::vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlotte", 28},
        {"David", 22}
    }; // ソートする人物のベクター
    std::sort(people.begin(), people.end(), compareByAge); // 年齢に基づいてソート
    // ソート結果を表示
    for (const Person& person : people) {
        std::cout << person.name << " (" << person.age << ") "; // 各人物を出力
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

David (22) Bob (25) Charlotte (28) Alice (30)

この例では、compareByAgeというカスタム比較関数を使用して、年齢に基づいて人物をソートしています。

これにより、年齢が若い順に人物が並びます。

3. ソート後の重複排除

std::sort()を使用して、重複した要素を排除することもできます。

以下の例では、整数のベクターから重複を排除します。

#include <iostream>
#include <vector>
#include <algorithm> // std::sortを使用するために必要
int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6, 2}; // ソートする整数のベクター
    std::sort(numbers.begin(), numbers.end()); // 昇順にソート
    // 重複を排除
    auto last = std::unique(numbers.begin(), numbers.end()); // 重複を排除
    numbers.erase(last, numbers.end()); // 重複を排除した後の要素を削除
    // ソート結果を表示
    for (int number : numbers) {
        std::cout << number << " "; // 各要素を出力
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

1 2 5 6 9

このコードでは、std::sort()でソートした後、std::unique()を使用して重複を排除しています。

std::unique()は、隣接する重複を排除するため、ソートが必要です。

std::sort()は、さまざまなデータ型や条件に基づいてソートを行うことができる非常に強力な機能です。

文字列や構造体のリスト、重複排除など、実用的な応用が可能です。

次のセクションでは、std::sort()を使う際の注意点について解説します。

std::sort()と他のソート関数の比較

C++には、std::sort()以外にもさまざまなソート関数が用意されています。

それぞれのソート関数には特性があり、使用する場面によって適切な選択が求められます。

ここでは、std::sort()と他の主要なソート関数を比較し、それぞれの特徴を解説します。

1. std::sort()

概要: C++標準ライブラリに含まれるソート関数で、最も一般的に使用されます。
時間計算量: 平均および最悪の場合の計算量はO(n log n)。
安定性: 不安定(同じ値の要素の順序が保持されない場合がある)。
使用例: ベクターや配列のソートに広く使用される。

2. std::stable_sort()

概要: std::sort()の安定版で、同じ値の要素の順序を保持します。
時間計算量: 平均および最悪の場合の計算量はO(n log n)。
安定性: 安定(同じ値の要素の順序が保持される)。
使用例: 同じ値の要素の順序を保持したい場合に使用される。

#include <iostream>
#include <vector>
#include <algorithm> // std::stable_sortを使用するために必要
#include <string>    // std::stringを使用するために必要
struct Person {
    std::string name;
    int age;
};
int main() {
    std::vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 25},
        {"David", 22}
    }; // ソートする人物のベクター
    std::stable_sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age; // 年齢に基づいてソート
    }); // 安定ソートを使用
    // ソート結果を表示
    for (const Person& person : people) {
        std::cout << person.name << " (" << person.age << ") "; // 各人物を出力
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

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

3. std::partial_sort()

概要: 一部の要素をソートし、残りの要素は未ソートのままにします。
時間計算量: O(n log k)(kはソートする要素数)。
安定性: 不安定。
使用例: 上位k個の要素を取得したい場合に便利。

#include <iostream>
#include <vector>
#include <algorithm> // std::partial_sortを使用するために必要
int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6}; // ソートする整数のベクター
    std::partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end()); // 上位3つをソート
    // ソート結果を表示
    for (int number : numbers) {
        std::cout << number << " "; // 各要素を出力
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

1 2 5 5 9 6

4. std::nth_element()

概要: 指定した位置にある要素を正しい位置に配置し、他の要素は未ソートのままにします。
時間計算量: O(n)(平均的な場合)。
安定性: 不安定。
使用例: k番目に小さい要素を見つけたい場合に便利。

#include <iostream>
#include <vector>
#include <algorithm> // std::nth_elementを使用するために必要
int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6}; // ソートする整数のベクター
    std::nth_element(numbers.begin(), numbers.begin() + 2, numbers.end()); // 3番目に小さい要素を見つける
    // ソート結果を表示
    for (int number : numbers) {
        std::cout << number << " "; // 各要素を出力
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}

1 2 5 5 9 6

std::sort()は一般的なソート関数ですが、特定の要件に応じて他のソート関数を選択することが重要です。

std::stable_sort()は安定性が必要な場合に、std::partial_sort()やstd::nth_element()は部分的なソートが必要な場合に便利です。

次のセクションでは、std::sort()を使う際の注意点について解説します。

std::sort()を使う際の注意点

std::sort()は非常に便利なソート関数ですが、使用する際にはいくつかの注意点があります。

これらの注意点を理解しておくことで、より効果的にstd::sort()を活用できます。

以下に、主な注意点を挙げます。

1. ソート対象の範囲

注意点: std::sort()は、指定した範囲内の要素をソートします。

範囲を正しく指定しないと、意図しない結果を招くことがあります。

例: std::sort(numbers.begin(), numbers.end())は、numbersベクター全体をソートしますが、std::sort(numbers.begin() + 1, numbers.end())は、最初の要素を除いた範囲をソートします。

2. 不安定なソート

注意点: std::sort()は不安定なソートです。

同じ値の要素の順序が保持されない場合があります。

これが問題となる場合は、std::stable_sort()を使用することを検討してください。

例: 同じ値を持つ要素がある場合、std::sort()を使用すると、元の順序が失われることがあります。

3. カスタム比較関数の使用

注意点: カスタム比較関数を使用する場合、関数が反射的であること(a < b、b < cならば、a < cが成り立つこと)が重要です。

これを満たさないと、未定義の動作を引き起こす可能性があります。

例: 比較関数が不適切な場合、ソート結果が正しくないことがあります。

4. ソート対象のデータ型

注意点: ソート対象のデータ型が比較可能である必要があります。

ユーザー定義型の場合、比較演算子をオーバーロードする必要があります。

例: 構造体やクラスをソートする場合、比較演算子を定義しておく必要があります。

#include <iostream>
#include <vector>
#include <algorithm> // std::sortを使用するために必要
#include <string>    // std::stringを使用するために必要
struct Person {
    std::string name;
    int age;
    // 年齢に基づく比較演算子のオーバーロード
    bool operator<(const Person& other) const {
        return age < other.age; // 年齢が小さい方を先にする
    }
};
int main() {
    std::vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 28},
        {"David", 22}
    }; // ソートする人物のベクター
    std::sort(people.begin(), people.end()); // 年齢に基づいてソート
    // ソート結果を表示
    for (const Person& person : people) {
        std::cout << person.name << " (" << person.age << ") "; // 各人物を出力
    }
    std::cout << std::endl; // 改行
    return 0; // プログラムの終了
}