C++ stable_partition()
C++算法stable_partition()
C++算法 stable_partition()函数用于对[first,last)范围内的元素进行分类,例如一种这样的方式,所有pred返回true的元素都在其返回false的所有元素之前,保留元素的相对顺序。
注意: -此功能通常使用内部临时缓冲区来实现。
语法
template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator stable_partition (BidirectionalIterator first,
BidirectionalIterator last,
UnaryPredicate pred);
参数
first: 一个双向迭代器,指向要分区范围内的第一个元素。
last : 指向要分区范围中最后一个元素的双向迭代器。
pred : 用户定义的一元谓词函数,用于定义条件
返回值
此函数将迭代器返回到不满足谓词条件的范围的第一个元素。
复杂度
如果有足够的内存,则复杂度在[first,last)范围内是线性的: 将pred应用于每个元素。
数据竞争
[first,last)范围内的对象被修改。
异常
此函数抛出如果元素的任何比较,元素交换或对迭代器的操作引发任何异常,都会引发异常。
请注意,无效参数会导致未定义的行为。
示例1
让我们看一个简单的示例来演示stable_partition()的用法:
#include <iostream> // std::cout
#include <algorithm> // std::stable_partition
#include <vector> // std::vector
using namespace std;
bool IsOdd (int i) { return (i%2)==1; }
int main () {
vector<int> myvector;
// set some values:
for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9
vector<int>::iterator bound;
bound = stable_partition (myvector.begin(), myvector.end(), IsOdd);
// print out content:
cout << "odd elements:";
for (vector<int>::iterator it=myvector.begin(); it!=bound; ++it)
cout << ' ' << *it;
cout << '\n';
cout << "even elements:";
for (vector<int>::iterator it=bound; it!=myvector.end(); ++it)
cout << ' ' << *it;
cout << '\n';
return 0;
}
输出:
odd elements: 1 3 5 7 9
even elements: 2 4 6 8
在上面的示例中,从1到9的元素被划分为偶数和奇数元素。
示例2
让我们看另一个简单的示例:
#include <vector>
#include <algorithm>
#include <iostream>
bool greater5 ( int value ) {
return value >5;
}
int main( ) {
using namespace std;
vector <int> v1, v2;
vector <int>::iterator Iter1, Iter2, result;
int i;
for ( i = 0 ; i <= 10 ; i++ )
v1.push_back( i );
int ii;
for ( ii = 0 ; ii <= 4 ; ii++ )
v1.push_back( 5 );
random_shuffle(v1.begin( ), v1.end( ) );
cout << "Vector v1 is ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Partition the range with predicate greater10
result = stable_partition (v1.begin( ), v1.end( ), greater5 );
cout << "The partitioned set of elements in v1 is:\n ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
cout << "The first element in v1 to fail to satisfy the"
<< "\n predicate greater5 is: " << *result << "." << endl;
return 0;
}
输出:
Vector v1 is ( 4 10 5 5 5 5 5 1 6 9 3 7 8 2 0 5 ).
The partitioned set of elements in v1 is:
( 10 6 9 7 8 4 5 5 5 5 5 1 3 2 0 5 ).
The first element in v1 to fail to satisfy the
predicate greater5 is: 4.
示例3
让我们看看另一个简单的示例,该示例使用partition()函数对vector的元素进行快速排序:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
vector<int> v{0, 0, 3, 0, 2, 4, 5, 0, 7};
stable_partition(v.begin(), v.end(), [](int n){return n>0;});
for (int n : v) {
cout << n << ' ';
}
cout << '\n';
return 0;
}
输出:
示例4
让我们看另一个简单的示例:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v = {1, 0, 3, 4, 5, 6, 12, 7, 9};
stable_partition(v.begin(), v.end(), [](int x) { return x % 3 == 0; });
for_each(v.begin(), v.end(), [](int x) {
cout << x << endl;
});
return 0;
}
输出: