C++ partition_point()
C++算法partition_point()
C++算法 partition_point()函数用于返回给定范围中pred不为真的第一个元素。以满足条件的元素排在不满足条件的元素之前的方式对元素进行排序。
语法
template <class ForwardIterator, class UnaryPredicate>
ForwardIterator partition_point (ForwardIterator first, ForwardIterator last,
UnaryPredicate pred);
参数
first: 前向迭代器,指向范围中的第一个元素以检查条件。
last : 指向范围的最后一个元素的前向迭代器。
pred : 用户定义的一元谓词
返回值
此函数返回正向迭代器,以指向不满足测试条件的第一个元素如果找不到,则返回pred或last。
复杂度
复杂度在[first,last)范围内是对数的。
数据竞争
可以访问[first,last)范围内的某些对象。
异常
如果元素的比较或迭代器上的操作引发异常,则此函数引发异常。
注意: 无效的参数会导致未定义的行为。
示例1
让我们看一个简单的示例来演示partition_point()的用法:
#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>
using namespace std;
int main()
{
array<int, 9> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
auto is_even = [](int i)
{ return i % 2 == 0; };
partition(v.begin(), v.end(), is_even);
auto p = std::partition_point(v.begin(), v.end(), is_even);
cout << "Before partition:\n ";
copy(v.begin(), p, ostream_iterator<int>(cout, " "));
cout << "\nAfter partition:\n ";
copy(p, v.end(), ostream_iterator<int>(cout, " "));
return 0;
}
输出:
Before partition:
8 2 6 4
After partition:
5 3 7 1 9
示例2
让我们看另一个简单的示例:
#include <iostream> // std::cout
#include <algorithm> // std::partition, std::partition_point
#include <vector> // std::vector
using namespace std;
bool IsOdd (int i) { return (i%2)==1; }
int main () {
vector<int> foo {1,2,3,4,5,6,7,8,9};
vector<int> odd;
partition (foo.begin(),foo.end(),IsOdd);
auto it = partition_point(foo.begin(),foo.end(),IsOdd);
odd.assign (foo.begin(),it);
// print contents of odd:
cout << "odd:";
for (int& x:odd) cout << ' ' << x;
cout << '\n';
return 0;
}
输出:
示例3
让我们看另一个简单的示例:
#include<iostream>
#include<algorithm> // for partition algorithm
#include<vector> // for vector
using namespace std;
int main()
{
// Initializing vector
vector<int> vect = { 2, 1, 5, 6, 8, 7 };
// partitioning vector using stable_partition()
// in sorted order
stable_partition(vect.begin(), vect.end(), [](int x)
{
return x%2 == 0;
});
// Displaying partitioned Vector
cout << "The partitioned vector is : ";
for (int &x : vect) cout << x << " ";
cout << endl;
// Declaring iterator
vector<int>::iterator it1;
// using partition_point() to get ending position of partition
auto it = partition_point(vect.begin(), vect.end(), [](int x)
{
return x%2==0;
});
// Displaying partitioned Vector
cout << "The vector elements returning true for condition are : ";
for ( it1= vect.begin(); it1!=it; it1++)
cout << *it1 << " ";
cout << endl;
return 0;
}
输出:
The partitioned vector is : 2 6 8 1 5 7
The vector elements returning true for condition are : 2 6 8
示例4
让我们看另一个简单的示例:
#include <iostream> // std::cout
#include <algorithm> // std::partition, std::partition_point
#include <vector> // std::vector
using namespace std;
bool IsNegative(int i) { return (i < 0); }
int main()
{
vector<int> data{ 1,-1, 3,-4, 5, 2,-2, 4,-5,-3 };
vector<int> negative, positive;
// partition data on the basis of odd elements using
// pred IsNegative()
stable_partition(data.begin(), data.end(), IsNegative);
// gets the partition point based on odd elements
auto it = 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:
cout << "Negative: ";
for (int& x : negative)
cout << ' ' << x;
cout << '\n';
// print contents of even:
cout << "Positive: ";
for (int& x : positive)
cout << ' ' << x;
cout << '\n';
return 0;
}
输出:
Negative: -1-4-2-5-3
Positive: 1 3 5 2 4