c++ STL划分算法；partition()、partition_copy()、stable_partition()、partition_point()详解

2024 年 05 月 15 日

138 次浏览

2871字数

C++ Standard Template Library (STL) 提供了一系列高效的算法，用于操作容器中的元素。在这些算法中，partition()、partition_copy()、stable_partition() 和 partition_point() 是用于数据划分的重要成员，它们各自有着独特的功能和适用场景。下面是对这些算法的详细解析：

1. `partition()`

partition() 算法将给定范围内的元素分为两部分，使得一部分的元素满足某个谓词（predicate）条件，而另一部分的元素则不满足。这个过程通过交换元素位置来实现，但不保证保持原有元素的相对顺序。该算法返回一个迭代器，指向第一个不满足谓词条件的元素。

原型:

template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred);

使用示例:

std::vector<int> numbers = {1, 2, 3, 4, 5, 6};
auto is_even = [](int x) { return x % 2 == 0; };
auto it = std::partition(numbers.begin(), numbers.end(), is_even);

在这个例子中，it 会指向第一个奇数，使得 numbers的前半部分全为偶数。

2. `partition_copy()`

partition_copy() 算法类似于 partition()，但它不是在原容器内部重新排列元素，而是将满足谓词条件的元素复制到一个输出序列中，不满足条件的元素复制到另一个输出序列中。这个过程不会改变原容器的内容。

原型:

template <class InputIterator, class OutputIterator1, class OutputIterator2, class UnaryPredicate>
std::pair<OutputIterator1, OutputIterator2>
partition_copy(InputIterator first, InputIterator last, OutputIterator1 out_true, OutputIterator2 out_false, UnaryPredicate pred);

使用示例:

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> evens, odds;
auto is_even = [](int x) { return x % 2 == 0; };
std::tie(evens.end(), odds.end()) = std::partition_copy(src.begin(), src.end(), evens.begin(), odds.begin(), is_even);

这段代码将偶数复制到 evens 向量中，奇数复制到 odds 向量中。

3. `stable_partition()`

stable_partition() 算法与 partition() 类似，也是将元素划分为满足和不满足谓词条件的两部分，但不同之处在于它会保持原序列中满足条件的元素的相对顺序不变。也就是说，它是一个稳定版本的划分算法。

原型:

template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred);

使用示例:

std::list<int> numbers = {1, 3, 5, 2, 4, 6};
auto is_even = [](int x) { return x % 2 == 0; };
auto it = std::stable_partition(numbers.begin(), numbers.end(), is_even);

在此例中，序列被分为偶数和奇数两部分，且原序列中偶数的相对顺序保持不变。

4. `partition_point()`

partition_point() 算法用于确定一个已分区序列中谓词条件从假变为真的分界点的迭代器位置。它假设序列已经被 partition() 或 stable_partition() 处理过，或者自然满足分区条件。这个函数对于了解分区的边界非常有用。

原型:

template <class ForwardIterator, class UnaryPredicate>
ForwardIterator partition_point(ForwardIterator first, ForwardIterator last, UnaryPredicate pred);

使用示例:

std::vector<int> sorted_numbers = {1, 2, 4, 6, 7, 9};
auto is_less_than_5 = [](int x) { return x < 5; };
auto boundary = std::partition_point(sorted_numbers.begin(), sorted_numbers.end(), is_less_than_5);

在这里，boundary 将指向第一个大于等于5的元素，即 sorted_numbers 中满足 is_less_than_5 由 true 变为 false 的位置。