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

C&C++标准库

std::

partition_point

函数模板 <algorithm>

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

获取分区点

返回一个迭代器，指向划分范围[first,last)中pred不为true的第一个元素，表示其划分点.

范围内的元素应该已经被分区了，就好像用相同的参数调用了partition一样。

该函数通过比较排序范围内的非连续元素来优化比较次数，这对于随机访问迭代器特别有效。

这个函数模板的行为相当于:

template <class ForwardIterator, class UnaryPredicate>
  ForwardIterator partition_point (ForwardIterator first, ForwardIterator last,
                                   UnaryPredicate pred)
{
  auto n = distance(first,last);
  while (n>0)
  {
    ForwardIterator it = first;
    auto step = n/2;
    std::advance (it,step);
    if (pred(*it)) { first=++it; n-=step+1; }
    else n=step;
  }
  return first;
}

☲ 参数

first, last: 指向已经分区的序列的初始和最终位置的前向迭代器。使用的范围是[first,last)，它包含first和last之间的所有元素，包括first指向的元素，但不包括last指向的元素。
pred: 返回的值指示元素是否在划分点之前(如果为true，它在划分点之前;如果false在它后面)。
函数不应修改其参数。
它可以是函数指针，也可以是函数对象。

☉ 返回值

指向分区范围[first,last]中pred不为真值的第一个元素的迭代器，如果pred对任何元素都不为真值，则为last。

☣ 示例

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

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

int main () {
  std::vector<int> foo {1,2,3,4,5,6,7,8,9};
  std::vector<int> odd;

  std::partition (foo.begin(),foo.end(),IsOdd);

  auto it = std::partition_point(foo.begin(),foo.end(),IsOdd);
  odd.assign (foo.begin(),it);

  // print contents of odd:
  std::cout << "odd:";
  for (int& x:odd) std::cout << ' ' << x;
  std::cout << '\n';

  return 0;
}

输出:
odd: 1 3 5 7 9

✥ 复杂度

平均看,first and last之间的距离是对数:大约执行log2(N)+2元素比较(N是这个距离)。

对于非随机访问迭代器，迭代器 advances会平均增加N的线性复杂度。

⇄ 数据竞争

[first,last)范围内的一些对象被访问。

☂ 异常安全性

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

🍄 另请参阅

partition	对范围分区 (函数模板)
find_if_not	在范围内查找元素(函数模板)
binary_search	测试value是否存在于排序序列中(函数模板)