std::partition

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

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

对范围进行分区

重新排列范围 [first,last) 中的元素，使得所有 pred 返回 true 的元素都位于 pred 返回 false 的元素之前。返回的迭代器指向第二个组的第一个元素。

各组内的相对顺序不一定与调用前相同。有关具有类似行为但各组内顺序稳定的函数，请参阅 stable_partition。

此函数模板（C++98）的行为等同于

template <class BidirectionalIterator, class UnaryPredicate>
  BidirectionalIterator partition (BidirectionalIterator first,
                                   BidirectionalIterator last, UnaryPredicate pred)
{
  while (first!=last) {
    while (pred(*first)) {
      ++first;
      if (first==last) return first;
    }
    do {
      --last;
      if (first==last) return first;
    } while (!pred(*last));
    swap (*first,*last);
    ++first;
  }
  return first;
}

参数

first, last: 双向迭代器指向要分区的序列的起始和结束位置。使用的范围是 [first,last)，它包含 first 和 last1 之间的所有元素，包括 first 指向的元素，但不包括 last 指向的元素。

前向迭代器指向要分区的序列的起始和结束位置。使用的范围是 [first,last)，它包含 first 和 last 之间的所有元素，包括 first 指向的元素，但不包括 last 指向的元素。
ForwardIterator 应指向一个 swap 已定义且能交换其参数值的类型。
pred: 一元函数，它接受范围内的元素作为参数，并返回一个可转换为 bool 的值。返回值指示元素是否应放在前面（如果为 true，则该元素放在所有 pred 返回 false 的元素之前）。
该函数不得修改其参数。
这可以是函数指针，也可以是函数对象。

返回值

指向第二个元素组（pred 返回 false 的元素）的第一个元素的迭代器，如果该组为空，则为 last。

示例

// partition algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::partition
#include <vector>       // std::vector

bool IsOdd (int i) { return (i%2)==1; }

int main () {
  std::vector<int> myvector;

  // set some values:
  for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9

  std::vector<int>::iterator bound;
  bound = std::partition (myvector.begin(), myvector.end(), IsOdd);

  // print out content:
  std::cout << "odd elements:";
  for (std::vector<int>::iterator it=myvector.begin(); it!=bound; ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  std::cout << "even elements:";
  for (std::vector<int>::iterator it=bound; it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

可能的输出

odd elements: 1 9 3 7 5
even elements: 6 4 8 2

复杂度

线性复杂度，复杂度为 first 和 last 之间距离的线性复杂度：对每个元素应用 pred，并可能交换其中一些元素（如果迭代器类型是双向的，则交换次数最多为该距离的一半，否则最多为该距离）。

数据竞争

范围[first,last)内的对象将被修改。

异常

如果元素交换或迭代器操作引发异常，则抛出异常。
请注意，无效参数会导致未定义行为。

另见

reverse: 反转范围（函数模板）

rotate: 将范围中的元素向左旋转（函数模板）

find_if: 在范围中查找元素（函数模板）

swap: 交换两个对象的值（函数模板）