partition与stable_partition

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

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

1. 将数组中的元素分为两部分，第一部分[first,middle)中的每个元素都是pred(i)为true，第二部分[middle,last)中的每个元素都是pred(i)为false
2. 返回值为middle
3. partition执行速度很快，除非要求稳定性使用stable_partition,否则使用partition
4. partition不保证与原来的数组中元素相对顺序相同，sable_partition保证

5. stable_partition是一个adpative算法，会试图分配内存缓冲区，其运行复杂度取决于缓冲区中有多少内存，最坏情况下没有分配任何内存，至多调用swap Nlog(N)次，N为last-first，最好情况下（缓冲区中有足够内存）与N呈线性关系，两种情况下pred都被调用N次

   #include <iostream>
   #include <vector>
   #include <algorithm>
   #include <iterator>
   #include <functional>
   using namespace std;
   
   class F
   {
       public:
           bool operator()(int i)
           {
               return (i&1)==0;    
           }    
   };
   int main()
   {
       vector<int> v{1,2,3,4,5,6};
       auto it=stable_partition(v.begin(),v.end(),F());
       for_each(v.begin(),v.end(),[](int i)
       {
           cout<<i<<" ";
       });
       cout<<endl;
       return 0;
   }

    

partition与stable_partition

原文：https://www.cnblogs.com/tianzeng/p/10386097.html