C++のpartition_pointとは？使い方とサンプルコードをわかりやすく解説

本記事では、C++標準ライブラリの std::partition_point について、サンプルコードを交えながらわかりやすく解説します。

partition_pointとは

partition_point は、すでに分割（パーティション）済みの範囲に対して使用できるアルゴリズムの一つです。この関数は、範囲内で「述語（条件）が false となる最初の要素」を指すイテレータを返します。つまり、述語が true となる要素群と false となる要素群の境界位置を特定することができます。

サンプルプログラム

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

bool IsOdd(int i) { return (i % 2) == 1; }

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

    // 奇数が前半に来るように安定分割
    std::stable_partition(data.begin(), data.end(), IsOdd);

    // 分割点（奇数と偶数の境界）を取得
    auto it = std::partition_point(data.begin(), data.end(), IsOdd);

    odd.assign(data.begin(), it);
    even.assign(it, data.end());

    std::cout << "odd:";
    for (int& x : odd)
        std::cout << ' ' << x;
    std::cout << '\n';

    std::cout << "even:";
    for (int& x : even)
        std::cout << ' ' << x;
    std::cout << '\n';

    return 0;
}

実行結果

odd: 1 3 5 7 9
even: 2 4 6 8 10

コードの解説

まず、std::stable_partition を使って、IsOdd が true を返す奇数を前半に、偶数を後半に配置しています。これにより、範囲全体が「奇数のグループ」と「偶数のグループ」に分割された状態になります。

次に std::partition_point を呼び出すことで、偶数が始まる位置（＝述語が false になる最初の要素）を指すイテレータを取得します。このイテレータを境界として、odd には前半部分を、even には後半部分をそれぞれコピーし、結果を出力しています。

利用時の注意点

partition_point は二分探索と同様の仕組みで O(log n) の計算量で動作するため、対象の範囲が正しく分割されていることが前提条件となります。分割されていない範囲に対して呼び出した場合の動作は未定義となるため、必ず std::partition や std::stable_partition などで事前に分割しておきましょう。