分区

ℹ️ 什么是分区？
一个集合的分区是指将该集合分解为若干子集，使得集合中的每个元素恰好属于其中一个子集。在 C++ 中，这些子集由一元谓词定义：满足该谓词的元素属于第一个子集，其余元素则属于第二个子集。

C++ 提供了几种用于处理分区的函数。它们都接受一个一元谓词 pre 作为参数。std::partition 和 std::stable_partition 接收一个谓词和一个范围，根据谓词对范围进行分区，并返回分区点。使用 std::partition_point 可以获取已分区范围的分区点。之后可以使用 std::is_partitioned 检查范围是否已正确分区，或使用 std::partition_copy 将分区结果复制到两个不同的范围中。

std::is_partitioned：检查范围是否已分区。

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

std::partition：对范围进行分区。

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

std::stable_partition：以保持元素相对顺序的方式对范围进行分区。

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

std::partition_copy：将分区结果复制到两个不同的范围中。

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)

std::partition_point：返回分区点。

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

std::stable_partition 与 std::partition 不同，它保证元素的相对顺序不变。std::partition 和 std::stable_partition 返回的迭代器（FwdIt 和 BiIt）指向分区后第二部分的起始位置。std::partition_copy 返回的 std::pair<OutIt, OutIt> 包含两个输出范围的结束迭代器，分别对应满足和不满足谓词的元素。如果输入范围未被正确分区，则 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}

---

在下一课中，我们将学习如何在 C++ 中轻松实现排序。