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;
}

输出：

odd: 1 9 3 7 5

示例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