stable_partition-c和c++中文资料站

C&C++标准库

std::

stable_partition

函数模板 <algorithm>

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

对范围稳定有序分区

重新排列[first,last]范围内的元素，使pred返回true的所有元素先于返回false的所有元素，并且，与函数 partition不同的是，保留每个组内元素的相对顺序。

这通常使用内部临时缓冲区实现。

☲ 参数

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

双向迭代器(BidirectionalIterator)必须指向一个定义了swap的类型 (并交换其实参的值)，并且该类型是可移动构造和可移动赋值的。
pred: 一个一元函数，它接受范围中的一个元素作为参数，并返回一个可转换为bool的值。返回的值指示该元素是否属于第一组(如果为真，则将其放在所有返回false的元素之前)。
函数不应修改其参数。
它可以是函数指针，也可以是函数对象。

☉ 返回值

指向第二组元素(pred返回false的元素)的第一个元素的迭代器，如果这组元素为空，则指向最后一个元素.

☣ 示例

// stable_partition example
#include <iostream>     // std::cout
#include <algorithm>    // std::stable_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::stable_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 3 5 7 9
even elements: 2 4 6 8

✥ 复杂度

如果有足够的额外内存， first and last之间的距离是线性的:对每个元素只应用pred一次，并在多个元素移动时执行。

否则，接近线性:执行最多N*log(N)的元素交换(其中N是 first and last的距离)。它还对每个元素只应用一次pred。

⇄ 数据竞争

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

☂ 异常安全性

如果任何元素比较、元素交换(或移动)或迭代器上的操作抛出，则抛出。
注意，无效的参数会导致未定义的行为。

🍄 另请参阅

partition	对范围分区 (函数模板)
sort	对范围内的元素进行排序(函数模板)
reverse	反转元素(函数模板)
find_if	在范围内查找元素(函数模板)