stable_partition


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

原型

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

描述

stable_partition非常类似于partition: 它根据函数对象pred对范围内的元素进行重新排序[first, last), 使得所有满足条件的元素都出现在所有不满足条件的元素之前。后置条件是，对于范围内的某个迭代器[first, last)middle,pred(*i)pred, 对于每个迭代器i[first, middle)都为truepred(*i), 并且对于每个迭代器i[middle, last)都为truepred(*i)都为falsestable_partitioni,.

stable_partition. 的返回值与partition不同，因为stable_partition保证保留相对顺序。也就是说，如果xiy是pred中的元素，并且pred(x) == pred(y), 并且如果xxy在stable_partitionyxxy. [1]

之前，那么在

执行之后，

x

仍然会出现在y
之前。定义
仍然会出现在在标准头文件 algorithm 中定义，在非标准向后兼容头文件 algo.h 中也有定义。之前。类型要求

ForwardIterator

pred是前向迭代器的模型

Predicate

stable_partition是谓词的模型's 值类型可以转换为's 参数类型。前提条件i是有效的范围。复杂度前提条件是一个自适应算法：它尝试分配一个临时内存缓冲区，它的运行时间复杂度取决于可用内存的大小。最坏情况行为（如果不可用辅助内存）最多为[first, last)N*log(N)前提条件次交换，其中

N

last - first

int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
const int N = sizeof(A)/sizeof(int);
stable_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 "2 4 6 8 10 1 3 5 7 9". [1]

, 最佳情况（如果可用足够大的辅助内存缓冲区）在

Nstable_partition中是线性的。无论哪种情况，partition都会被精确调用partition.

N

partition次。

示例对序列进行重新排序，使偶数位于奇数之前。