C++ 提高篇 9 之 STL 常用算法二

C++ 自学

• —— 常用排序算法
• • sort 算法
  • random_shuffle 算法
  • merge 算法
  • reverse 算法
• —— 常用拷贝和替换算法
• • copy 算法
  • replace 算法
  • replace_if 算法
  • swap 算法
• —— 常用算术生成算法
• • accumulate 算法
  • fill 算法
• —— 常用集合算法
• • set_intersection 算法
  • set_union 算法
  • set_difference 算法

—— 常用排序算法

算法简介

1. sort // 对容器内元素进行排序
2. random_shuffle // （洗牌）指定范围内的元素随机调整次序
3. merge // 容器元素合并，并存储到另一个容器中
4. reverse // 反转指定范围内的元素

sort 算法

功能描述

对容器内元素进行排序

函数原型

sort(iterator begin, iterator end, _Pred);

如下利用 sort 算法对存放在 vector 容器中的一组数据进行某种排序

#include 
using namespace std;
#include  // 用于创建 vector 容器
#include  // 用于 for_each 和 sort 算法
#include  // 用于 greater() 仿函数

void Print(int value) {
	cout << value << " ";
}

void PrintVector(vector &v) {
	for_each(v.begin(), v.end(), Print);
	cout << endl;
}

void RandomInsert(vector &v) {
	for (int i = 0; i < 5; i++) {
		v.push_back(rand() % 10 + 1); // 1 ~ 10
	}
}

class Dec {
public:
	bool operator()(int value1, int value2) {
		return value1 < value2;
	}
};

int main() {

	// 创建容器数组
	vector v;
	// 随机插入 5 个数据
	RandomInsert(v);
	// 打印容器内元素
	PrintVector(v); // 2 8 5 1 10

	// 1. 对容器 v 进行升序排列
	sort(v.begin(), v.end());
	PrintVector(v); // 1 2 5 8 10

	// 2. 对容器 v 进行降序排列 -- 借助内置仿函数
	sort(v.begin(), v.end(), greater());
	PrintVector(v); // 10 8 5 2 1
	// 自定义仿函数 -- 升序
	sort(v.begin(), v.end(), Dec());
	PrintVector(v); // 1 2 5 8 10

	system("pause");
	return 0;
}

random_shuffle 算法

功能描述

指定范围内元素调整次序（洗牌）

函数原型

random_shuffle(iterator begin, iterator end);

如下利用 random_shuffle 算法打乱存放在 vector 容器中的一组数据

#include 
using namespace std;
#include  // 用于创建 vector 容器
#include  // 用于 for_each 和 random_shuffle 算法
#include  // 用于随机数种子

void Print(int value) {
	cout << value << " ";
}

void PrintVector(vector &v) {
	for_each(v.begin(), v.end(), Print);
	cout << endl;
}

void RandomInsert(vector &v) {
	for (int i = 0; i < 5; i++) {
		v.push_back(rand() % 10 + 1); // 1 ~ 10
	}
}

int main() {

	// 随机数种子
	srand((unsigned int)time(NULL));

	// 创建容器数组
	vector v;
	// 随机插入 5 个数据
	RandomInsert(v);
	// 打印容器内元素
	PrintVector(v); // 9 3 5 3 3

	// 1. 打乱容器内指定范围内的元素
	random_shuffle(v.begin(), v.end());
	PrintVector(v); // 3 5 3 3 9

	system("pause");
	return 0;
}

merge 算法

功能描述

重点：二个容器必须是（同方向）有序的！

容器元素合并，并存储到另一个容器中

函数原型

merge(iterator begin1, iterator end1, iterator begin2, iterator end2, iterator dest_begin);

如下利用 merge 算法将二个有序容器重组成一个新的容器（有序）

#include 
using namespace std;
#include  // 用于创建 vector 容器
#include  // 用于 for_each 和 merge 算法

void Print(int value) {
	cout << value << " ";
}

void PrintVector(vector &v) {
	for_each(v.begin(), v.end(), Print);
	cout << endl;
}

int main() {

	// 创建容器数组
	vector v1;
	vector v2;
	vector dest;

	for (int i = 0; i < 5; i++) {
		v1.push_back(i);
		v2.push_back(i + 3);
	}

	// 打印容器 v1 和 v2 内元素
	PrintVector(v1); // 0 1 2 3 4
	PrintVector(v2); // 3 4 5 6 7

	// 插入二个容器数据前，需要扩容此容器
	dest.resize(v1.size() + v2.size());
	// 将二个容器合并为容器 dest
	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), dest.begin());
	PrintVector(dest); // 0 1 2 3 3 4 4 5 6 7
	
	system("pause");
	return 0;
}

reverse 算法

功能描述

反转指定范围内的元素

函数原型

reverse(iterator begin, iterator end);

如下利用 reverse 算法将容器某区间元素反转

#include 
using namespace std;
#include  // 用于创建 vector 容器
#include  // 用于 for_each 和 reverse 算法

void Print(int value) {
	cout << value << " ";
}

void PrintVector(vector &v) {
	for_each(v.begin(), v.end(), Print);
	cout << endl;
}

int main() {

	// 创建容器数组
	vector v;

	for (int i = 0; i < 5; i++) {
		v.push_back(i);
	}

	// 反转之前
	PrintVector(v); // 0 1 2 3 4
			
	reverse(v.begin(), v.end());
	
	// 反转之后
	PrintVector(v); // 4 3 2 1 0
	
	system("pause");
	return 0;
}

—— 常用拷贝和替换算法

算法简介

1. copy // 容器内指定范围的元素拷贝到另一个容器中
2. replace // 将容器内指定范围的旧元素修改为新元素
3. replace_if // 将容器指定范围内满足条件的旧元素修改为新元素
4. swap // 互换二个容器的元素

copy 算法

功能描述

重点：拷贝之前记得扩容！

容器内指定范围的元素拷贝到另一个容器中

函数原型

copy(iterator begin, iterator end, iterator dest_begin);

如下利用 copy 算法将容器内元素拷贝到另一个容器中

#include 
using namespace std;
#include  // 用于创建 vector 容器
#include  // 用于 for_each 和 copy 算法

void Print(int value) {
	cout << value << " ";
}

void PrintVector(vector &v) {
	for_each(v.begin(), v.end(), Print);
	cout << endl;
}

int main() {

	// 创建容器数组
	vector v;
	vector dest;

	for (int i = 0; i < 5; i++) {
		v.push_back(i);
	}

	// 利用 copy 算法将容器 v 的元素拷贝到 dest 中
	dest.resize(v.size());
	copy(v.begin(), v.end(), dest.begin());
	PrintVector(dest); // PrintVector

	system("pause");
	return 0;
}

replace 算法

功能描述

将容器内指定范围的旧元素修改为新元素

函数原型

replace(iterator begin, iterator end, oldvalue, newvalue);

利用 replace 算法将容器内指定范围的旧元素修改为新元素

#include 
using namespace std;
#include  // 用于创建 vector 容器
#include  // 用于 for_each 和 replace 算法

void Print(int value) {
	cout << value << " ";
}

void PrintVector(vector &v) {
	for_each(v.begin(), v.end(), Print);
	cout << endl;
}

int main() {

	vector v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	PrintVector(v); // 1 1 1 2 3

	// 若我们想将容器 v 中的元素 1 全替换成元素 100，则需要借助算法 replace
	// 第一（二）个参数分别代表迭代器指向的起始（结束）位置
	// 第三个参数代表需要替换的旧元素，第四个参数代表取代旧元素的新元素
	replace(v.begin(), v.end(), 1, 100);
	PrintVector(v); // 100 100 100 2 3

	system("pause");
	return 0;
}

replace_if 算法

功能描述

将容器指定范围内满足条件的旧元素修改为新元素

函数原型

replace_if(iterator begin, iterator end, _Pred, newvalue);

利用算法 replace_if 将容器指定范围内满足条件的旧元素修改为新元素

#include 
using namespace std;
#include  // 用于创建 vector 容器
#include  // 用于 for_each 和 replace_if 算法

void Print(int value) {
	cout << value << " ";
}

void PrintVector(vector &v) {
	for_each(v.begin(), v.end(), Print);
	cout << endl;
}

class GreaterOne {
public:
	bool operator()(int value) {
		return value > 1;
	}
};

int main() {

	vector v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	PrintVector(v); // 1 1 1 2 3

	// 若我们想将容器 v 中大于 1 的所有元素全替换成元素 200，则需要借助算法 replace_if
	// 第一（二）个参数分别代表迭代器指向的起始（结束）位置
	// 第三个参数代表谓词（仿函数 -- bool），第四个参数代表取代旧元素的新元素
	replace_if(v.begin(), v.end(), GreaterOne(), 200);
	PrintVector(v); // 1 1 1 200 200

	system("pause");
	return 0;
}

swap 算法

功能描述

互换二个容器的元素

函数原型

swap(container v1, container v2);

利用算法 swap 互换二个容器的元素

#include 
using namespace std;
#include  // 用于创建 vector 容器
#include  // 用于 for_each 和 swap 算法

void Print(int value) {
	cout << value << " ";
}

void PrintVector(vector &v) {
	for_each(v.begin(), v.end(), Print);
	cout << endl;
}

int main() {

	vector v;
	vector v1;
	for (int i = 0; i < 5; i++) {
		v.push_back(i + 1);
		v1.push_back(10 - i);
	}
	PrintVector(v); // 1 2 3 4 5
	PrintVector(v1); // 10 9 8 7 6

	// 若我们想将容器 v 和 v1 内的元素替换，那么我们可以借助算法 swap
	// 二个参数都代表容器，替换之后，容器内元素互换
	swap(v, v1);
	PrintVector(v); // 10 9 8 7 6
	PrintVector(v1); // 1 2 3 4 5
	
	system("pause");
	return 0;
}

—— 常用算术生成算法

注意

算术生成属于小型算法，使用时包含头文件

算法简介

1. accumulate // 计算容器内元素总和
2. fill // 向容器中添加元素

accumulate 算法

功能描述

计算区间内容器元素累积总和

函数原型

accumulate(iterator begin, iterator end, value);

利用算法 accumulate 计算容器内元素累积总和

#include 
using namespace std;
#include  // 用于创建 vector 容器
#include  // 用于 accumulate 算法

int main() {

	vector v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}

	// 如果我们想计算容器内所有元素的总和，那么我们可以借助算法 accumulate 
	// 前二个参数分别代表迭代器指向的起始（结束）位置
	// 后一个参数代表累积总和的基础上加上的值
	int total = accumulate(v.begin(), v.end(), 0);
	cout << total << endl; // 45

	total = accumulate(v.begin(), v.end(), 100);
	cout << total << endl; // 145

	system("pause");
	return 0;
}

fill 算法

功能描述

向容器中填充指定的元素

函数原型

fill(iterator begin, iterator end, value);

利用算法 fill 向容器中填充指定的元素

#include 
using namespace std;
#include  // 用于创建 vector 容器
#include  // 用于 for_each 算法
#include  // 用于 fill 算法

void Print(int value) {
	cout << value << " ";
}

void PrintVector(vector &v) {
	for_each(v.begin(), v.end(), Print);
	cout << endl;
}

int main() {

	vector v;
	for (int i = 0; i < 5; i++) {
		v.push_back(i);
	}
	PrintVector(v); // 0 1 2 3 4

	// 向容器 v 中填充元素 -- 会覆盖原有数据
	fill(v.begin(), v.end(), 100);
	PrintVector(v); // 100 100 100 100 100

	system("pause");
	return 0;
}

—— 常用集合算法

算法简介

1. set_intersection // 求二个容器的交集
2. set_union // 求二个容器的并集
3. set_difference // 求二个容器的差集

set_intersection 算法

功能描述

重点：目标容器需要提前开辟空间！空间大小不细致讲解

求二个容器的交集

函数原型

set_intersection(iterator begin1, iterator end1, iterator begin2, iterator end2, iterator dest_begin);

利用算法 set_intersection 求二个容器的交集

#include 
using namespace std;
#include  // 用于创建 vector 容器
#include  // 用于 for_each 和 min 和 set_intersection 算法

void Print(int value) {
	cout << value << " ";
}

void PrintVector(vector &v) {
	for_each(v.begin(), v.end(), Print);
	cout << endl;
}

int main() {

	vector v;
	vector v1;
	vector dest;
	for (int i = 0; i < 5; i++) {
		v.push_back(i);
		v1.push_back(i + 3);
	}
	PrintVector(v); // 0 1 2 3 4
	PrintVector(v1); // 3 4 5 6 7

	// 若我们想求容器 v 和 v1 的交集并把得到的结果存在另一个目标容器，那么可以借助算法 set_intersection
	// 前面四个参数分别是二个容器的起始（结束）迭代器，后面一个参数是目标迭代器的起始位置
	dest.resize(min(v.size(), v1.size()));
	vector::iterator End = set_intersection(v.begin(), v.end(), v1.begin(), v1.end(), dest.begin());
	for (vector::iterator pos = dest.begin(); pos != End; pos++) {
		cout << *pos << " "; // 3 4
	}
	cout << endl; 

	system("pause");
	return 0;
}

set_union 算法

功能描述

重点：目标容器需要提前开辟空间！空间大小不细致讲解

求二个容器的并集

函数原型

set_union(iterator begin1, iterator end1, iterator begin2, iterator end2, iterator dest_begin);

利用算法 set_union 求二个容器的并集

#include 
using namespace std;
#include  // 用于创建 vector 容器
#include  // 用于 for_each 和 set_union 算法

void Print(int value) {
	cout << value << " ";
}

void PrintVector(vector &v) {
	for_each(v.begin(), v.end(), Print);
	cout << endl;
}

int main() {

	vector v;
	vector v1;
	vector dest;
	for (int i = 0; i < 5; i++) {
		v.push_back(i);
		v1.push_back(i + 3);
	}
	PrintVector(v); // 0 1 2 3 4
	PrintVector(v1); // 3 4 5 6 7

	// 若我们想求容器 v 和 v1 的并集并把得到的结果存在另一个目标容器，那么可以借助算法 set_union
	// 前面四个参数分别是二个容器的起始（结束）迭代器，后面一个参数是目标迭代器的起始位置
	dest.resize(v.size() + v1.size());
	vector::iterator End = set_union(v.begin(), v.end(), v1.begin(), v1.end(), dest.begin());
	for (vector::iterator pos = dest.begin(); pos != End; pos++) {
		cout << *pos << " "; // 0 1 2 3 4 5 6 7
	}
	cout << endl; 

	system("pause");
	return 0;
}

set_difference 算法

功能描述

重点：目标容器需要提前开辟空间！空间大小不细致讲解

求二个容器的差集

函数原型

set_difference(iterator begin1, iterator end1, iterator begin2, iterator end2, iterator dest_begin);

利用算法 set_difference 求二个容器的差集

#include 
using namespace std;
#include  // 用于创建 vector 容器
#include  // 用于 for_each 和 max 和 set_difference 算法

void Print(int value) {
	cout << value << " ";
}

void PrintVector(vector &v) {
	for_each(v.begin(), v.end(), Print);
	cout << endl;
}

int main() {

	vector v;
	vector v1;
	vector dest;
	for (int i = 0; i < 5; i++) {
		v.push_back(i);
		v1.push_back(i + 3);
	}
	PrintVector(v); // 0 1 2 3 4
	PrintVector(v1); // 3 4 5 6 7

	// 1. 若我们想求容器 v 和 v1 的差集并把得到的结果存在另一个目标容器，那么可以借助算法 set_union
	// 前面四个参数分别是二个容器的起始（结束）迭代器，后面一个参数是目标迭代器的起始位置
	dest.resize(max(v.size(), v1.size()));
	vector::iterator End = set_difference(v.begin(), v.end(), v1.begin(), v1.end(), dest.begin());
	for (vector::iterator pos = dest.begin(); pos != End; pos++) {
		cout << *pos << " "; // 0 1 2
	}
	cout << endl; 

	// 2. 若我们想求容器 v1 和 v 的差集并把得到的结果存在另一个目标容器，同理可以借助算法 set_union
	End = set_difference(v1.begin(), v1.end(), v.begin(), v.end(), dest.begin());
	for (vector::iterator pos = dest.begin(); pos != End; pos++) {
		cout << *pos << " "; // 5 6 7
	}
	cout << endl;

	system("pause");
	return 0;
}