当前位置： 首页 > news >正文

【stl -- 常用算法】

news 来源：原创 2023/12/8 20:24:46

目录：

  • 前言
  • 一、遍历算法
    • for_each、transform
  • 二、查找、统计算法
    • find、find_if
    • adjacent_find
    • binary_search
    • count、count_if
  • 三、排序算法
    • sort
    • random_shuffle
    • merge
    • reverse
  • 拷贝、替换算法
    • copy
    • replace、replace_if
    • swap
  • 算数生成算法
    • accumulate
    • fill
  • 集合算法
    • set_intersection
    • set_union
    • set_difference

前言

打怪升级：第19天
在这里插入图片描述

在学习这些算法是我们需要了解一些头文件：< algorithm > 、< numeric > 和 < functional >
< algorithm > 是stl头文件中最大的一个，包含下方介绍的绝大多数算法。
< numeric > 体积很小，只包含几个在序列上进行简单数学运算的模板函数。
< functional >定义了一些模板类、用以声明函数对象。

一、遍历算法

在这里插入图片描述

for_each、transform

这里是引用

class Form
{
public:
	int operator()(int& v)
	{
		return v + 1000; //  这里我们可以进行各种操作
	}
}; 

void Print(int v)
{
	cout << v << ' ';
}

void test04()
{
	vector<int>v1;
	for (int i = 0; i < 8; ++i)
	{
		v1.push_back(i);
	}
	vector<int>v2;
	v2.resize(v1.size());   //  改变大小，空位默认用 0 填充
	// v2.reserve(v1.size());   reserve是预开辟空间，但是实际大小还是0，
	// 而我们使用transform时需要有足够的空间来存放搬运过来的数据， 因此这里不可以使用 

	transform(v1.begin(), v1.end(), v2.begin(), Form());  //  Form()  为仿函数、也可以直接使用函数
	for_each(v1.begin(), v1.end(), Print);  //  Print   为函数指针、也可以使用仿函数
	cout << endl;
	for_each(v2.begin(), v2.end(), Print);
	cout << endl;
}

运行实例：
在这里插入图片描述

二、查找、统计算法

在这里插入图片描述

find、find_if

在这里插入图片描述

class Greater
{
public:
	bool operator()(int val)  // 谓词就是用来做判断的
	{
		return val > 650;
	}
};

void Print(int val)
{
	cout << val << ' ';
}

void test05()
{
	vector<int>v;
	for (int i = 0; i < 10; ++i)
	{
		v.push_back(rand() % 100 + 600);
	}
	for_each(v.begin(), v.end(), Print);
	cout << endl;

	vector<int>::iterator it = find(v.begin(), v.end(), 600);  // 查找数字600
	if (it != v.end())
	{
		cout << *it << endl;
	}
	else
	{
		cout << "did not find" << endl;
	}

	it = find_if(v.begin(), v.end(), Greater()); //  查找有没有大于650的数字
	if (it != v.end())
	{
		cout << *it << endl;
	}
	else
	{
		cout << "did not find" << endl;
	}

}

运行实例：
在这里插入图片描述

find -> 自定义数据类型 – 示例：

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

	bool operator==(Person p)  // 重载==，告诉编译器查找的规则
	{
		if (this->name == p.name && this->age == p.age)
			return true;
		else
			return false;
	}
	string name;
	int age;
};

void test06()
{
	vector<Person>v1;
	Person p1("小米粒", 20);
	v1.push_back(p1);
	Person p2("陈暖树", 20);
	v1.push_back(p2);
	Person p3("裴钱", 22);
	v1.push_back(p3);
	Person p4("李宝瓶", 24);
	v1.push_back(p4);
	Person p5("李宝瓶", 24);

	vector<Person>::iterator it = find(v1.begin(), v1.end(), p5);
	if (it != v1.end())
	{
		cout << "name->" << it->name << " age->" << it->age << endl;
	}
	else
	{
		cout << "did not find" << endl;
	}
}

运行实例：
在这里插入图片描述

adjacent_find

在这里插入图片描述

void PrintVector(int val)
{
	cout << val << ' ';
}

void test01()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; ++i)
	{
		v1.push_back(i);
		v2.push_back(rand() % 3);
	}

	cout << "v1: ";
	for_each(v1.begin(), v1.end(), PrintVector);
	cout << endl;
	cout << "v2: ";
	for_each(v2.begin(), v2.end(), PrintVector);
	cout << endl;

	//  查找连续相同的第一组数据
	vector<int>::iterator vit = adjacent_find(v1.begin(), v1.end()); // 查v1容器
	if (vit != v1.end())
	{
		cout << "adjacent data is : " << *vit << endl;
	}
	else
	{
		cout << "did not find" << endl;
	}
	vit = adjacent_find(v2.begin(), v2.end());  // 查v2容器
	if (vit != v2.end())
	{
		cout << "adjacent data is : " << *vit << endl;
	}
	else
	{
		cout << "did not find" << endl;
	}
}

示例：在这里插入图片描述

binary_search

在这里插入图片描述

void Print(int val)
{
	cout << val << ' ';
}

void test02()
{
	vector<int>v1;
	set<int>s1;
	for (int i = 0; i < 10; ++i)
	{
		v1.push_back(rand() % 100);
		s1.insert(rand() % 100);
	}

	//  binary_search 必须在有序容器中进行查找
	sort(v1.begin(), v1.end(), greater<int>()); // 排降序
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;
	for_each(s1.begin(), s1.end(), Print);
	cout << endl;

	bool target = binary_search(v1.begin(), v1.end(), 30);
	if (target)
	{
		cout << "30存在" << endl;
	}
	else
	{
		cout << "30不存在" << endl;
	}
	target = binary_search(s1.begin(), s1.end(), 30);
	if (target)
	{
		cout << "30存在" << endl;
	}
	else
	{
		cout << "30不存在" << endl;
	}
}

示例：在这里插入图片描述

count、count_if

在这里插入图片描述
count 示例：

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

	bool operator==(const Person& p)
	{
		return this->m_name == p.m_name && this->m_age == p.m_age;
	}

	string m_name;
	int m_age;
};

void test01()
{
	vector<int>v1;
	for (int i = 0; i < 100; ++i)  //  100 个 0~9之间的数字
	{
		v1.push_back(rand() % 10);
	}
	
	/* bool found = binary_search(v1.begin(), v1.end(), 5); // 二分查找 只适用于 有序序列
	if (found)
	{
		cout << "find it" << endl;
	}
	else
	{
		cout << "did not find" << endl;
	}*/

	cout << "9 is count->" << count(v1.begin(), v1.end(), 9) << endl;  //  统计 9 的个数

	vector<Person>v2;
	Person p1("aaa", 19);
	v2.push_back(p1);
	Person p2("bbb", 12);
	v2.push_back(p2);
	Person p3("ccc", 14);
	v2.push_back(p3);
	Person p4("ddd", 16);
	v2.push_back(p4);
	Person p5("ccc", 14);
	v2.push_back(p5);

	Person tmp("ccc", 14);

	int found = count(v2.begin(), v2.end(), tmp); //对于自定义类型，需要重载== ，来告诉编译器相等的条件
	cout << "count elements thit match val-> " << found << endl;

}

运行实例：
在这里插入图片描述

三、排序算法

在这里插入图片描述

sort

顺序：默认排升序，使用非常广泛。在这里插入图片描述

void Print(int v)
{
	cout << v << ' ';
}

void test03()
{
	vector<int>v1;
	for (int i = 0; i < 10; ++i)
	{
		v1.push_back(rand() % 100);
	}

	cout << "初始数据：";
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;

	cout << "升序排列：";
	sort(v1.begin(), v1.end());
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;

	cout << "降序排列：";
	sort(v1.begin(), v1.end(), greater<int>());  //  此处使用内建函数对象
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;
}

运行实例：
在这里插入图片描述

random_shuffle

洗牌：对区间内数据进行重新排列；
使用场景：抽签、随机取号等。
在这里插入图片描述

void Init(vector<int>&v, int val)
{
	for (int i = 0; i < 10; ++i)
	{
		v.push_back(i + val);
	}
}

void Print(int v)
{
	cout << v << ' ';
}

void test02()
{
	srand((unsigned int)time(NULL));
	
	vector<int>v1;
	Init(v1, 10);
	
	cout << "random_shuffle: ";
	random_shuffle(v1.begin(), v1.end());   //  洗牌1
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;
	
	cout << "random_shuffle: ";
	random_shuffle(v1.begin(), v1.end());   //  洗牌2
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;
	
	cout << "random_shuffle: ";
	random_shuffle(v1.begin(), v1.end());   //  洗牌3
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;
}

运行实例：
在这里插入图片描述

merge

合并：将两个有序容器中的数据进行合并，并把合并后的数据放到目标容器中，
这里需要注意：目标容器需要提前开辟好足够的空间。
在这里插入图片描述

void Print(int v)
{
	cout << v << ' ';
}

void test04()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 8; ++i)
	{
		v1.push_back(i);
		v2.push_back(i + 5);
	}
	cout << "v1-> ";
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;
	cout << "v2-> ";
	for_each(v2.begin(), v2.end(), Print);
	cout << endl;

	vector<int>vtarget; // 目标容器
	vtarget.resize(v1.size() + v2.size());
	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vtarget.begin());
	cout << "vtarget-> ";
	for_each(vtarget.begin(), vtarget.end(), Print);
	cout << endl;
}

运行实例：
在这里插入图片描述

reverse

反转：reverse，将容器内的数据进行反转。
在这里插入图片描述

void Print(int val)
{
	cout << val << ' ';
}

void test03()
{
	vector<int>v1;
	for (int i = 0; i < 10; ++i)
	{
		v1.push_back(rand() % 10);
	}
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;

	cout << "反转: ";
	reverse(v1.begin(), v1.end());
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;

	cout << "排序: ";
	sort(v1.begin(), v1.end());
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;

	cout << "反转: ";
	reverse(v1.begin(), v1.end());  // 对有序数据进行反转，相当于排反序
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;
}

运行实例：在这里插入图片描述

拷贝、替换算法

在这里插入图片描述

copy

示例：

void Print(int v)
{
	cout << v << ' ';
}

//  拷贝和替换函数
void test08()
{
	// copy
	vector<int>v1;
	for (int i = 0; i < 10; ++i)
	{
		v1.push_back(i);
	}

	//vector<int>v2;
	//v2.resize(v1.size());  //  不要忘记分配大小
	 将v1容器完全拷贝到v2，其实如果只是这样的操作，不如直接使用拷贝构造或者赋值operator=
	//copy(v1.begin(), v1.end(), v2.begin());
	// vector<int>v2(v1);  或者   v2 = v1;
	

	 //  copy更常用的是：将一个容器到一部分内容进行拷贝

	cout << "v1: ";
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;
	//  将v1的前半部分数据拷贝到v2
	vector<int>v2;
	v2.resize(v1.size() / 2);
	copy(v1.begin(), v1.end() - v1.size() / 2, v2.begin());
	cout << "v2: ";
	for_each(v2.begin(), v2.end(), Print);
	cout << endl;

}

运行实例：
在这里插入图片描述

replace、replace_if

在这里插入图片描述

void Print(int val)
{
	cout << val << ' ';
}
// 拷贝和替换算法
// replace
// replace_if

bool GreaterTow(int val)
{
	return val > 2;
}

void test01()
{
	vector<int>v1;
	for (int i = 0; i < 10; ++i)
	{
		v1.push_back(rand() % 5);
	}
	vector<int>v2(v1);
	cout << "替换前：";
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;
	
	cout << "替换后：";
	replace(v1.begin(), v1.end(), 0, 1000);  //  将 0 全部替换成 1000
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;

	cout << "按条件替换：";
	replace_if(v2.begin(), v2.end(), GreaterTow, 2);  // 将 大于 2 的全部替换成 2
	for_each(v2.begin(), v2.end(), Print);
	cout << endl;
}

运行实例：
在这里插入图片描述

swap

在这里插入图片描述

bool GreaterTow(int val)
{
	return val > 2;
}

void test02()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; ++i)
	{
		v1.push_back(i);
	}
	for (int i = 0; i < 6; ++i)
	{
		v2.push_back(i + 100);
	}

	cout << "交换前：" << endl;
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;
	for_each(v2.begin(), v2.end(), Print);
	cout << endl;
	cout << "v1: " << v1.size() << ' ' << v1.capacity() << endl;
	cout << "v2: " << v2.size() << ' ' << v2.capacity() << endl;

	cout << "交换后：" << endl;
	swap(v1, v2);  //  直接传两个容器
	               //  vector中也内置了swap函数模板，因此也可以写成： v1.swap(v2);
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;
	for_each(v2.begin(), v2.end(), Print);
	cout << endl;
	cout << "v1: " << v1.size() << ' ' << v1.capacity() << endl;
	cout << "v2: " << v2.size() << ' ' << v2.capacity() << endl;
}

运行实例：
在这里插入图片描述

算数生成算法

在这里插入图片描述

accumulate

在这里插入图片描述

void test03()
{
	//  accumulate  -- 求和
	vector<int>v1;
	for (int i = 0; i <= 100; ++i)
	{
		v1.push_back(i);
	}
	//											0 为初始累加值
	int total = accumulate(v1.begin(), v1.end(), 0);
	cout <<  total << endl;

	

int cnt = accumulate(v1.begin(), v1.end(), 1000);
	cout << cnt << endl;

}

运行实例：
在这里插入图片描述

fill

在这里插入图片描述

void Print(int val)
{
	cout << val << ' ';
}

void test05()
{
	// fill  -- 填充
	// 对于填充区间，我们既可以在使用 resize 扩大空间的同时设置填充数据，也可以后期使用 fill 更改填充数据

	vector<int>v1;
	cout << "申请空间，并初始化为100" << endl;
	v1.resize(10, 100); //  第二个参数默认为0，此时我们改为100
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;

	cout << "将后半部分的数值改为520" << endl;
	fill(v1.begin() + v1.size() / 2, v1.end(), 520);
	for_each(v1.begin(), v1.end(), Print);
	cout << endl;
}

运行实例：
在这里插入图片描述

集合算法

集合算法的 ‘集合’ 指的是两个容器里的数据需要是有序的，并非限制只有set容器的数据才可以使用。
注意：交集和并集：a与b的交集，a与b的交集，因此a与b和b与a结果都是一样的，
但是差集不一样，a相对于b的差集，和b相对于a的差集，可能会得到两个结果，下面我们通过实践来验证。
在这里插入图片描述

set_intersection

在这里插入图片描述

void Print(int val)
{
	cout << val << ' ';
}

void test06()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; ++i)
	{
		v1.push_back(i);         //  0 ~ 9
		v2.push_back(i + 5);     //  5 ~ 14
	}

	vector<int>vTarget;
	vTarget.resize(min(v1.size(), v2.size()));  // 一个集合包含于另一个集合时size最大
	vector<int>::iterator intEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin()); 
	for_each(vTarget.begin(), intEnd, Print);   //  intEnd 不一定等于 end()
	cout << endl;
	for_each(vTarget.begin(), vTarget.end(), Print);
	cout << endl;
}

运行实例：在这里插入图片描述

set_union

在这里插入图片描述

void Print(int val)
{
	cout << val << ' ';
}

void test07()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; ++i)
	{
		v1.push_back(i);         //  0 ~ 9
		v2.push_back(i + 5);     //  5 ~ 14
	}

	vector<int>vTarget;
	vTarget.resize(v1.size() + v2.size());  // 两个集合交集为空时最大
	vector<int>::iterator intEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
	for_each(vTarget.begin(), intEnd, Print);
	cout << endl;
	for_each(vTarget.begin(), vTarget.end(), Print);
	cout << endl;
}

运行实例：
在这里插入图片描述

set_difference

注意：a相对b的差集、b相对于a的差集。
在这里插入图片描述

void Print(int val)
{
	cout << val << ' ';
}

void test08()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; ++i)
	{
		v1.push_back(i);         //  0 ~ 9
		v2.push_back(i + 5);     //  5 ~ 14
	}

	vector<int>vTarget1;
	cout << "v1 相对于 v2的差集：" << endl;
	vTarget1.resize(v1.size());  // 两个集合完全不同时最大			
	vector<int>::iterator intEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget1.begin());
	for_each(vTarget1.begin(), intEnd, Print);
	cout << endl;
	for_each(vTarget1.begin(), vTarget1.end(), Print);
	cout << endl;

	vector<int>vTarget2;
	cout << "v2 相对于 v1的差集：" << endl;
	vTarget2.resize(v2.size());  // 两个集合完全不同时最大			
	intEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget2.begin());
	for_each(vTarget2.begin(), intEnd, Print);
	cout << endl;
	for_each(vTarget2.begin(), vTarget2.end(), Print);
	cout << endl;
}

运行实例：
在这里插入图片描述

以上内容为看过黑马c++后的知识总结，如果有什么疑问或者建议都可以在评论区留言，感谢大家对在这里插入图片描述的支持。

相关文章：

  • python图像处理（图像缩放）
  • 电商项目之同一笔单多次收款成功
  • OpenFeign总结
  • 【Linux】基础IO --- 系统级文件接口、文件描述符表、文件控制块、fd分配规则、重定向…
  • 计算机网络01_---软考高级系统架构师010
  • 【Linux】冯诺依曼体系结构与操作系统概念理解
  • 【c语言进阶】枚举与联合体的基本知识大全
  • Python与Matlab混合编程案例
  • 排列的时候如何避免重复？
  • 芒果改进YOLOv5系列：原创结合Conv2Formers改进结构，Transformer 风格的卷积网络视觉基线模型，超越ConvNeXt结构
  • 利用Windows系统服务进行权限提升
  • WebAssembly编译之(2)-Ubuntu搭建WASM编译环境
  • InstanceNorm LayerNorm
  • yolo结构介绍
  • 最详细、最仔细、最清晰的几道python习题及答案（建议收藏哦）
  • CentOS从零开始部署Nodejs项目
  • javascript面向对象之创建对象
  • Kibana配置logstash，报表一体化
  • Linux链接文件
  • python_bomb----数据类型总结
  • vagrant 添加本地 box 安装 laravel homestead
  • 阿里云容器服务区块链解决方案全新升级 支持Hyperledger Fabric v1.1
  • 对超线程几个不同角度的解释
  • 和 || 运算
  • 模仿 Go Sort 排序接口实现的自定义排序
  • 前端每日实战：61# 视频演示如何用纯 CSS 创作一只咖啡壶
  • 一些关于Rust在2019年的思考
  • 做一名精致的JavaScripter 01：JavaScript简介
  • 微龛半导体获数千万Pre-A轮融资，投资方为国中创投 ...
  • ​VRRP 虚拟路由冗余协议（华为）
  • #宝哥教你#查看jquery绑定的事件函数
  • #我与Java虚拟机的故事#连载19：等我技术变强了，我会去看你的 ​
  • （16）Reactor的测试——响应式Spring的道法术器
  • （2）STM32单片机上位机
  • (cljs/run-at (JSVM. :browser) 搭建刚好可用的开发环境!)
  • (javascript)再说document.body.scrollTop的使用问题
  • （Java岗）秋招打卡！一本学历拿下美团、阿里、快手、米哈游offer
  • (MonoGame从入门到放弃-1) MonoGame环境搭建
  • (Spark3.2.0)Spark SQL 初探： 使用大数据分析2000万KF数据
  • （笔记）Kotlin——Android封装ViewBinding之二 优化
  • （附源码）计算机毕业设计SSM基于java的云顶博客系统
  • （四）汇编语言——简单程序
  • (原創) 人會胖會瘦，都是自我要求的結果 (日記)
  • (转)h264中avc和flv数据的解析
  • (转)视频码率,帧率和分辨率的联系与区别
  • .bat批处理（三）：变量声明、设置、拼接、截取
  • .NET 的静态构造函数是否线程安全？答案是肯定的！
  • .net 调用php,php 调用.net com组件 --
  • .Net+SQL Server企业应用性能优化笔记4——精确查找瓶颈
  • .sh
  • :如何用SQL脚本保存存储过程返回的结果集
  • @Autowired标签与 @Resource标签 的区别
  • @JoinTable会自动删除关联表的数据
  • @param注解什么意思_9000字，通俗易懂的讲解下Java注解
  • @staticmethod和@classmethod的作用与区别