分区

ℹ️ 什么是划分（partition）？

一个集合的划分是指将该集合分解为若干子集，使得集合中的每个元素恰好属于其中一个子集。在 C++ 中，这种划分通过一元谓词（unary predicate）来定义：满足谓词条件的元素构成第一个子集，其余元素则组成第二个子集。

C++ 提供了若干用于处理划分的操作函数，它们都需要一个一元谓词 pre。std::partition 和 std::stable_partition 用于对一个范围进行划分，并返回划分点。使用 std::partition_point 可以获取已划分范围的划分点。之后可以通过 std::is_partitioned 检查某个范围是否已被正确划分，或使用 std::partition_copy 将划分结果复制到两个不同的目标范围中。

检查范围是否已划分：

1bool is_partitioned(InpIt first, InpIt last, UnPre pre)
2bool is_partitioned(ExePol pol, FwdIt first, FwdIt last, UnPre pre)

对范围进行划分：

1FwdIt partition(FwdIt first, FwdIt last, UnPre pre)
2FwdIt partition(ExePol pol, FwdIt first, FwdIt last, UnPre pre)

稳定地对范围进行划分（保持元素相对顺序）：

1BiIt stable_partition(BiIt first, BiIt last, UnPre pre)
2BiIt stable_partition(ExePol pol, BiIt first, BiIt last, UnPre pre)

将划分后的元素分别复制到两个输出范围：

1pair<OutIt1, OutIt2> partition_copy(InIt first, InIt last, OutIt1 result_true, OutIt2 result_false, UnPre pre)
2pair<FwdIt1, FwdIt2> partition_copy(ExePol pol, FwdIt1 first, FwdIt1 last, FwdIt2 result_true, FwdIt3 result_false, UnPre pre)

返回划分点的位置：

1FwdIt partition_point(FwdIt first, FwdIt last, UnPre pre)

与 std::partition 不同，std::stable_partition 能够保证划分前后各元素在其所属子集内的相对顺序不变。上述函数返回的迭代器（如 FwdIt 或 BiIt）指向划分后第二部分子集的第一个元素位置。而 std::partition_copy 返回的 std::pair<OutIt1, OutIt2> 则分别包含两个输出子集的尾后迭代器（即结束位置）。需要注意的是，若给定范围尚未被正确划分，则调用 std::partition_point 的行为是未定义的。

示例代码：

1#include <algorithm>
2#include <cctype>
3#include <deque>
4#include <iostream>
5#include <list>
6#include <string>
7#include <vector>
8 
9bool isOdd(int i){ return (i%2); }
10 
11int main(){
12 
13  std::cout << std::boolalpha << std::endl;
14 
15  std::vector<int> vec{1, 4, 3, 4, 5, 6, 7, 3, 4, 5, 6, 0, 4, 8, 4, 6, 6, 5, 8, 8, 3, 9, 3, 7, 6, 4, 8};
16 
17  for ( auto v: vec ) std::cout << v << " ";
18 
19  std::cout << "\n\n";
20 
21  auto parPoint= std::partition(vec.begin(), vec.end(), isOdd);
22   
23  for (auto v: vec) std::cout << v << " ";
24  std::cout << std::endl;
25  for (auto v= vec.begin(); v != parPoint; ++v) std::cout << *v << " ";
26  std::cout << std::endl;
27  for (auto v= parPoint; v != vec.end(); ++v) std::cout << *v << " ";
28  std::cout << std::endl;
29   
30  std::cout << std::endl;
31 
32  std::cout << "std::is_partitioned: " << std::is_partitioned(vec.begin(), vec.end(), isOdd) << std::endl;
33 
34  std::cout << "std::partition_point: " << (std::partition_point(vec.begin(), vec.end(), isOdd) == parPoint) << std::endl;
35 
36  std::cout << std::endl;
37   
38  std::list<int> li;
39  std::list<int> de;
40  std::partition_copy(vec.begin(), vec.end(), std::back_inserter(li), std::back_inserter(de), [](int i) { return i < 5; });
41  
42  for (auto v: li) std::cout << v << " ";
43  std::cout <<  std::endl;
44  for (auto v: de) std::cout << v << " "; 
45   
46  std::cout << "\n\n";
47   
48}