极客笔记C++ 标准分区点
partition_point()获取分区点：返回范围[first, last]中第一个分区元素的迭代器，该元素满足谓词pred为假，表示该元素的分区点。
如果假设使用相同的输入调用了partition函数，那么范围的元素必须已经被分区。
该函数比较排序范围中非连续的元素，对于随机访问迭代器特别有效，以减少比较的数量。
返回满足pred为假的所提供范围的第一个元素需要使用C++算法partition_point()函数。元素被安排在满足条件的元素之前。
语法
ForwardIterator partition_point(ForwardIterator first,
ForwardIterator last,
UnaryPredicate pred);
第一个和最后一个参数是前向迭代器，分别指向分区序列的开始和结尾。已经测试的范围是[first, last]，其中包括了first和last之间的所有元素，但不包括last所指向的元素。
一个一元函数，以范围元素为参数，并返回一个可以转换为布尔值的值。结果显示在分区点之前的元素是否为真（如果为真，则在之前；如果为假，则在分区点或之后）。函数不能修改其参数。这可以是一个函数对象或一个函数指针。
返回值： 如果对于任何元素pred为false，则返回分区范围[first, last]中的最后一个元素的迭代器，或者如果对于任何元素pred都为false，则返回最后一个元素的迭代器。
这个函数模板的定义相当于：
template
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;
}
示例
// C++ program to get odd elements
// and even elements
#include // std::cout
#include // std::partition, std::partition_point
#include // std::vector
bool IsOdd(int i) { return (i % 2) == 1; }
int main()
{
std::vector data{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
std::vector odd, even;
// partition data on the basis of odd elements
// using pred IsOdd()
std::stable_partition(data.begin(), data.end(), IsOdd);
// gets the partition point based on odd elements
auto it = std::partition_point(data.begin(), data.end(),
IsOdd);
// assign elements to odd from beginning till partition
// point.
odd.assign(data.begin(), it);
even.assign(it, data.end());
// print contents of odd:
std::cout << "odd:";
for (int& x : odd)
std::cout << ' ' << x;
std::cout << '\n';
// print contents of even:
std::cout << "even:";
for (int& x : even)
std::cout << ' ' << x;
std::cout << '\n';
return 0;
}
输出：
odd: 1 3 5 7 9
even: 2 4 6 8 10
示例
// C++ program to get negative elements
// and positive elements using partition_point
#include // std::cout
#include // std::partition, std::partition_point
#include // std::vector
bool IsNegative(int i) { return (i < 0); }
int main()
{
std::vector data{ 1, -1, 3, -4, 5, 2, -2, 4,
-5, -3 };
std::vector negative, positive;
// partition data on the basis of odd elements using
// pred IsNegative()
std::stable_partition(data.begin(), data.end(),
IsNegative);
// gets the partition point based on odd elements
auto it = std::partition_point(data.begin(), data.end(),
IsNegative);
// assign elements to odd from beginning till
// partition point.
negative.assign(data.begin(), it);
positive.assign(it, data.end());
// print contents of odd:
std::cout << "Negative: ";
for (int& x : negative)
std::cout << ' ' << x;
std::cout << '\n';
// print contents of even:
std::cout << "Positive: ";
for (int& x : positive)
std::cout << ' ' << x;
std::cout << '\n';
return 0;
}
输出：
Negative: -1 -4 -2 -5 -3
Positive: 1 3 5 2 4
大约执行了log2(N)+2个元素比较（其中N是此距离）。迭代器的前进在非随机访问迭代器上提供了额外的线性复杂度，平均而言。
示例
#include
#include
#include
bool IsOdd(int i) { return (i % 2) == 1; }
int main(){
std::vector data{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
std::vector odd, even;
std::stable_partition(data.begin(), data.end(), IsOdd);
auto it = std::partition_point(data.begin(), data.end(),
IsOdd);
odd.assign(data.begin(), it);
even.assign(it, data.end());
std::cout << "odd:";
for (int& x : odd)
std::cout << ' ' << x;
std::cout << '\n';
std::cout << "even:";
for (int& x : even)
std::cout << ' ' << x;
std::cout << '\n';
return 0;
}
输出：
odd: 1 3 5 7 9
even: 2 4 6 8 10