分区


类别：算法	组件类型：函数

原型

template <class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator first,
                          ForwardIterator last, Predicate pred)

描述

分区重新排序范围内的元素[first, last)基于函数对象pred，使得满足条件的元素pred位于不满足条件的元素之前。后置条件是，对于范围内的某个迭代器middle，在范围内[first, last), pred(*i)为true对于每个迭代器i，在范围内[first, middle)并且false对于每个迭代器i，在范围内[middle, last)。 [1] 的返回值分区为middle.

定义

在标准头文件 algorithm 中定义，并在非标准向后兼容头文件 algo.h 中定义。

类型要求

ForwardIterator是前向迭代器的模型。
谓词是谓词的模型。
ForwardIterator的值类型可转换为谓词的参数类型。

先决条件

[first, last)是一个有效的范围。

复杂度

线性。正好last - first应用pred，最多(last - first)/2交换。

示例

重新排序序列，使偶数位于奇数之前。

int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
const int N = sizeof(A)/sizeof(int);
partition(A, A + N,
          compose1(bind2nd(equal_to<int>(), 0),
                   bind2nd(modulus<int>(), 2)));
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The output is "10 2 8 4 6 5 7 3 9 1". [1]

注释

[1] 这两个块中元素的相对顺序不一定与原始序列中的相同。另一种算法，stable_partition，确实保证保留相对顺序。

另请参阅

stable_partition，谓词，函数对象