STL 源代码剖析 算法 stl_algo.h -- partition

本文为senlie原创，转载请保留此地址：http://blog.csdn.net/zhengsenlie

partition

------------------------------------------------------------------------



描写叙述：partition 会将区间[first,last) 中的元素又一次排列。全部被一元条件运算 pred 判定为 true 的元素，都会被放在区间的前段，

被判定为 false 的元素，都会被放在区间的后段。

partition 不稳定，不保证 partition 后元素保留在原始相对位置。 stable_partition 稳定

思路：

1.first往下查找，遇到"符合移动条件"(pred不成立)的就停下来

2.last往上查找，遇到"符合移动条件"(pred成立)的就停下来

3.交换 *first 和 *last, ++first, --last



复杂度：O(n)

源代码：

//全部被 pred 判定为 true 的元素，都被放到前段

//被 pred 判定为 false 的元素，都被放到后段

//不保证保留相对位置

template <class BidirectionalIterator, class Predicate>

BidirectionalIterator partition(BidirectionalIterator first,

                                BidirectionalIterator last, Predicate pred) {

  while (true) {

    while (true)

      if (first == last)

        return first;

      else if (pred(*first))

        ++first;

      else

        break;

    --last;

    while (true)

      if (first == last)

        return first;

      else if (!pred(*last))

        --last;

      else

        break;

    iter_swap(first, last);

    ++first;

  }

}

演示样例：

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".