アルゴリズム

[C++] partition()の使い方 – コンテナの範囲を区分化する

C++のstd::partitionは、指定した条件を満たす要素をコンテナの先頭に集め、それ以外を後方に移動させるアルゴリズムです。

戻り値は条件を満たす要素の範囲の終端を指すイテレータです。

使用するには、範囲(イテレータ)と条件を指定します。

元の順序は保証されませんが、効率的に区分化できます。

条件を満たす要素と満たさない要素を分ける際に便利です。

目次から探す

partition()とは何か

C++の標準ライブラリに含まれるpartition()は、コンテナ内の要素を特定の条件に基づいて2つのグループに分けるためのアルゴリズムです。

この関数は、指定された条件を満たす要素と満たさない要素を分けることができます。

partition()は、イテレータを使用してコンテナの範囲を操作し、効率的に要素を再配置します。

特徴

条件に基づく分割: ユーザーが定義した条件に従って要素を分けることができます。
安定性: 元の順序を保持するわけではありませんが、条件を満たす要素は前方に、満たさない要素は後方に配置されます。
効率性: 一度の走査で分割を行うため、時間計算量はO(n)です。

以下は、partition()を使用して整数のベクターを偶数と奇数に分けるサンプルコードです。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // 偶数を前に、奇数を後ろに分ける条件
    auto it = std::partition(numbers.begin(), numbers.end(), [](int n) {
        return n % 2 == 0; // 偶数の場合はtrueを返す
    });
    
    // 分割後の結果を表示
    std::cout << "偶数と奇数に分けた結果: ";
    for (auto num : numbers) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl;
    return 0;
}

偶数と奇数に分けた結果: 2 4 6 8 10 1 3 5 7 9

このコードでは、partition()を使用して、整数のベクターを偶数と奇数に分けています。

条件として、偶数であるかどうかを判定するラムダ式を使用しています。

分割後、偶数が前に、奇数が後ろに配置されていることが確認できます。

partition()の使い方

partition()は、C++の標準ライブラリに含まれるアルゴリズムで、特定の条件に基づいてコンテナの要素を2つのグループに分けるために使用されます。

以下に、partition()の基本的な使い方を説明します。

基本構文

partition()の基本的な構文は以下の通りです。

std::partition(イテレータ範囲の開始, イテレータ範囲の終了, 条件を満たすかどうかを判定する関数またはラムダ式);

イテレータ範囲の開始: 分割を行う範囲の最初の要素を指すイテレータ。
イテレータ範囲の終了: 分割を行う範囲の最後の要素を指すイテレータ。
条件を満たすかどうかを判定する関数またはラムダ式: 各要素に対して適用される条件を定義します。

条件が真の場合、その要素は前方に移動します。

以下は、partition()を使用して文字列のベクターを長さが5文字以上のものとそれ未満のものに分けるサンプルコードです。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main() {
    std::vector<std::string> words = {"apple", "banana", "kiwi",
                                      "grape", "fig",    "orange"};

    // 長さが5文字以上の単語を前に、未満の単語を後ろに分ける条件
    auto it =
        std::partition(words.begin(), words.end(), [](const std::string& word) {
            return word.length() >= 5; // 長さが5以上の場合はtrueを返す
        });

    // 分割後の結果を表示
    std::cout << "長さで分けた結果: ";
    for (auto word : words) {
        std::cout << word << " "; // 各単語を表示
    }
    std::cout << std::endl;
    return 0;
}

長さで分けた結果: apple banana orange grape fig kiwi

このコードでは、partition()を使用して、文字列のベクターを長さが5文字以上の単語とそれ未満の単語に分けています。

条件として、文字列の長さを判定するラムダ式を使用しています。

分割後、長さが4文字以上の単語が前に、未満の単語が後ろに配置されていることが確認できます。

partition()の具体例

partition()を使用する具体的な例をいくつか紹介します。

これにより、さまざまなデータ型や条件に基づいて要素を分ける方法を理解できます。

例1: 整数のベクターを正の数と負の数に分ける

以下のコードでは、整数のベクターを正の数と負の数に分ける方法を示します。

#include <algorithm>
#include <iostream>
#include <vector>
int main() {
    std::vector<int> numbers = {-5, 3, -1, 7, 0, -2, 4};

    // 正の数を前に、負の数を後ろに分ける条件
    auto it = std::partition(numbers.begin(), numbers.end(), [](int n) {
        return n >= 0; // 正の数か0の場合はtrueを返す
    });

    // 分割後の結果を表示
    std::cout << "正の数と負の数に分けた結果: ";
    for (auto num : numbers) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl;
    return 0;
}

正の数と負の数に分けた結果: 4 3 0 7 -1 -2 -5

この例では、partition()を使用して、正の数が前に、負の数が後ろに配置されています。

例2: 学生の成績を合格と不合格に分ける

次に、学生の成績を合格(60点以上)と不合格に分ける例を示します。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> scores = {55, 78, 90, 45, 62, 33, 88};
    
    // 合格(60点以上)を前に、不合格を後ろに分ける条件
    auto it = std::partition(scores.begin(), scores.end(), [](int score) {
        return score >= 60; // 60点以上の場合はtrueを返す
    });
    
    // 分割後の結果を表示
    std::cout << "合格と不合格に分けた結果: ";
    for (auto score : scores) {
        std::cout << score << " "; // 各成績を表示
    }
    std::cout << std::endl;
    return 0;
}

合格と不合格に分けた結果: 78 90 62 88 55 45 33

この例では、partition()を使用して、合格の成績が前に、不合格の成績が後ろに配置されています。

例3: 文字列のベクターを特定の文字で始まるものとそうでないものに分ける

最後に、文字列のベクターを特定の文字(例えば、’a’)で始まるものとそうでないものに分ける例を示します。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
int main() {
    std::vector<std::string> fruits = {"apple", "banana", "avocado", "grape", "apricot", "kiwi"};
    
    // 'a'で始まる果物を前に、そうでない果物を後ろに分ける条件
    auto it = std::partition(fruits.begin(), fruits.end(), [](const std::string& fruit) {
        return fruit[0] == 'a'; // 'a'で始まる場合はtrueを返す
    });
    
    // 分割後の結果を表示
    std::cout << "'a'で始まる果物とそうでない果物に分けた結果: ";
    for (auto fruit : fruits) {
        std::cout << fruit << " "; // 各果物を表示
    }
    std::cout << std::endl;
    return 0;
}

'a'で始まる果物とそうでない果物に分けた結果: apple avocado apricot banana grape kiwi

この例では、partition()を使用して、’a’で始まる果物が前に、そうでない果物が後ろに配置されています。

これらの具体例を通じて、partition()の使い方を理解し、さまざまな条件で要素を分ける方法を学ぶことができます。

partition()の応用

partition()は、要素を特定の条件に基づいて分けるだけでなく、さまざまな場面で応用することができます。

以下に、partition()の応用例をいくつか紹介します。

1. フィルタリングと後処理

partition()を使用してデータをフィルタリングし、その後の処理を行うことができます。

例えば、特定の条件を満たす要素だけを抽出し、その後に別の処理を行うことができます。

#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric> // accumulateを使用するために必要

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // 偶数を前に、奇数を後ろに分ける
    auto it = std::partition(numbers.begin(), numbers.end(), [](int n) {
        return n % 2 == 0; // 偶数の場合はtrueを返す
    });

    // 偶数の合計を計算
    int evenSum =
        std::accumulate(numbers.begin(), it, 0); // 偶数の範囲で合計を計算

    std::cout << "偶数の合計: " << evenSum << std::endl;
    return 0;
}

偶数の合計: 30

この例では、partition()を使用して偶数と奇数を分けた後、偶数の合計を計算しています。

2. クイックソートの実装

partition()は、クイックソートアルゴリズムの一部としても利用されます。

クイックソートでは、基準となる要素を選び、その要素より小さいものと大きいものに分けるためにpartition()を使用します。

#include <iostream>
#include <vector>

int partition(std::vector<int>& arr, int left, int right) {
    int pivot = arr[right]; // 基準となる要素
    int i = left - 1; // iは小さい要素の最後のインデックス

    for (int j = left; j < right; ++j) {
        if (arr[j] < pivot) {
            ++i;
            std::swap(arr[i], arr[j]); // 小さい要素を前に移動
        }
    }
    std::swap(arr[i + 1], arr[right]); // 基準を正しい位置に移動
    return i + 1; // 基準の位置を返す
}

void quickSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int pivotIndex = partition(arr, left, right); // パーティションを作成し、基準の位置を取得

        quickSort(arr, left, pivotIndex - 1); // 基準の左側をソート
        quickSort(arr, pivotIndex + 1, right); // 基準の右側をソート
    }
}

int main() {
    std::vector<int> numbers = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};

    quickSort(numbers, 0, numbers.size() - 1);

    // ソート後の結果を表示
    std::cout << "ソート結果: ";
    for (auto num : numbers) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl;
    return 0;
}

ソート結果: 2 3 5 6 7 9 10 11 12 14

この例では、partition()を使用してクイックソートを実装しています。

基準となる要素を選び、その要素より小さいものと大きいものに分けることで、再帰的にソートを行っています。

3. 複数条件での分割

partition()を使用して、複数の条件に基づいて要素を分けることも可能です。

例えば、数値のベクターを正の偶数、正の奇数、負の数に分けることができます。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> numbers = {-5, 3, -1, 7, 0, -2, 4, 6, -8, 9};
    
    // 正の偶数を前に、正の奇数をその次に、負の数を後ろに分ける
    auto itEven = std::partition(numbers.begin(), numbers.end(), [](int n) {
        return n > 0 && n % 2 == 0; // 正の偶数の場合はtrueを返す
    });
    
    auto itOdd = std::partition(itEven, numbers.end(), [](int n) {
        return n > 0 && n % 2 != 0; // 正の奇数の場合はtrueを返す
    });
    
    // 分割後の結果を表示
    std::cout << "分割結果: ";
    for (auto num : numbers) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl;
    return 0;
}

分割結果: 6 4 9 7 3 -2 0 -5 -8 -1

この例では、partition()を2回使用して、正の偶数、正の奇数、負の数に分けています。

最初のpartition()で正の偶数を前に、次のpartition()で正の奇数をその次に配置しています。

これらの応用例を通じて、partition()の柔軟性と強力さを理解し、さまざまな場面での利用方法を学ぶことができます。

partition()の注意点

partition()を使用する際には、いくつかの注意点があります。

これらを理解しておくことで、より効果的にpartition()を活用できるようになります。

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

1. 元の順序が保証されない

partition()は、要素を条件に基づいて分ける際に、元の順序を保持するわけではありません。

条件を満たす要素が前方に、満たさない要素が後方に配置されますが、同じ条件を満たす要素の順序は保証されません。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6};
    
    // 偶数を前に、奇数を後ろに分ける
    auto it = std::partition(numbers.begin(), numbers.end(), [](int n) {
        return n % 2 == 0; // 偶数の場合はtrueを返す
    });
    
    // 分割後の結果を表示
    std::cout << "分割結果: ";
    for (auto num : numbers) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl;
    return 0;
}

分割結果: 6 2 4 3 5 1

このように、偶数の順序は元の順序を保持していないことがわかります。

2. 条件が常に真または偽である必要がある

partition()に渡す条件は、各要素に対して真または偽を返す必要があります。

条件が不適切な場合、意図しない結果を招く可能性があります。

例えば、条件が常に真を返す場合、すべての要素が前方に配置され、分割が行われません。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    
    // 常にtrueを返す条件
    auto it = std::partition(numbers.begin(), numbers.end(), [](int n) {
        return true; // 常にtrueを返す
    });
    
    // 分割後の結果を表示
    std::cout << "分割結果: ";
    for (auto num : numbers) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl;
    return 0;
}

分割結果: 1 2 3 4 5

この場合、すべての要素が前方に配置され、分割が行われていないことがわかります。

3. コンテナの範囲を正しく指定する

partition()を使用する際には、イテレータの範囲を正しく指定することが重要です。

範囲が不適切な場合、未定義の動作を引き起こす可能性があります。

特に、範囲の開始イテレータが終了イテレータよりも後にある場合や、範囲がコンテナの外に出ている場合は注意が必要です。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    
    // 不適切な範囲を指定
    auto it = std::partition(numbers.begin() + 3, numbers.begin() + 1, [](int n) {
        return n % 2 == 0; // 偶数の場合はtrueを返す
    });
    
    // 分割後の結果を表示
    std::cout << "分割結果: ";
    for (auto num : numbers) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl;
    return 0;
}

このコードは未定義の動作を引き起こす可能性があり、実行時エラーが発生することがあります。

範囲を正しく指定することが重要です。

4. コンテナの要素数が0の場合

partition()を使用する際、コンテナの要素数が0の場合でも問題なく動作しますが、分割結果は空のままとなります。

特に、条件を満たす要素がない場合や、すべての要素が条件を満たさない場合も同様です。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> numbers; // 空のベクター
    
    // 空のベクターに対してpartitionを実行
    auto it = std::partition(numbers.begin(), numbers.end(), [](int n) {
        return n % 2 == 0; // 偶数の場合はtrueを返す
    });
    
    // 分割後の結果を表示
    std::cout << "分割結果: ";
    for (auto num : numbers) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl;
    return 0;
}

分割結果:

このように、空のコンテナに対してpartition()を実行しても、特にエラーは発生せず、結果は空のままとなります。

これらの注意点を理解しておくことで、partition()をより効果的に活用し、意図した通りの結果を得ることができるようになります。

partition()と関連するアルゴリズム

partition()は、C++の標準ライブラリにおける重要なアルゴリズムの一つであり、他のアルゴリズムと組み合わせて使用されることが多いです。

以下に、partition()と関連するいくつかのアルゴリズムを紹介します。

1. sort()

sort()は、コンテナ内の要素を昇順または降順に並べ替えるアルゴリズムです。

partition()を使用して要素を分けた後、sort()を適用することで、特定の条件に基づいて分けた要素をさらに整列させることができます。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> numbers = {5, 3, 8, 1, 4, 7, 2, 6};
    
    // 偶数を前に、奇数を後ろに分ける
    auto it = std::partition(numbers.begin(), numbers.end(), [](int n) {
        return n % 2 == 0; // 偶数の場合はtrueを返す
    });
    
    // 偶数部分をソート
    std::sort(numbers.begin(), it); // 偶数を昇順にソート
    
    // 奇数部分をソート
    std::sort(it, numbers.end()); // 奇数を昇順にソート
    
    // 結果を表示
    std::cout << "分割後のソート結果: ";
    for (auto num : numbers) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl;
    return 0;
}

分割後のソート結果: 2 4 6 8 1 3 5 7

この例では、partition()を使用して偶数と奇数を分けた後、それぞれをsort()で整列させています。

2. stable_partition()

stable_partition()は、partition()と似ていますが、元の順序を保持する点が異なります。

条件を満たす要素の順序を保持しながら分割を行いたい場合に使用します。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> numbers = {5, 3, 8, 1, 4, 7, 2, 6};
    
    // 偶数を前に、奇数を後ろに分ける(順序を保持)
    auto it = std::stable_partition(numbers.begin(), numbers.end(), [](int n) {
        return n % 2 == 0; // 偶数の場合はtrueを返す
    });
    
    // 結果を表示
    std::cout << "stable_partitionの結果: ";
    for (auto num : numbers) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl;
    return 0;
}

stable_partitionの結果: 8 4 2 6 5 3 1 7

この例では、stable_partition()を使用して偶数と奇数を分けていますが、元の順序が保持されています。

3. remove_if()

remove_if()は、指定した条件を満たす要素を削除するためのアルゴリズムです。

partition()と似たような機能を持っていますが、remove_if()は要素を削除するのではなく、条件を満たす要素を後ろに移動させます。

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {5, 3, 8, 1, 4, 7, 2, 6};

    // 偶数を削除する
    auto it = std::remove_if(numbers.begin(), numbers.end(), [](int n) {
        return n % 2 == 0; // 偶数の場合はtrueを返す
    });

    // 実際に削除する
    numbers.erase(it, numbers.end());

    // 結果を表示
    std::cout << "remove_ifの結果: ";
    for (auto num : numbers) {
        std::cout << num << " "; // 各要素を表示
    }
    std::cout << std::endl;
    return 0;
}

remove_ifの結果: 5 3 1 7

この例では、remove_if()を使用して偶数を削除しています。

条件を満たす要素は後ろに移動し、結果として奇数だけが残ります。

4. unique()

unique()は、連続する重複要素を削除するアルゴリズムです。

partition()を使用して条件に基づいて要素を分けた後、unique()を適用することで、重複を排除することができます。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> numbers = {1, 2, 2, 3, 4, 4, 5, 5, 6};
    
    // 重複を排除
    auto it = std::unique(numbers.begin(), numbers.end());
    
    // 結果を表示
    std::cout << "uniqueの結果: ";
    for (auto num = numbers.begin(); num != it; ++num) {
        std::cout << *num << " "; // 各要素を表示
    }
    std::cout << std::endl;
    return 0;
}