【跟学C++】C++STL标准模板库——算法详细整理(下)(Study18)

 ============================ 【说明】 ===================================================
  大家好，本专栏主要是跟学C++内容，自己学习了这位博主【 AI菌】的【C++21天养成计划】，讲的十分清晰，适合小白，希望给这位博主多点关注、收藏、点赞。
  主要针对所学内容，通过自己的理解进行整理，希望大家积极交流、探讨，多给意见。后面也会给大家更新，其他一些知识。若有侵权，联系删除！共同维护网络知识权利！
 =======================================================================================
   写在前面
  至此，我们了解了C++的基本语法，但是进一步学习C++，数据结构是必不可少的内容。 数据结构与算法决定了代码测存储方式，以及代码执行效率。
  数据结构的重要性不言而喻， 关于数据结构的基本知识可以转至本人另一专栏====>【 数据结构】。同样也可以阅读博主【 AI菌】写的【 数据结构与算法】，比较通俗易懂，可以学习学习！

---

1、简介

  上一节，详细介绍了STL标准模板库——算法整理(上)相关内容，介绍了STL算法分类及常用函数，详细说明非变序算法的常用函数，今天我们继续介绍关于变序算法的一些常用函数及注意点。

2、STL算法分类及常用函数

  STL算法模板库分为两大类：非变序与变序。对于这两种类别如何理解？下面就详细介绍两大类以及各函数的具体应用。

2.2、变序算法（二）

  

---

2.2.1 替换算法(2个)

  

  (1)replace

  replace() ：功能是用新的值来替换和给定值相匹配的元素。
  前2个参数是被处理序列的正向迭代器；
  第 3 个参数是被替换的值；
  第 4 个参数是新的值。

  
  关于replace案例如下：

//==================5.6、replace
int main(){
	deque<int> data{ 10, -5, 12, -6, 10, 8, -7, 10, 11 };
	replace(begin(data), end(data), 10, 99);
	copy(begin(data), end(data), ostream_iterator<int>{cout," "});
	cout << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9

  data 容器中和 10 匹配的全部元素都会被 99 替代。

  
  (2)replace_if

  eplace_if() 会将使谓词返回 true 的元素替换为新的值。
  前2个参数与上述一致，是被处理序列的正向迭代器；
  第 3 个参数是一个谓词；
  第 4 个参数是新的值。
  参数的类型一般是元素类型的 const 引用；const 不是强制性的，但谓词不应该改变元素。

  
  关于replace_if案例如下：

//==================5.7、replace_if
int main(){
	string password{ "This is a good choice !" };
	replace_if(begin(password), end(password), [](char ch) {return isspace(ch); }, '_');
	copy(begin(password), end(password), ostream_iterator<char>{cout, ""});
}
1
2
3
4
5
6

  第3个参数这个谓词会为任何是空格字符的元素返回 true，因此这里的空格都会被下划线代替。

  

---

2.2.2 排序算法(6个)

  
  (1)sort

  sort()：该函数专门用来对容器或普通数组中指定范围内的元素进行排序，排序规则默认升序排序，除此之外我们也可以选择标准库提供的其它排序规则（比如std::greater降序排序规则），甚至还可以自定义排序规则。

  对于sort()算法要注意的是：sort() 函数是基于快速排序实现的，函数受到底层实现方式的限制，它仅适用于普通数组和部分类型的容器。
  （1）sort() 只对 array、vector、deque 这 3 个容器提供支持。
  （2）如果对容器中指定区域的元素做默认升序排序，则元素类型必须支持<小于运算符；同样，如果选用标准库提供的其它排序规则，元素类型也必须支持该规则底层实现所用的比较运算符；
  （3）sort() 函数在实现排序时，需要交换容器中元素的存储位置。这种情况下，如果容器中存储的是自定义的类对象，则该类的内部必须提供移动构造函数和移动赋值运算符。

  sort()算法有两种语法格式：

//对 [first, last) 区域内的元素做默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则，对 [first, last) 区域内的元素进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4

  first 和 last 都为随机访问迭代器，它们的组合 [first, last) 用来指定要排序的目标区域；
  另外在第 2 种格式中，comp 可以是 C++ STL 标准库提供的排序规则（比如 std::greater），也可以是自定义的排序规则。

  
  关于sort案例如下：

//==================6、sort

//以普通函数的方式实现自定义排序规则
bool mycomp(int i, int j) {
	return (i < j);
}
//以函数对象的方式实现自定义排序规则
class mycomp2 {
public:
	bool operator() (int i, int j) {
		return (i < j);
	}
};

int main() {
	std::vector<int> myvector{ 52, 61, 8, 35, 36, 70, 63, 23 };
	//调用第一种语法格式，只对 52, 61, 8, 35 进行排序
	sort(myvector.begin(), myvector.begin() + 4); //(8, 35, 52, 61), 36, 70, 63, 23
	copy(begin(myvector), end(myvector), ostream_iterator<int>{cout," "});
	cout << endl;




	//调用第二种语法格式，利用STL标准库提供的其它比较规则（比如 greater）进降序行排序
	sort(myvector.begin(), myvector.begin() + 4, std::greater<int>()); //(61，52，35，8), 36, 70, 63, 23
	copy(begin(myvector), end(myvector), ostream_iterator<int>{cout, " "});
	cout << endl;



	//调用第二种语法格式，通过自定义比较规则进行排序
	sort(begin(myvector), myvector.end(), mycomp2());//8，23，35，36，52，61，63，70
	
	//输出 myvector 容器中的元素
	for (vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it) {
		cout << *it << ' ';
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

  
  (2)stable_sort

  前面阐述了sort() 函数的功能和用法。但是，当指定范围内包含多个相等的元素时，sort() 排序函数无法保证不改变它们的相对位置。那么，如果既要完成排序又要保证相等元素的相对位置，stable_sort()可以看作是 sort() 的升级版，它除了可以实现排序，还可以保证不改变相等元素的相对位置。

  table_sort() 函数的用法也有 2 种，其语法格式和 sort() 函数完全相同（仅函数名不同）：

//对 [first, last) 区域内的元素做默认的升序排序
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );
//按照指定的 comp 排序规则，对 [first, last) 区域内的元素进行排序
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );
1
2
3
4

  first 和 last 都为随机访问迭代器，它们的组合 [first, last) 用来指定要排序的目标区域；
  另外在第 2 种格式中，comp 可以是 C++ STL 标准库提供的排序规则（比如 std::greater），也可以是自定义的排序规则。
  
  关于stable_sort案例同sort，换个函数名即可，当遇到相同元素时，相对位置不会发生变化。

  
  (3)partial_sort

  在某种场景下，若某容器元素很多(上百/千万级别)，而需求是仅要筛选其中10个最小的元素，那对整个容器进行排序再去筛选的效率就比较低下。
  partial_sort()功能就是可以从指定区域中提取出部分数据，并对它们进行排序。
  partial_sort() 函数有 2 种用法，其语法格式分别为：

//按照默认的升序排序规则，对 [first, last) 范围的数据进行筛选并排序
void partial_sort (RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last);
//按照 comp 排序规则，对 [first, last) 范围的数据进行筛选并排序
void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last, Compare comp);
1
2
3
4

  first、middle 和 last 都是随机访问迭代器，comp 参数用于自定义排序规则。
  partial_sort() 函数会以交换元素存储位置的方式实现部分排序的，会将 [first, last) 范围内最小（或最大）的 middle-first 个元素移动到 [first, middle) 区域中，并对这部分元素做升序（或降序）排序。

  对于partial_sort()算法要注意的是：函数受到底层实现方式的限制，它仅适用于普通数组和部分类型的容器。
  （1）partial_sort() 只对 array、vector、deque 这 3 个容器提供支持。
  （2）如果对容器中指定区域的元素做默认升序排序，则元素类型必须支持<小于运算符；同样，如果选用标准库提供的其它排序规则，元素类型也必须支持该规则底层实现所用的比较运算符；
  （3）partial_sort() 函数在实现排序时，需要交换容器中元素的存储位置。这种情况下，如果容器中存储的是自定义的类对象，则该类的内部必须提供移动构造函数和移动赋值运算符。

  
  关于partial_sort案例如下：

//==================6.1、partial_sort

//以普通函数的方式实现自定义排序规则
bool mycomp61(int i, int j) {
	return (i > j);
}
//以函数对象的方式实现自定义排序规则
class mycomp62 {
public:
	bool operator() (int i, int j) {
		return (i > j);
	}
};

int main() {

	vector<int> myvector{ 52, 61, 8, 35, 36, 70, 63, 23 };
	cout << "初始序列:" << endl;
	copy(myvector.begin(), myvector.end(), ostream_iterator<int>{cout, " "});
	cout << endl;



	//以默认的升序排序作为排序规则，将 myvector 中最小的 5 个元素移动到开头位置并排好序
	partial_sort(myvector.begin(), myvector.begin() + 5, myvector.end());
	cout << "对myvector最小的 5 个元素移动到开头位置并排好序:" << endl;
	copy(myvector.begin(), myvector.end(), ostream_iterator<int>{cout," "});
	cout << endl;


	// 以指定的 mycomp62 作为排序规则，将 myvector 中最大的 5 个元素移动到开头位置并排好序

	partial_sort(myvector.begin(), myvector.begin() + 5, myvector.end(), mycomp62());
	cout << "对myvector最大的 5 个元素移动到开头位置并排好序:" << endl;
	copy(myvector.begin(), myvector.end(), ostream_iterator<int>{cout, " "});
	cout << endl;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

  
  (4)partial_sort_copy

  partial_sort_copy() 函数的功能和 partial_sort() 类似，唯一的区别在于，partial_sort_copy() 不会对原有数据做任何变动，而是先将选定的部分元素拷贝到另外指定的数组或容器中，然后再对这部分元素进行排序。

  同样partial_sort_copy() 函数也有 2 种语法格式，分别为：

//默认以升序规则进行部分排序
RandomAccessIterator partial_sort_copy (
                       InputIterator first,
                       InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last);
//以 comp 规则进行部分排序
RandomAccessIterator partial_sort_copy (
                       InputIterator first,
                       InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last,
                       Compare comp);
1
2
3
4
5
6
7
8
9
10
11
12
13

  first 和 last 为输入迭代器；result_first 和 result_last 为随机访问迭代器；comp 用于自定义排序规则。
  partial_sort_copy() 函数会将 [first, last) 范围内最小（或最大）的 result_last-result_first 个元素复制到 [result_first, result_last) 区域中，并对该区域的元素做升序（或降序）排序。
  对于partial_sort_copy()算法要注意的是：partial_sort_copy() 函数放宽了对存储原有数据的容器类型的限制。该函数还支持对 list 容器或者 forward_list 容器中存储的元素进行“部分排序”，而 partial_sort() 函数不行。

  
  关于partial_sort_copy案例如下：

//==================6.2、partial_sort_copy

//以普通函数的方式实现自定义排序规则
bool mycomp621(int i, int j) {
	return (i > j);
}
//以函数对象的方式实现自定义排序规则
class mycomp622 {
public:
	bool operator() (int i, int j) {
		return (i > j);
	}
};

int main() {


	vector<int> myvector{ 52, 61, 8, 35, 36, 70, 63, 23 };
	vector <int> newvector(5);


	cout << "初始序列:" << endl;
	copy(myvector.begin(), myvector.end(), ostream_iterator<int>{cout, " "});
	cout << endl;
	cout << "=======================================" << endl;

	//按照默认的排序规则进行部分排序
	partial_sort_copy(myvector.begin(), myvector.end(), newvector.begin(), newvector.begin() + 5);
	
	
	cout << "partial_sort_copy后的myvector序列:" << endl;
	copy(myvector.begin(), myvector.end(), ostream_iterator<int>{cout, " "});
	cout << endl;


	cout << "partial_sort_copy后的newvector序列:" << endl;
	copy(newvector.begin(), newvector.end(), ostream_iterator<int>{cout, " "});
	cout << endl;

	//====================================================
	cout << "=======================================" << endl;
	//以自定义的 mycomp2 作为排序规则，进行部分排序

	partial_sort_copy(myvector.begin(), myvector.end(), newvector.begin(), newvector.begin() + 5,mycomp622());
	
	cout << "partial_sort_copy后的myvector序列:" << endl;
	copy(myvector.begin(), myvector.end(), ostream_iterator<int>{cout, " "});
	cout << endl;


	cout << "partial_sort_copy后的newvector序列:" << endl;
	copy(newvector.begin(), newvector.end(), ostream_iterator<int>{cout, " "});
	cout << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

  从代码中可以看到，程序中调用了 2 次 partial_sort_copy() 函数，其作用分别是：
  第一次：采用默认的升序排序规则，在 myvector容器中筛选出最小的 5 个元素，然后将它们复制到 newvector[5] 数组中，并对这部分元素进行升序排序；
  第二次：：采用自定义的 mycomp622 降序排序规则，从 myvector容器筛选出最大的 5 个元素，同样将它们复制到 newvector[5] 数组中，并对这部分元素进行降序排序；

  
  (5)is_sorted

  不同的排序算法，所消耗的时间不一，不管哪种排序算法都需要一定的时间，但是对于本身已经是有序的序列而言，对其进行排序属于浪费资源，我们可以利用is_sorted()专门来判断某个序列是否为有序序列。
  is_sorted() 函数有 2 种语法格式，分别是：

//判断 [first, last) 区域内的数据是否符合 std::less 排序规则，即是否为升序序列
bool is_sorted (ForwardIterator first, ForwardIterator last);
//判断 [first, last) 区域内的数据是否符合 comp 排序规则  
bool is_sorted (ForwardIterator first, ForwardIterator last, Compare comp);
1
2
3
4

  first 和 last 都为正向迭代器（这意味着该函数适用于大部分容器），[first, last) 用于指定要检测的序列；comp 用于指定自定义的排序规则。
  注意：如果使用默认的升序排序规则，则 [first, last) 指定区域内的元素必须支持使用 < 小于运算符做比较；同样，如果指定排序规则为 comp，也要保证 [first, last) 区域内的元素支持该规则内部使用的比较运算符。

  
  关于is_sorted案例如下：

//==================6.3、is_sorted

//以普通函数的方式实现自定义排序规则
bool mycomp631(int i, int j) {
	return (i > j);
}
//以函数对象的方式实现自定义排序规则
class mycomp632 {
public:
	bool operator() (int i, int j) {
		return (i > j);
	}
};

int main() {

	vector<int> myvector{ 3,5,4,1,6,2 };
	list<int> mylist{10,11,12,13,14};

	//调用第 2 种语法格式的 is_sorted() 函数，该判断语句会得到执行
	if (!is_sorted(myvector.begin(),myvector.end()))
	{
		cout << "myvector为非有序序列，对 myvector 容器排序：" << endl;
		//对 myvector 容器做降序排序
		sort(myvector.begin(), myvector.end(),mycomp632());
		cout << "排序后的myvector序列:" << endl;
		copy(myvector.begin(), myvector.end(), ostream_iterator<int>{cout, " "});
		cout << endl;
	}

	//=============================================
	cout << "==========================" << endl;


	//调用第一种语法格式的 is_sorted() 函数，该判断语句得不到执行
	int newlist[5] = { 0 };
	if (!is_sorted(mylist.begin(),mylist.end()))
	{
		cout << "mylist为非有序序列，对 mylist 容器排序：" << endl;
		//对 mylist 容器做降序排序
		//注意：sort()和partial_sort()不适用list容器，顾使用partial_sort_copy
		partial_sort_copy(mylist.begin(), mylist.end(), newlist, newlist+5);
		
	}

	else
	{
		cout << "该序列为有序升序序列，无需排序！" << endl;
	}
	
	return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

  注意：sort()和partial_sort()不适用list容器，顾使用partial_sort_copy。

  
  (6)is_sorted_until

  和is_sorted()函数相比 ，is_sorted_until() 函数不仅能检测出某个序列是否有序，还会返回一个正向迭代器，该迭代器指向的是当前序列中第一个破坏有序状态的元素。

  is_sorted_until() 函数也有以下 2 种语法格式：

//排序规则为默认的升序排序
ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last);
//排序规则是自定义的 comp 规则
ForwardIterator is_sorted_until (ForwardIterator first,
                                 ForwardIterator last,
                                 Compare comp);
1
2
3
4
5
6

  first 和 last 都为正向迭代器（这意味着该函数适用于大部分容器），[first, last) 用于指定要检测的序列；comp 用于指定自定义的排序规则。
  注意：如果使用默认的升序排序规则，则 [first, last) 指定区域内的元素必须支持使用 < 小于运算符做比较；同样，如果指定排序规则为 comp，也要保证 [first, last) 区域内的元素支持该规则内部使用的比较运算符。

  
  关于is_sorted_until案例如下：’

//==================6.4、is_sorted_until

//以普通函数的方式实现自定义排序规则
bool mycomp641(int i, int j) {
	return (i > j);
}
//以函数对象的方式实现自定义排序规则
class mycomp642 {
public:
	bool operator() (int i, int j) {
		return (i > j);
	}
};

int main() {

	vector<int> myvector{ 3,5,4,1,6,2 };
	list<int> mylist{ 10,11,12,13,14 };

	//调用第 2 种语法格式的 is_sorted() 函数，该判断语句会得到执行
	if (is_sorted_until(myvector.begin(), myvector.end())!=myvector.end())
	{
		cout << "myvector为非有序序列，对 myvector 容器排序：" << endl;
		//对 myvector 容器做降序排序
		sort(myvector.begin(), myvector.end(), mycomp632());
		cout << "排序后的myvector序列:" << endl;
		copy(myvector.begin(), myvector.end(), ostream_iterator<int>{cout, " "});
		cout << endl;
	}

	//=============================================
	cout << "==========================" << endl;


	//调用第一种语法格式的 is_sorted() 函数，该判断语句得不到执行
	int newlist[5] = { 0 };
	if (is_sorted_until(mylist.begin(), mylist.end()) != mylist.end())
	{
		cout << "mylist为非有序序列，对 mylist 容器排序：" << endl;
		//对 mylist 容器做降序排序
		//注意：sort()和partial_sort()不适用list容器，顾使用partial_sort_copy
		partial_sort_copy(mylist.begin(), mylist.end(), newlist, newlist + 5);

	}

	else
	{
		cout << "该序列为有序升序序列，无需排序！" << endl;
	}


	return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

  注意：区别在于判断条件if (is_sorted_until(myvector.begin(), myvector.end())!=myvector.end())，is_sorted_until()返回的是迭代器指向的是当前序列中第一个破坏有序状态的元素，指向第一个破坏有序状态元素后，判断条件成立，即对序列进行重新排序。

  

---

2.2.3 分区算法(4个)

  
  (1)partition

  partition() 函数可根据用户自定义的筛选规则，重新排列指定区域内存储的数据，使其分为 2 组，第一组为符合筛选条件的数据，另一组为不符合筛选条件的数据。例如：
  原始序列：1 2 3 4 5 6 7 8 9
  筛选规则为i%2=0
  筛选后的结果为：1 9 3 7 5 6 4 8 2

  但是，partition() 函数只会根据筛选条件将数据进行分组，并不关心分组后各个元素具体的存储位置。

  partition() 函数的语法格式如下：

ForwardIterator partition (ForwardIterator first,
                           ForwardIterator last,
                           UnaryPredicate pred);
1
2
3

  first 和 last 都为正向迭代器，其组合 [first, last) 用于指定该函数的作用范围；pred 用于指定筛选规则。

  
  关于partition案例如下：

//==================7、partition

//以普通函数的方式实现自定义排序规则
bool mycomp71(int i) {
	return (i%2==0);
}
//以函数对象的方式实现自定义排序规则
class mycomp72 {
public:
	bool operator() (int i) {
		return (i % 2 == 0);
	}
};
int main() {
	vector<int> myvector{10, 11, 12, 13, 14, 15};
	vector<int>::iterator point;

	point = partition(myvector.begin(), myvector.end(), mycomp72());

	copy(myvector.begin(), myvector.end(), ostream_iterator<int>{cout, " "});
	cout << endl;

	cout << "point="<< *point << endl;



	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

  该代码利用parition() 函数将myvector容器分成两组，利用筛选规则一组符合，另一组不符合，同时parition()会返回一个迭代器，该迭代器指向的是元素 13，同时也是第 2 组数据中的第 1 个元素。

  
  (2)stable_partition

  上面的partition() 函数只负责对指定区域内的数据进行分组，并不保证各组中元素的相对位置不发生改变。而如果想在分组的同时保证不改变各组中元素的相对位置，可以使用 stable_partition() 函数。例如：
  原始序列：1 2 3 4 5 6 7 8 9
  筛选规则为i%2=0
  筛选后的结果为：2 4 6 8 1 3 5 7

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

  stable_partition() 函数其语法格式如下：

BidirectionalIterator stable_partition (BidirectionalIterator first,
                                        BidirectionalIterator last,
                                        UnaryPredicate pred);
1
2
3

  
  关于stable_partition案例如下：’

//==================7、partition/stable_partition

//以普通函数的方式实现自定义排序规则
bool mycomp71(int i) {
	return (i%2==0);
}
//以函数对象的方式实现自定义排序规则
class mycomp72 {
public:
	bool operator() (int i) {
		return (i % 2 == 0);
	}
};
int main() {
	vector<int> myvector{10, 11, 12, 13, 14, 15};
	vector<int>::iterator point;

	//point = partition(myvector.begin(), myvector.end(), mycomp72());

	point = stable_partition(myvector.begin(), myvector.end(), mycomp72());


	copy(myvector.begin(), myvector.end(), ostream_iterator<int>{cout, " "});
	cout << endl;

	cout << "point="<< *point << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

  
  (3)partition_copy

  上面已经详细介绍了 partition() 和 stable_partition() 函数的功能和用法。这 2 个函数在实现功能时，都直接修改了原序列中元素的存储位置。

  但是在某些场景中，我们需要类似 partition() 或者 stable_partition() 函数“分组”的功能，但并不想对原序列做任何修改。这种情况下，就可以考虑使用 partition_copy() 函数。

  partition_copy() 函数也能按照某个筛选规则对指定区域内的数据进行“分组”，并且分组后不会改变各个元素的相对位置。更重要的是，partition_copy() 函数不会对原序列做修改，而是以复制的方式将序列中各个元组“分组”到其它的指定位置存储。

  partition_copy() 语法格式如下：

pair<OutputIterator1,OutputIterator2> partition_copy (
                    InputIterator first, InputIterator last,
                    OutputIterator1 result_true, OutputIterator2 result_false,
                    UnaryPredicate pred);
1
2
3
4

  其中：
  first、last：都为输入迭代器，其组合 [first, last) 用于指定该函数处理的数据区域；
  result_true：为输出迭代器，其用于指定某个存储区域，以存储满足筛选条件的数据；
  result_false：为输出迭代器，其用于指定某个存储区域，以存储满足筛选条件的数据；
  pred：用于指定筛选规则，其本质就是接收一个具有 1 个参数且返回值类型为 bool 的函数。注意，该函数既可以是普通函数，还可以是一个函数对象。

  
  关于partition_copy案例如下：

//==================7.1、partition_copy
//以普通函数的方式定义筛选规则
bool mycomp711(int i) { return (i % 2) == 0; }

//以函数对象的形式定义筛选规则
class mycomp712 {
public:
	bool operator()(const int& i) {
		return (i % 2 == 0);
	}
};

int main() {
	vector<int> myvector{ 10, 11, 12, 13, 14, 15,16,17,18};
	int b[10] = { 0 }, c[10] = { 0 };
	//以 mycomp711 规则，对 myvector 容器中的数据进行分组，这里的 mycomp 还可以改为 mycomp2()，即以 mycomp2 为筛选规则
	pair<int*, int*> result = partition_copy(myvector.begin(), myvector.end(), b, c, mycomp711);
	cout << "b[10]：";
	
	for (int *p = b; p < result.first; p++) {
		cout << *p << " ";
	}

	cout << "\nc[10]：";
	for (int *p = c; p < result.second; p++) {
		cout << *p << " ";
	}
cout << "myvector序列：";
	copy(myvector.begin(), myvector.end(), ostream_iterator<int>{cout, " "});
	cout << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

  
  (4)partition_point

  partition()、stable_partition() 和 partition_copy() 这 3 个函数，它们的功能本质上都是根据某个筛选规则对指定范围内的数据进行分组（即符合条件的为一组，不符合条件的为另一组），并且反馈给我们两组数据之间的分界位置。
  有些数据本身就已经是按照某个筛选规则分好组的，例如：
  1,2,3,4,5,6,7 根据规则 i<4，{1,2,3} 为一组，{4,5,6,7} 为另一组
  2,4,6,8,1,3,5,7,9 根据规则 i%2=0，{2,4,6,8} 为一组，{1,3,5,7,9} 为另一组
  类似上面这样已经“分好组”的数据，在使用时会有一个问题，即不知道两组数据之间的分界在什么位置，再次调用partition()、stable_partition() 和 partition_copy() 这些函数也是可以的，但是不建议这么做，当然有更好的方法，partition_point() 就解决了这样的问题。

  partition_point()语法格式为：

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

  first 和 last 为正向迭代器，[first, last) 用于指定该函数的作用范围；pred 用于指定数据的筛选规则。
  
  关于partition_point案例如下：

//==================7.2、partition_point

//以普通函数的方式定义筛选规则
bool mycomp721(int i) { return i <= 14; }

//以函数对象的形式定义筛选规则
class mycomp722 {
public:
	bool operator()(const int& i) {
		return (i <= 14);
	}
};

int main() {
	vector<int> myvector{ 10, 11, 12, 13, 14, 15,16,17,18 };
	//根据 mycomp 规则，为 myvector 容器中的数据找出分界
	vector<int>::iterator iter = partition_point(myvector.begin(), myvector.end(), mycomp721);
	
	//输出第一组的数据
	for (auto it = myvector.begin(); it != iter; ++it) {
		cout << *it << " ";
	}
	cout << "\n";


	//输出第二组的数据
	for (auto it = iter; it != myvector.end(); ++it) {
		cout << *it << " ";
	}
	cout << "\n*iter = " << *iter;

	cout << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

  该代码可以看出，partition_point() 返回了一个指向元素 15 的迭代器，而该元素为 myvector 容器中第一个不符合 mycomp721 规则的元素，同时其也可以第二组数据中第一个元素。

  

---

2.2.4 可用于排序容器的算法(3个)

  
  (1)binary_search

  binary_search()该函数有 2 种语法格式，分别为：

//查找 [first, last) 区域内是否包含 val
bool binary_search (ForwardIterator first, ForwardIterator last,const T& val);
//根据 comp 指定的规则，查找 [first, last) 区域内是否包含 val
bool binary_search (ForwardIterator first, ForwardIterator last,const T& val, Compare comp);
1
2
3
4

  first 和 last 都为正向迭代器，[first, last) 用于指定该函数的作用范围；
  val 用于指定要查找的目标值；
  comp 用于自定义查找规则，此参数可接收一个包含 2 个形参（第一个形参值为 val）且返回值为 bool 类型的函数，可以是普通函数，也可以是函数对象。

  由于 binary_search() 底层实现采用的是二分查找的方式(关于二分查找可以查阅本人写的数据结构专栏----查找这一节)，因此该函数仅适用于“已排好序”的序列。所谓“已排好序”，并不是要求 [first, last) 区域内的数据严格按照某个排序规则进行升序或降序排序，只要满足“所有令 element   该函数会返回一个 bool 类型值，如果 binary_search() 函数在 [first, last) 区域内成功找到和 val 相等的元素，则返回 true；反之则返回 false。

  
  关于binary_search案例如下：

//==================8、binary_search

//以普通函数的方式定义查找规则
bool mycomp811(int i, int j) { return i > j; }
//以函数对象的形式定义查找规则
class mycomp812 {
public:
	bool operator()(const int& i, const int& j) {
		return i > j;
	}
};
int main() {
	int a[9] = { 10, 11, 12, 13, 14, 15,16, 17, 18 };
	//从 a 数组中查找元素 15
	bool haselem1 = binary_search(a, a + 10, 15);
	cout << "haselem1：" << haselem1 << endl;
	if (haselem1 == 1)
		cout << "Find the number，is True!"<<endl;
	else
		cout << "Not find the number，is False!" << endl;


	//从 a 数组中查找元素 20
	bool haselem2 = binary_search(a, a + 10, 20);
	cout << "haselem2：" << haselem2 << endl;

	if (haselem2 == 1)
		cout << "Find the number，is True!" << endl;
	else
		cout << "Not find the number，is False!" << endl;

	cout << "==================================" << endl;

	vector<int>myvector{ 14,15,13,8,9 };
	//从 myvector 容器查找元素 3
	bool haselem3 = binary_search(myvector.begin(), myvector.end(), 13, mycomp812());
	cout << "haselem2：" << haselem3;

	if (haselem3 == 1)
		cout << "Find the number，is True!" << endl;
	else
		cout << "Not find the number，is False!" << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

  该代码演示了binary_search() 函数的 2 种适用场景，其中 a[9] 数组中存储的为升序序列；
  而 myvector 容器中存储的序列虽然整体是乱序的，但对于目标元素 13 来说，所有符合 mycomp812(element, 13) 规则的元素都位于其左侧，不符合的元素都位于其右侧，因此 binary_search() 函数仍可正常执行。

  
  (2)lower_bound

  lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素，该函数在指定范围内查找某个目标值时，最终查找到的不一定是和目标值相等的元素，还可能是比目标值大的元素。

  lower_bound() 语法格式有 2 种，分别为：

//在 [first, last) 区域内查找不小于 val 的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
//在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);
1
2
3
4
5
6

  first 和 last 都为正向迭代器，[first, last) 用于指定函数的作用范围；
  val 用于指定目标元素；
  comp 用于自定义比较规则，此参数可以接收一个包含 2 个形参（第二个形参值始终为 val）且返回值为 bool 类型的函数，可以是普通函数，也可以是函数对象。

  此外，该函数还会返回一个正向迭代器，当查找成功时，迭代器指向找到的元素；反之，如果查找失败，迭代器的指向和 last 迭代器相同。
  
  关于binary_search案例如下：

//==================8.1、lower_bound

//以普通函数的方式定义查找规则
bool mycomp821(int i, int j) { return i>j; }

//以函数对象的形式定义查找规则
class mycomp822 {
public:
	bool operator()(const int& i, const int& j) {
		return i>j;
	}
};
int main() {
	int a[5] = { 1,2,3,4,5 };
	//从 a 数组中找到第一个不小于 3 的元素
	int *p = lower_bound(a, a + 5, 3);
	cout << "*p = " << *p << endl;

	vector<int> myvector{ 4,5,3,1,2 };
	//根据 mycomp2 规则，从 myvector 容器中找到第一个违背 mycomp2 规则的元素
	vector<int>::iterator iter = lower_bound(myvector.begin(), myvector.end(), 3, mycomp2());
	cout << "*iter = " << *iter;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

  myvector 容器中存储的元素看似是乱序的，但对于元素 3 来说，大于 3 的所有元素都位于其左侧，小于 3 的所有元素都位于其右侧，且查找规则选用的是 mycomp822()，其查找的就是第一个不大于 3 的元素，因此 lower_bound() 函数是可以成功运行的。

  
  (3)upper_bound

  upper_bound()与lower_bound()刚好相反，用于在指定范围内查找大于目标值的第一个元素。
  upper_bound()函数的语法格式有 2 种，分别是：

//查找[first, last)区域中第一个大于 val 的元素。
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
//查找[first, last)区域中第一个不符合 comp 规则的元素
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);
1
2
3
4
5
6

  各参数要求与上述lower_bound()类似。

  
  关于upper_bound 案例如下：

//==================8.3、upper_bound

//以普通函数的方式定义查找规则
bool mycomp831(int i, int j) { return i > j; }
//以函数对象的形式定义查找规则
class mycomp832 {
public:
	bool operator()(const int& i, const int& j) {
		return i > j;
	}
};
int main() {
	int a[5] = { 1,2,3,4,5 };
	//从 a 数组中找到第一个大于 3 的元素
	int *p = upper_bound(a, a + 5, 3);
	cout << "*p = " << *p << endl;
	vector<int> myvector{ 4,5,3,1,2 };
	//根据 mycomp2 规则，从 myvector 容器中找到第一个违背 mycomp2 规则的元素
	vector<int>::iterator iter = upper_bound(myvector.begin(), myvector.end(), 3, mycomp2());
	cout << "*iter = " << *iter;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

  该代码演示了 upper_bound() 函数的 2 种适用场景，其中 a[5] 数组中存储的为升序序列；
  而 myvector 容器中存储的序列虽然整体是乱序的，但对于目标元素 3 来说，所有符合 mycom832(3, element) 规则的元素都位于其左侧，不符合的元素都位于其右侧，因此 upper_bound() 函数仍可正常执行。

---

3、总结

  最后，长话短说，大家看完就好好动手实践一下，切记不能三分钟热度、三天打鱼，两天晒网。大家也可以自己尝试写写博客，来记录大家平时学习的进度，可以和网上众多学者一起交流、探讨，我也会及时更新，来督促自己学习进度。一开始提及的博主【AI菌】，个人已关注，并订阅了相关专栏(对我有帮助的)，希望大家觉得不错的可以点赞、关注、收藏。