STD:：C++中的稳定分区-yiteyi-C++库

这个 稳定分区（） 算法排列由start和end定义的序列，使得pfn指定的谓词返回true的所有元素都位于谓词返回false的元素之前。分区是稳定的。这意味着序列的相对顺序得以保留。 语法：

null

template 
BiIter stable_partition(BiIter start, BiIter end, UnPred pfn);

参数：

start:  the range of elements to reorder
end:  the range of elements to reorder
pfn:  User-defined predicate function object that 
defines the condition to be satisfied if an element is to be classified.
A predicate takes single argument and returns true or false.
Return Value: 
Returns an iterator to the beginning of the elements 
for which the predicate is false.

此函数尝试分配一个临时缓冲区。如果分配失败，则选择效率较低的算法。 例1：

                     // CPP program to illustrate stable_partition                   
                     #include <iostream>                   
                     #include <algorithm>                   
                     #include <vector>                   
                     using                               namespace                               std;                   
                     int                               main()                   
                     {                   
                                         vector<                               int                               > v{ 6, 9, 0, 1, 2, 7, 5, 8, 0 };                   
                                         stable_partition(v.begin(), v.end(), [](                               int                               n) {                               return                               n>0; });                   
                                         for                               (                               int                               n : v) {                   
                                         cout << n <<                               ' '                               ;                   
                                         }                   
                                         cout <<                               ''                               ;                   
                     }                   

输出：

6 9 1 2 7 5 8 0 0

例2：

                     // CPP program to illustrate stable_partition                   
                     #include <iostream>                   
                     #include <algorithm> // std::stable_partition                   
                     #include <vector>                   
                             
                     bool                               odd(                               int                               i) {                               return                               (i % 2) == 1; }                   
                             
                     int                               main()                   
                     {                   
                                         std::vector<                               int                               > vct;                   
                             
                                         for                               (                               int                               i = 1; i < 10; ++i)                   
                                         vct.push_back(i);                               // 1 2 3 4 5 6 7 8 9                   
                             
                                         std::vector<                               int                               >::iterator bound;                   
                                         bound = std::stable_partition(vct.begin(), vct.end(), odd);                   
                             
                                         std::cout <<                               "odd numbers:"                               ;                   
                                         for                               (std::vector<                               int                               >::iterator it = vct.begin(); it != bound; ++it)                   
                                         std::cout <<                               ' '                               << *it;                   
                                         std::cout <<                               ''                               ;                   
                             
                                         std::cout <<                               "evennumbers:"                               ;                   
                                         for                               (std::vector<                               int                               >::iterator it = bound; it != vct.end(); ++it)                   
                                         std::cout <<                               ' '                               << *it;                   
                                         std::cout <<                               ''                               ;                   
                             
                                         return                               0;                   
                     }                   

输出：

odd numbers: 1 3 5 7 9
even numbers: 2 4 6 8

例3：

                     // CPP program to illustrate stable_partition                   
                     #include <algorithm>                   
                     #include <deque>                   
                     #include <functional>                   
                     #include <iostream>                   
                     #include <iterator>                   
                             
                     template                               <                               class                               Arg>                   
                     struct                               is_even :                               public                               std::unary_function<Arg,                               bool                               > {                   
                                         bool                               operator()(                               const                               Arg& arg1)                               const                   
                                         {                   
                                         return                               (arg1 % 2) == 0;                   
                                         }                   
                     };                   
                             
                     int                               main()                   
                     {                   
                                         typedef                               std::deque<                               int                               , std::allocator<                               int                               > > Deque;                   
                                         typedef                               std::ostream_iterator<                               int                               ,                               char                               ,                   
                                         std::char_traits<                               char                               > >                   
                                         Iter;                   
                             
                                         const                               Deque::value_type a[] = { 1, 2, 3, 4, 5,                   
                                         6, 7, 8, 9, 10 };                   
                             
                                         Deque d1(a + 0, a +                               sizeof                               a /                               sizeof                               *a);                   
                                         Deque d2(d1);                   
                             
                                         std::cout <<                               "Unpartitioned values: 		"                               ;                   
                                         std::copy(d1.begin(), d1.end(), Iter(std::cout,                               " "                               ));                   
                             
                                         std::partition(d2.begin(), d2.end(), is_even<                               int                               >());                   
                                         std::cout <<                               "Partitioned values: 		"                               ;                   
                                         std::copy(d2.begin(), d2.end(), Iter(std::cout,                               " "                               ));                   
                             
                                         std::stable_partition(d1.begin(), d1.end(),                   
                                         is_even<                               int                               >());                   
                                         std::cout <<                               "Stable partitioned values: 	"                               ;                   
                                         std::copy(d1.begin(), d1.end(), Iter(std::cout,                               " "                               ));                   
                                         std::cout << std::endl;                   
                             
                                         return                               0;                   
                     }                   

输出：

Unpartitioned values:         1 2 3 4 5 6 7 8 9 10 
Partitioned values:         10 2 8 4 6 5 7 3 9 1 
Stable partitioned values:     2 4 6 8 10 1 3 5 7 9

复杂性： 谓词的结束-开始应用程序，如果内存不足，最多（结束-开始）*日志（结束-开始）交换；如果内存充足，则交换的线性数。

本文由 希瓦尼·古泰尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章