Home C&C++函数库 c++ 语法 程序源码 Linux C库

std::

partition

函数模板  <algorithm>
C++98
template <class BidirectionalIterator, class UnaryPredicate>
  BidirectionalIterator partition (BidirectionalIterator first,
                                   BidirectionalIterator last, UnaryPredicate pred);

范围分区为二

随机重新排列[first,last)范围内的元素。

重新排列范围[first,last]中的元素,使pred返回true的所有元素先于返回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
C++98: 指向分区序列的初始和最终位置的双向迭代器。使用的范围是[first,last), 它包含first和last1之间的所有元素,包括first指向的元素,但不包括last指向的元素。

C++11: 指向分区序列的初始和最终位置的前向迭代器.使用的范围是[first,last), 它包含first和last之间的所有元素,包括first指向的元素,但不包括last指向的元素。
前向迭代器(ForwardIterator)必须指向一个定义了swap的类型,并交换其实参的值。

pred
一个一元函数,它接受范围中的一个元素作为参数,并返回一个可转换为bool的值。 返回的值指示是否将该元素放在前面(如果为真,则将其放在所有返回false的元素之前)。
函数不应修改其参数。
它可以是函数指针,也可以是函数对象。

☉  返回值



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

☣  示例



// 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 and last 之间的距离线性: 对每个元素应用pred,并可能交换其中一些元素 (如果迭代器类型是双向的,最多交换量的一半)。

⇄ 数据竞争


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

☂ 异常安全性



如果元素交换或迭代器上的操作抛出,则抛出。
注意,无效的参数会导致未定义的行为。

🍄  另请参阅



rotate 旋转元素(函数模板)
reverse 反转元素(函数模板)
find_if 在范围内查找元素(函数模板)
swap 交换两个对象的值(函数模板)

联系我们 免责声明 关于CandCplus 网站地图