C++ Std partition point

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

partition point() 获取分区点：返回一个迭代器，指向范围 [first, last] 中第一个 pred(谓词) 为 false 的分区元素，指示该元素的分区点。

就好像已使用相同的输入调用了 partition，范围的元素必须已经分区。

该函数比较已排序范围的非连续元素，这对于随机访问迭代器尤其有效，可以减少比较次数。

返回给定范围中第一个 pred 为 false 的元素需要使用 C++ 算法 partition point() 函数。元素被排列成满足条件的元素放置在不满足条件的元素之前。

语法

ForwardIterator partition_point(ForwardIterator first, 
                                  ForwardIterator last,
                                  UnaryPredicate pred); 

first 和 last 参数是向前迭代器，分别指向已分区序列的开头和结尾。已测试的范围是 [first, last]，它包含 first 和 last 之间的所有元素，但不包括 last 指向的元素。

一个一元函数，它将范围元素作为参数并返回一个可转换为布尔值的值。结果显示元素是否在分区点之前（如果为 true，则在之前；如果为 false，则在分区点或之后）。其参数不能被函数修改。这可以是一个函数对象或函数指针。

返回值：如果 pred 对于任何元素都为 false，则返回一个迭代器，指向分区范围 [first, last] 中的最后一个元素，或者如果 pred 对于任何元素都为 false，则返回最后一个元素。

此函数模板的定义等效于

template 
  ForwardIterator partition_point (ForwardIterator first, ForwardIterator last,
                                   UnaryPredicate pred)

{
  auto n = distance(first, last);
  while (n>0)
  {
    ForwardIterator it = first;
    auto step = n/2;
    std::advance (it, step);
    if (pred(*it)) { first=++it; n-=step+1; }
    else n=step;
  }
  return first;
}

示例

// C++ program to get odd elements
// and even elements
#include <iostream> // std::cout

#include <algorithm> // std::partition, std::partition_point
#include <vector> // std::vector

bool IsOdd(int i) { return (i % 2) == 1; }

int main()
{
	std::vector<int> data{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	std::vector<int> odd, even;

	// partition data on the basis of odd elements
	// using pred IsOdd()
	std::stable_partition(data.begin(), data.end(), IsOdd);

	// gets the partition point based on odd elements
	auto it = std::partition_point(data.begin(), data.end(),
													IsOdd);

	// assign elements to odd from beginning till partition
	// point.
	odd.assign(data.begin(), it);
	even.assign(it, data.end());

	// print contents of odd:
	std::cout << "odd:";
	for (int& x : odd)
		std::cout << ' ' << x;
	std::cout << '\n';

	// print contents of even:
	std::cout << "even:";
	for (int& x : even)
		std::cout << ' ' << x;
	std::cout << '\n';

	return 0;
}

输出

odd:  1 3 5 7 9
even: 2 4 6 8 10

示例

// C++ program to get negative elements
// and positive elements using partition_point
#include <iostream> // std::cout

#include <algorithm> // std::partition, std::partition_point
#include <vector> // std::vector

bool IsNegative(int i) { return (i < 0); }

int main()
{
	std::vector<int> data{ 1, -1, 3, -4, 5, 2, -2, 4,
											-5, -3 };
	std::vector<int> negative, positive;

	// partition data on the basis of odd elements using
	// pred IsNegative()
	std::stable_partition(data.begin(), data.end(),
									IsNegative);

	// gets the partition point based on odd elements
	auto it = std::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:
	std::cout << "Negative: ";
	for (int& x : negative)
		std::cout << ' ' << x;
	std::cout << '\n';

	// print contents of even:
	std::cout << "Positive: ";
	for (int& x : positive)
		std::cout << ' ' << x;
	std::cout << '\n';

	return 0;
}

输出

Negative:  -1 -4 -2 -5 -3
Positive:  1 3 5 2 4

执行大约 log2(N)+2 次元素比较（其中 N 是此距离）。在非随机访问迭代器上，迭代器前进平均会为 N 增加线性复杂度。

示例

#include <iostream>
#include <algorithm>
#include <vector>

bool IsOdd(int i) { return (i % 2) == 1; }
int main(){
   std::vector<int> data{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
   std::vector<int> odd, even;
   std::stable_partition(data.begin(), data.end(), IsOdd);
   auto it = std::partition_point(data.begin(), data.end(),
   IsOdd);
   odd.assign(data.begin(), it);
   even.assign(it, data.end());
   std::cout << "odd:";
   for (int& x : odd)
      std::cout << ' ' << x;
   std::cout << '\n';
   std::cout << "even:";
   for (int& x : even)
      std::cout << ' ' << x;
   std::cout << '\n';
   return 0;
}

输出

odd: 1 3 5 7 9
even: 2 4 6 8 10

下一主题在 C++ 中打开和关闭文件 Pdf

← prev next →

C++ Std partition point

语法

示例

示例

示例

联系信息

关注我们

教程

面试题

在线编译器

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++ Std partition point

语法

示例

示例

示例

相关帖子

C++ 中范围内所有子数组按位与和的查询

C++ 中的自顶向下方法是什么

C++ Cuckoo 散列

C++ STL 中的 multimap::emplace_hint() 函数

C++ Cin.ignore() 函数

C++ 属性

C++ 程序实现模幂运算算法

现代 C++ 中 STL 算法的执行策略

C++ Elo 评分算法

Boost C++ | C++ 编程中 Boost 的历史、目的、优点

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器