C++ STL算法partition/stable

partition

函数原型

template
_NODISCARD inline _FwdIt partition(_FwdIt _First, _FwdIt _Last, _Pr _Pred)

partition可直译为“分组”，partition函数可根据用户自定义的筛选规则，重新排列指定区域内存储的数据，使其分为 2 组，第一组为符合筛选条件的数据，另一组为不符合筛选条件的数据。

如数组a[9]：1 2 3 4 5 6 7 8 9 。设定筛选规则为 i%2==0（其中 i 指数组 a 中各元素），则借助 partition() 函数，a[9] 数组中存储数据的顺序可能变为：8; 6; 2; 4; 5; 7; 3; 1; 9; ，第 一组为{8， 6， 2， 4} ，第二组{5， 7， 3，1， 9} 。

显然前者中的各个元素都符合筛选条件，而后者则都不符合。由此还可看出，partition函数只会根据筛选条件将数据进行分组，并不关心分组后各个元素具体的存储位置。

参数

• fisrt last 输入容器
• pred 可以是函数指针或函数对象或lambda表达式

#include 
#include 
#include 
#include 
#include 
#include 
#include 

bool isEven(int a)
{
	std::cout << "a = " << a << std::endl;
	return a % 2 == 0;
}

class IsEven
{
public:
	bool operator()(int value, int b)
	{
		std::cout << "value = " << value << std::endl;
		return 0 == value % b;
	}

};

int main()
{	
	std::array a ={ 1, 3, 2, 4, 5, 7, 6, 8, 9 };
	
	std::partition(std::begin(a), std::end(a), isEven);
	std::cout << "偶数a: ";
	std::copy(std::begin(a), std::end(a), std::ostream_iterator(std::cout, "; "));
	std::cout << "n";

	auto f = std::bind(IsEven(), std::placeholders::_1, 3);
	std::partition(std::begin(a), std::end(a), f);
	std::cout << "能被3整除a: ";
	std::copy(std::begin(a), std::end(a), std::ostream_iterator(std::cout, "; "));
	std::cout << "n";

	return -1;
}

//输出
a = 1
a = 9
a = 8
a = 3
a = 6
a = 2
a = 4
a = 5
a = 7
偶数a: 8; 6; 2; 4; 5; 7; 3; 1; 9;

value = 8
value = 9
value = 6
value = 2
value = 1
value = 3
value = 4
value = 7
value = 5
能被3整除a: 9; 6; 3; 4; 5; 7; 2; 1; 8;

stable_partition

template 
inline_BidIt stable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred)

stable_partition可以保证对区域内数据完成分组的同时，不改变各组内元素的相对位置。

如数组a[9]：1 2 3 4 5 6 7 8 9 。设定筛选规则为 i%2==0（其中 i 指数组 a 中各元素），则借助 partition() 函数，a[9] 数组中存储数据的顺序可能变为：2; 4; 6; 8; 1; 3; 5; 7; 9; ，第 一组为{2， 4， 6， 8} ，第二组{1， 3， 5，7， 9} 。通过与上面 a[9] 对比不难看出，各组元素的相对位置没有发生改变。

所谓元素的相对位置不发生改变，以{2,4,6,8} 中的元素 4 为例，在原 a[9] 数组中，该元素位于 2 的右侧，6 和 8 的左侧；在经stable_partition函数后a[9] 数组中，元素 4 仍位于 2 的右侧，6 和 8 的左侧。故该元素的相对位置确实没有发生改变。

参数

• fisrt last 输入容器
• pred 可以是函数指针或函数对象或lambda表达式

函数/仿函数 

#include 
#include 
#include 
#include 
#include 
#include 
#include 

bool isEven(int a)
{
	std::cout << "a = " << a << std::endl;
	return a % 2 == 0;
}

class IsEven
{
public:
	bool operator()(int value, int b)
	{
		std::cout << "value = " << value << std::endl;
		return 0 == value % b;
	}

};

int main()
{	
	std::array a ={ 1, 3, 2, 4, 5, 7, 6, 8, 9 };
	
	std::stable_partition(std::begin(a), std::end(a), isEven);
	std::cout << "偶数a: ";
	std::copy(std::begin(a), std::end(a), std::ostream_iterator(std::cout, "; "));
	std::cout << "n";

	auto f = std::bind(IsEven(), std::placeholders::_1, 3);
	std::stable_partition(std::begin(a), std::end(a), f);
	std::cout << "能被3整除a: ";
	std::copy(std::begin(a), std::end(a), std::ostream_iterator(std::cout, "; "));
	std::cout << "n";

	return -1;
}

//输出
a = 1
a = 9
a = 8
a = 3
a = 2
a = 4
a = 5
a = 7
a = 6
偶数a: 2; 4; 6; 8; 1; 3; 5; 7; 9;
value = 2
value = 9
value = 4
value = 6
value = 8
value = 1
value = 3
value = 5
value = 7
能被3整除a: 6; 3; 9; 2; 4; 8; 1; 5; 7;