C++：STL：常用算法：遍历，查找，排序算法

FishAnd_Yu

已于 2023-01-04 12:09:46 修改

阅读量653

点赞数 1

分类专栏： # C++精华文章标签：算法 C++ 常见算法

于 2022-12-29 15:07:43 首次发布

本文链接： https://blog.csdn.net/u013620306/article/details/128470578

版权

C++精华专栏收录该内容

50 篇文章 20 订阅

订阅专栏

概述：

算法主要是由头文件 <algorithm>，<functional>, <numeric> 组成。
<algorithm> 是所有STL头文件中最大的一个，范围涉及到：比较，交换，查找，遍历，复制，修改等操作
<numeric> 体积最小，只包括几个在序列上进行简单数学运算的模板函数
<functional> 定义了一些模板类，用以声明函数对象

一：常用的遍历算法

学习目标：掌握常用的遍历算法

算法简介：

for_each // 遍历容器

transform // 搬运容器到另一个容器中

1.1： for_each

功能描述：实现遍历容器

函数原型：for_each(iterator beg, iterator end, _func)

遍历算法：遍历容器元素

beg: // 开始迭代器

end : // 结束迭代器

_func // 普通函数或者函数对象（仿函数）

源码分析

案例：使用 for_each 并指定函数对象，来完成遍历元素的操作

/**
	STL : 常见算法
*/
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#define NUM 10
using namespace std;

void print01(int val) {
	cout << val << " ";
}

// 仿函数
class Printo2
{
public:
	void operator()(int val) {
		cout << val << "  ";
	}
};

void test() {
	vector<int> v;
	for (int i = 0; i < NUM; i++)
	{
		v.push_back(i);
	}
	// 普通函数作为模板，只需要传入函数名即可。
	for_each(v.begin(), v.end(), print01);
	cout << endl;
	// 函数对象作为模板
	for_each(v.begin(), v.end(), Printo2());
}

int main() {
	test();
}

1.2：transform

功能描述：搬运容器到另一个容器中

函数原型：transform(iteratot beg1, iterator end1, iterator beg2, _func)

beg1: 源容器开始迭代器

end1: 源容器结束迭代器

beg2: 目标容器开始迭代器

_func: 函数或者函数对象，在搬运过程中对数据做的操作

案例：测试 transform的功能。

// 普通函数，将元素搬运过去并加100,之后这个函数将作为 搬运函数的_func
int transform(int val) {
	return val + 100;
}

// 仿函数
class print02 {
public:
	void operator()(int val) {
		cout << val << " ";
	}
};

void test1() {
	vector<int> v;
	for (int i = 0; i < NUM; i++)
	{
		v.push_back(i);
	}

	for_each(v.begin(), v.end(), print02());
	cout << endl;

	vector<int> v2;
	v2.resize(v.size());  // 目标容器必须先开辟空间
	transform(v.begin(), v.end(), v2.begin(), transform);
	for_each(v2.begin(), v2.end(), print02());
	cout << endl;
}

二：常用查找算法

学习目标：掌握常用的查找算法。

算法简介：

find // 查找元素

find_if // 按条件查找元素

adjacent_find // 查找相邻重复元素

binary_search // 二分查找法

count // 统计元素个数

count_if // 按条件统计元素个数

2.1：find算法

功能描述：查找指定元素，找到了就返回指定元素的迭代器，找不到就返回结束迭代器

函数原型：find(iterator beg, iterator end ,value);

按值查找元素，找到了就返回指定位置的迭代器，找不到就返回结束迭代器

beg : 开始迭代器

end: 结束迭代器

value : 查找元素

源码分析

案例：使用 find 查找内置数据

// 常用的查找算法
void test_find() {
	vector<int> v;
	for (int i = 0; i < NUM; i++)
	{
		v.push_back(i);
	}
	vector<int>::iterator it = find(v.begin(), v.end(), 6);
	if (it != v.end())
	{
		cout << "找到了元素";
	}
	else
	{
		cout << "没有找到元素" << endl;
	}
}


// 打印结果
找到了元素

案例：使用find 查找自定义数据类型

自定义数据类型，一定要重载 ==运算法，否则就会出错，这是因为 find源码中直接将迭代器解引用后的数据与需要查找的数据对比，而 Person是自定义数据类型，无法直接对比，所以需要重载 Person== 运算符。

class Person
{
public:
	Person(string name, int age) {
		this->m_Age = age;
		this->m_Name = name;
	}

	// 重载等号运算符,一元谓词
	bool operator==(const Person& p) {
		if (this->m_Name.compare(p.m_Name) == 0 && this->m_Age == p.m_Age) {
			return true;
		}
		return false;
	}

	int m_Age;
	string m_Name;

private:

};

void test2() {
	Person p1("张飞", 18);
	Person p2("关关羽", 30);
	Person p3("刘备", 48);

	vector<Person> v;
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);

	//根据 find源码：第三个形参为具体类型
	vector<Person>::iterator it = find(v.begin(), v.end(), p2);
	if (it == v.end())
	{
		cout << "没有找到" << endl;
	}
	else
	{
		cout << "找到了 姓名：" << it->m_Name << "  年龄： " << it->m_Age << endl;
	}

}

2.2： find_if

功能描述：按条件查找元素

函数原型： find_if (iterator beg, iterator end , _pred)

按值查找元素，找到了就返回指定位置的迭代器，找不到就返回结束位置迭代器

beg : 开始迭代器

end: 结束迭代器

_pred : 函数或者谓词（返回bool 类型的仿函数）

源码

案例：测试内置数据类型和自定义数据类型的 find_if 功能

// 测试自定义数据类型，查找大于4的数据
class Greater4
{
public:
	bool operator()(int val) {
		return val > 4;
	}
};

// 测试自定义数据类型，查找年龄大于20的数据
class Greater20 {
public:
	bool operator()(Person& p) {
		return p.m_Age > 20;
	}
};

void test_find_if() {
	vector<int> v1;
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(2);
	v1.push_back(1);
	vector<int>::iterator it = find_if(v1.begin(), v1.end(), Greater4());
	if (it == v1.end())
	{
		cout << "没有找到" << endl;
	}
	else {
		cout << "找到了元素" << endl;
	}

	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 40);
	Person p4("dd", 15);

	vector<Person> v;
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	vector<Person>::iterator it2 = find_if(v.begin(), v.end(), Greater20());
	if (it2 == v.end())
	{
		cout << "没有找到" << endl;
	}
	else
	{
		cout << "找到了姓名：" << it2->m_Name << "  年龄： " << it2->m_Age << endl;
	}
}

2.3：adjacent_find

功能描述：查找相邻重复元素

函数原型：adjacent_find(iterator beg, iterator end)

查找相邻重复元素，返回相邻元素的第一个位置迭代器

beg: 开始迭代器

end : 结束迭代器

源码

2.4：binary_search

功能描述：查找指定元素是否存在

函数原型：bool binary_search(iterator beg, iterator end, value)

查找指定元素，找到返回 true, 否则 false

beg: 开始迭代器

end : 结束迭代器

value : 查找的元素

源码

void test_binary_serach() {
	vector<int> v;
	for (int i = 0; i < NUM; i++)
	{
		v.push_back(i);
	}
	bool ret = binary_search(v.begin(), v.end(), 2);
	if (ret == 0)   // 0 false  1 ture
	{
		cout << "没有找到元素" << endl;
	}
	else
	{
		cout << "找到元素了: " << "2" << endl;
	}
}

2.5：count

功能描述：统计元素个数

函数原型：count(iterator beg, iterator end , value)

统计元素出现次数

beg : 开始迭代器

end : 结束迭代器

value : 统计的元素

源码

案例：对内置数据类和自定义数据类型测试 count功能；

class Person222
{
public:
	Person222(string name, int age) {
		this->m_Age = age;
		this->m_Name = name;
	}

	// 重载等号运算符,一元谓词
	bool operator==(const Person222& p) {
		if (this->m_Age == p.m_Age) {
			return true;
		}
		return false;
	}

	int m_Age;
	string m_Name;
};


void test_count() {
	vector<int> v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(2);
	v.push_back(1);

	int num = count(v.begin(), v.end(), 1);
	cout << "1的个数为：" << num << endl;

	// 自定义数据类型

	vector<Person222> v1;
	Person222 p1("刘备", 45);
	Person222 p2("关羽", 45);
	Person222 p3("赵云", 20);
	Person222 p4("张飞", 30);
	v1.push_back(p1);
	v1.push_back(p2);
	v1.push_back(p3);
	v1.push_back(p4);

	Person222 p("诸葛亮", 45);
	int num1 = count(v1.begin(), v1.end(), p);
	cout << "和诸葛亮同年龄：" << num1 << endl;
}

2.6：count_if

功能描述：按条件统计元素个数

函数原型： count_if(iterator beg, iterator end, _Pred)

按条件统计元素出现次数

beg: 开始迭代器

end : 结束迭代器

_Pred ：谓词

源码

class Greater10 {
public:

	bool operator()(int val) {
		return val > 10;
	}

private:
};

class AgeLess35
{
public:
	bool operator()(const Person& p) {
		return p.m_Age < 35;
	}

private:

};

void test_count_if() {
	vector<int> v;
	v.push_back(8);
	v.push_back(10);
	v.push_back(20);
	v.push_back(9);
	
	int num = count_if(v.begin(), v.end(), Greater10());
	cout << "大于10的个数：" << num << endl;

	vector<Person222> v1;
	Person222 p1("刘备", 35);
	Person222 p2("张飞", 35);
	Person222 p2("赵云", 30);
	v1.push_back(p1);
	v1.push_back(p2);
	int num1 = count_if(v1.begin(), v1.end(), AgeLess35());
	cout << "小于35岁的人数：" << num1 << endl;

}

三：常见排序算法

3.1 sort算法

功能描述：对容器内元素进行排序

函数原型：sotr(iterator beg, iterator end, _Pred)

按值查找元素，找到返回指定位置的迭代器，找不到返回结束位置迭代器

beg: 开始迭代器

end : 结束迭代器

_Pred ：谓词

源码

// 排序算法
void myPrint(int val) {
	cout << val << " ";
}

void test_sort() {
	vector<int> v;
	v.push_back(20);
	v.push_back(80);
	v.push_back(40);
	v.push_back(30);

	// sort默认从小到排序
	sort(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;

	// 从大到小
	sort(v.begin(), v.end(), greater<int>());
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;
}

int main() {
	test_sort();
}

3.2： random_shuffle

功能描述：洗牌，指定范围内的元素随机调整次序

函数原型： random_shuffle(iterator beg, iterator end)

指定范围内的元素调整次序

beg: 开始迭代器

end : 结束迭代器

class myPrint222
{
public:
	void operator()(int val) {
		cout << val << "  ";
	}
};

void test_random() {
	// 添加一个随机种子，每次都能产生不同的随机值
	// srand((unsigned int)time(NULL));
	vector<int> V;
	for (int i = 0; i < NUM; i++)
	{
		V.push_back(i);
	}
	for_each(V.begin(), V.end(), myPrint222());
	cout << endl;

	random_shuffle(V.begin(), V.end());
	for_each(V.begin(), V.end(), myPrint222());
}

int main() {
	test_random();
}

3.3 merge

功能描述：两个容器元素合并，并存储到另一个容器中

函数原型： merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)

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

beg1: 容器1开始迭代器

beg2: 容器2开始的迭代器

end1：容器1结束迭代器

end2：容器2结束迭代器

dest: 目标容器开始迭代器

void test_merge() {
	vector<int> v1;
	vector<int> V2;
	for (int i = 0; i < NUM; i++)
	{
		v1.push_back(i);
		V2.push_back(i);
	}
	// 目标容器
	vector<int> vTarget;
	// 目标容器开辟空间
	vTarget.resize(v1.size() + V2.size());
	// 合并
	merge(v1.begin(), v1.end(), V2.begin(), V2.end(), vTarget.begin());
	for_each(vTarget.begin(), vTarget.end(),myPrint222());
}

3.4： reverse

功能描述：将容器内元素进行反转

函数原型：reverse(iterator beg, iterator end)

反转指定范围内元素

beg: 开始迭代器

end: 结束迭代器

案例：测试reverse功能

void test_reverse() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(50);
	cout << "反转前: " << endl;
	for_each(v.begin(), v.end(), myPrint222());

	cout << "反转后： " << endl;
	reverse(v.begin(),v.end());
	for_each(v.begin(), v.end(), myPrint222());
	cout << endl;
}