STLalgorithm算法partition_point,stable_partition(44)
partition_point原型：
std::partition_point
template <class ForwardIterator, class UnaryPredicate>
ForwardIterator partition_point (ForwardIterator first, ForwardIterator last,
UnaryPredicate pred);
该函数返回范围内第一个不符合pred（即返回值为false）的元素的迭代器.
范围内的元素应该已经进行过划分，即使用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;
}
一个简单的例子：
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
using namespace std;
int main(){
vector<int> vi{8,5,10,7,1,3,5,8,9,13};
cout<<"vi=";
for_each(vi.begin(),vi.end(),[](int i){cout<<i<<" ";});
cout<<endl;
if(is_partitioned(vi.begin(),vi.end(),[](int n){return n%2==0;}))
cout<<"v1 is a partitioned!"<<endl;
else
cout<<"v1 not a partitioned!"<<endl;
auto it=partition(vi.begin(),vi.end(),[](int n){return n%2==0;});
cout<<"after auto it=partition(vi.begin(),vi.end(),[](int n){return n%2==0;}); "<<endl;
cout<<"vi=";
for_each(vi.begin(),vi.end(),[](int i){cout<<i<<" ";});
cout<<endl;
if(is_partitioned(vi.begin(),vi.end(),[](int n){return n%2==0;}))
cout<<"v1 is a partitioned!"<<endl;
else
cout<<"v1 not a partitioned!"<<endl;
cout<<"*it="<<*it<<endl;
auto it2=partition_point(vi.begin(),vi.end(),[](int n){return n%2==0;});
cout<<"auto it2=partition_point(vi.begin(),vi.end(),[](int n){return n%2==0;});"<<endl;
cout<<"it2="<<*it2<<endl;
}
运行结果：
返回值和partition是一样的。
stable_partition原型：
std::stable_partition
template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator stable_partition (BidirectionalIterator first,
BidirectionalIterator last,
UnaryPredicate pred);
该函数对范围内的元素进行稳定划分。
返回值为第一个返回false的元素的迭代器，如果没有，则返回last.
和partition是有区别的，当然在数值上是看不出来的。区别为：
稳定和不稳定，这对数值没有什么用，但对于多属性的对象就有用了。 如以下组合序列，按括号外的数排序，括号内是另一个属性， 1（1）， 3（2）， 5（3）， 5（4）， 7（5）， 9（6） ， 7（7） 稳定排序后 1（1）， 3（2）， 5（3）， 5（4）， 7（5）， 7（7） ， 9（6） 两个5和两个7的相对位置不变， 不稳定排序后，可以是5（4）， 5（3）或7（7）， 7（5）
感谢：http://zhidao.baidu.com/link?url=wpPsrq1rg5IQioAZ_afz4Qd5drgWSUfiw-GU1GcK_ur3cwNlLCgzwVIR5q0sEdsmS_H0ajKWM97wVsJcgK6uUuH-cl9_ZZzE4wRdTMi1M7e
一个简单的例子：
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
using namespace std;
int main(){
vector<int> vi{8,5,10,7,1,3,5,8,9,13};
cout<<"vi=";
for_each(vi.begin(),vi.end(),[](int i){cout<<i<<" ";});
cout<<endl;
if(is_partitioned(vi.begin(),vi.end(),[](int n){return n%2==0;}))
cout<<"v1 is a partitioned!"<<endl;
else
cout<<"v1 not a partitioned!"<<endl;
auto it=stable_partition(vi.begin(),vi.end(),[](int n){return n%2==0;});
cout<<"after auto it=stable_partition(vi.begin(),vi.end(),[](int n){return n%2==0;}); "<<endl;
cout<<"vi=";
for_each(vi.begin(),vi.end(),[](int i){cout<<i<<" ";});
cout<<endl;
if(is_partitioned(vi.begin(),vi.end(),[](int n){return n%2==0;}))
cout<<"v1 is a partitioned!"<<endl;
else
cout<<"v1 not a partitioned!"<<endl;
cout<<"*it="<<*it<<endl;
}
运行截图：
——————————————————————————————————————————————————————————————————
//写的错误或者不好的地方请多多指导，可以在下面留言或者点击左上方邮件地址给我发邮件，指出我的错误以及不足，以便我修改，更好的分享给大家，谢谢。
转载请注明出处：http://blog.csdn.net/qq844352155
author:天下无双
Email:coderguang@gmail.com
2014-9-22
于GDUT
——————————————————————————————————————————————————————————————————