C++ 算法 partition_point()

30 Aug 2024 | 3 分钟阅读

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

下一主题C++ 算法

C++ 算法 partition_point()

语法

参数

返回值

复杂度

数据竞争

异常

注意：无效参数会导致未定义行为。

示例 1

示例 2

示例 3

示例 4

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 算法 partition_point()

语法

参数

返回值

复杂度

数据竞争

异常

注意：无效参数会导致未定义行为。

示例 1

示例 2

示例 3

示例 4

相关帖子

algorithm inplace_merge() 函数

algorithm find_first_of() 函数

algorithm partial_sort_copy() 函数

algorithm unique() 函数

algorithm copy_if() 函数

algorithm lower_bound() 函数

C++ Thread hardware_concurrency() 函数

algorithm remove_if() 函数

algorithm fill() 函数