C++ 算法 stable_partition()

2024年8月30日 | 阅读4分钟

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) 成线性关系：将谓词应用于每个元素。

数据竞争

范围 [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() 函数对向量元素进行快速排序

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

输出

3 2 4 5 7 0 0 0 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;
}

输出

下一主题C++ 算法

C++ 算法 stable_partition()

注意：- 此函数通常使用内部临时缓冲区实现。

语法

参数

返回值

复杂度

数据竞争

异常

示例 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++ 算法 stable_partition()

注意：- 此函数通常使用内部临时缓冲区实现。

语法

参数

返回值

复杂度

数据竞争

异常

示例 1

示例 2

示例 3

示例 4

相关帖子

algorithm replace_copy() 函数

algorithm partition() 函数

algorithm for_each() 函数

algorithm upper_bound() 函数

algorithm lower_bound() 函数

algorithm count() 函数

algorithm rotate() 函数

algorithm is_sorted() 函数

algorithm swap_ranges() 函数