C++11 划分算法原理解析：is_partitioned、partition_copy与partition_point

一、std::is_partitioned：检查序列分区状态

功能概述

std::is_partitioned是C++11引入的非修改序列算法，用于判断给定范围内的元素是否已按指定谓词完成分区。具体而言，若所有满足谓词p的元素都出现在不满足p的元素之前（或范围为空），则返回true，否则返回false。

参数与返回值

返回值：bool类型，范围为空或已分区时返回true，否则false。

实现原理

核心逻辑分为两步：

1. 第一阶段：遍历范围，找到第一个不满足谓词p的元素，记为分界点；
2. 第二阶段：从分界点继续遍历，若后续出现满足p的元素，则说明未分区，返回false；若遍历结束未发现此类元素，则返回true。

简化源码（忽略迭代器类别优化和C++20 constexpr）：

template <class InputIt, class UnaryPredicate>
bool is_partitioned(InputIt first, InputIt last, UnaryPredicate p) {
    // 第一阶段：找到第一个不满足p的元素
    for (; first != last; ++first) {
        if (!p(*first)) break;
    }
    // 第二阶段：检查后续是否存在满足p的元素
    for (; first != last; ++first) {
        if (p(*first)) return false; // 存在则未分区
    }
    return true; // 空范围或已分区
}

使用示例

判断序列是否按“偶数在前”分区：

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

int main() {
    std::vector<int> v1 = {2, 4, 6, 1, 3, 5}; // 已分区（偶数在前）
    std::vector<int> v2 = {2, 1, 4, 3, 6, 5}; // 未分区（偶数与奇数交替）
    
    auto is_even = [](int x) { return x % 2 == 0; };
    
    std::cout << std::boolalpha;
    std::cout << "v1 is partitioned: " << std::is_partitioned(v1.begin(), v1.end(), is_even) << "\n"; // true
    std::cout << "v2 is partitioned: " << std::is_partitioned(v2.begin(), v2.end(), is_even) << "\n"; // false
    return 0;
}

复杂度分析

• 时间复杂度：最多应用std::distance(first, last)次谓词p，即O(n)（n为范围长度）。
• 空间复杂度：O(1)，仅使用常数额外空间。

二、std::partition_copy：分区复制元素

功能概述

std::partition_copy是C++11引入的修改序列算法，用于将输入范围中的元素按谓词p分区并复制到两个不同的输出范围：满足p的元素复制到第一个输出范围，不满足的复制到第二个输出范围。原始序列保持不变。

参数与返回值

返回值：std::pair<OutputIt1, OutputIt2>，其中第一个迭代器指向d_first_true范围的结尾，第二个指向d_first_false范围的结尾。

实现原理

遍历输入范围，对每个元素应用谓词p：

• 若满足p，则复制到d_first_true并递增该迭代器；
• 否则复制到d_first_false并递增该迭代器；
• 遍历结束后，返回两个输出迭代器的最终位置。

关键约束：输入范围与任一输出范围重叠时，行为未定义。

简化源码：

template <class InputIt, class OutputIt1, class OutputIt2, class UnaryPredicate>
std::pair<OutputIt1, OutputIt2> partition_copy(
    InputIt first, InputIt last,
    OutputIt1 d_first_true, OutputIt2 d_first_false,
    UnaryPredicate p
) {
    while (first != last) {
        if (p(*first)) {
            *d_first_true = *first; // 复制满足p的元素
            ++d_first_true;
        } else {
            *d_first_false = *first; // 复制不满足p的元素
            ++d_first_false;
        }
        ++first;
    }
    return {d_first_true, d_first_false}; // 返回两个输出范围的结尾
}

使用示例

将序列中的偶数和奇数分别复制到两个向量：

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

int main() {
    std::vector<int> src = {1, 2, 3, 4, 5, 6};
    std::vector<int> evens, odds;
    
    // 预留空间（可选，提升效率）
    evens.reserve(src.size());
    odds.reserve(src.size());
    
    auto is_even = [](int x) { return x % 2 == 0; };
    
    // 分区复制：偶数到evens，奇数到odds
    auto [even_end, odd_end] = std::partition_copy(
        src.begin(), src.end(),
        std::back_inserter(evens), std::back_inserter(odds),
        is_even
    );
    
    std::cout << "Evens: ";
    for (int x : evens) std::cout << x << " "; // 2 4 6
    std::cout << "\nOdds: ";
    for (int x : odds) std::cout << x << " ";  // 1 3 5
    return 0;
}

复杂度分析

• 时间复杂度：准确应用std::distance(first, last)次谓词p，复制操作次数与范围长度相同，总复杂度O(n)。
• 空间复杂度：O(1)（不包含输出范围的存储空间）。

三、std::partition_point：定位分区点

功能概述

std::partition_point是C++11引入的查找算法，用于在已分区的范围中定位“分区点”——即第一个不满足谓词p的元素。若所有元素都满足p，则返回last。

参数与返回值

返回值：指向分区点的迭代器（第一个不满足p的元素），或last（若所有元素满足p）。

实现原理

核心思想：利用已分区序列的特性（前半部分满足p，后半部分不满足），通过二分查找高效定位分区点，而非线性遍历。

• 对于随机访问迭代器（如vector::iterator），二分查找可将谓词应用次数降至O(log n)；
• 对于非随机访问迭代器（如list::iterator），仍需线性递增迭代器，总复杂度为O(n)。

简化源码（基于二分查找，适用于随机访问迭代器）：

template <class ForwardIt, class UnaryPredicate>
ForwardIt partition_point(ForwardIt first, ForwardIt last, UnaryPredicate p) {
    // 计算范围长度
    auto dist = std::distance(first, last);
    while (dist > 0) {
        auto half = dist / 2;
        auto mid = first;
        std::advance(mid, half); // 移动到中间位置
        
        if (p(*mid)) {
            // 中间元素满足p，分区点在右侧
            first = ++mid;
            dist -= half + 1;
        } else {
            // 中间元素不满足p，分区点在左侧（含mid）
            last = mid;
            dist = half;
        }
    }
    return first; // 此时first即为分区点
}

使用示例

在已分区序列中查找“偶数与奇数的分界点”：

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

int main() {
    std::vector<int> v = {2, 4, 6, 1, 3, 5}; // 已分区（偶数在前，奇数在后）
    auto is_even = [](int x) { return x % 2 == 0; };
    
    // 验证序列已分区
    if (!std::is_partitioned(v.begin(), v.end(), is_even)) {
        std::cout << "序列未分区，无法使用partition_point！\n";
        return 1;
    }
    
    // 查找分区点（第一个奇数）
    auto part_point = std::partition_point(v.begin(), v.end(), is_even);
    
    std::cout << "分区点位置：" << std::distance(v.begin(), part_point) << "\n"; // 3（索引从0开始）
    std::cout << "分区点元素：" << *part_point << "\n"; // 1
    return 0;
}

复杂度分析

• 谓词应用次数：O(log n)（n为范围长度），通过二分查找实现；
• 迭代器移动次数：对于随机访问迭代器为O(log n)，对于非随机访问迭代器为O(n)。

四、总结与对比

使用场景建议：

• 需验证分区状态时使用is_partitioned；
• 需保留原始序列并分区元素时使用partition_copy；
• 需快速定位分区边界时使用partition_point（前提是序列已分区）。

这些算法共同构成了C++11中分区操作的基础工具，结合谓词机制可灵活应用于数据筛选、分类和边界查找等场景。