IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【STL】常见遍历算法、查找算法、排序算法 -> 正文阅读

[数据结构与算法]【STL】常见遍历算法、查找算法、排序算法

文章目录

概述

STL常用算法主要是由头文件《algorithm》、《functional》、《numeric》组成
《algorithm》是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历、赋值、修改等等
《numeric》体积较小，只包括几个在序列上面进行简单数学运算的模板函数
《functional》定义了一些模板类，用来声明函数对象（仿函数）

1. 常用遍历算法

算法原型：

for_each //遍历容器
transform //搬运容器到另一个容器中

1.1 for_each

功能描述：

  • 实现容器的遍历

函数原型：

for_each(iterator beg, iterator end, _func);
// 遍历算法 遍历容器元素
// beg 开始迭代器
// end 结束迭代器
// _func 函数或者函数对象

示例：

//普通函数
void print01(int val)
{
	cout << val << " ";
}

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

void test01()
{
	vector<int> v;
	for (int i = 0; i < 10; ++i)
	{
		v.push_back(i + 1);
	}
	//遍历
	for_each(v.begin(), v.end(), print01);
	cout << endl;

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

1.2 transform

功能描述：

  • 搬运容器到另一个容器中

函数原型：

transform(iterator beg1, iterator end1, iterator beg2, _func);
//beg1 源容器开始迭代器
//end1 源容器结束迭代器
//beg2 目标容器开始迭代器
//_func 函数或者函数对象

示例：

class TransForm
{
public:
	int operator()(int val)
	{
		return val;
	}
};

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

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

	vector<int> target;//目标容器
	target.resize(v.size());//切记提前开辟好空间
	transform(v.begin(), v.end(), target.begin(), TransForm());
	for_each(target.begin(), target.end(), print());
	cout << endl;
}

注意：搬运的目标容器必须提前开辟空间，否则无法正常搬运

2. 常用查找算法

算法原型：

find //查找元素
find_if //按条件查找元素
adjacent_find //查找相邻重复元素
binary_search //二分查找法
count //统计元素个数
count_if //按条件统计元素个数

2.1 find

功能描述：

  • 查找指定元素，找到了返回元素的迭代器，找不到返回结束迭代器end()

函数原型：

ind(iterator beg, iterator end, value);
// 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
// beg 开始迭代器
// end 结束迭代器
// value 查找的元素

示例：

//内置数据类型
void test01()
{
	vector<int> v;
	for (int i = 0; i < 10; ++i)
	{
		v.push_back(i + 1);
	}
	//查找容器中是否有元素6
	vector<int>::iterator pos = find(v.begin(), v.end(), 6);
	if (pos == v.end()) cout << "没有找到" << endl;
	else cout << "找到了：" << *pos << endl;
}

//自定义数据类型
class Person
{
public:
	string name;
	int age;
public:
	Person(string name, int age)
	{
		this->name = name;
		this->age = age;
	}
	//重载==
	bool operator==(const Person& p)
	{
		if (this->name == p.name && this->age == p.age) return true;
		else return false;
	}
};

void test02()
{
	vector<Person> v;
	Person p1("张三", 18);
	Person p2("李四", 20);
	Person p3("王五", 25);
	Person p4("老六", 30);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	vector<Person>::iterator pos = find(v.begin(), v.end(), p2);
	if (pos == v.end()) cout << "没有找到" << endl;
	else cout << "找到了，姓名:" << pos->name << " 年龄:" << pos->age << endl;
}

注意：利用find查找容器中的指定元素，返回的是迭代器

2.2 find_if

功能描述：

  • 按条件查找元素

函数原型：

find_if(iterator beg, iterator end, _Pred);
// 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
// beg 开始迭代器
// end 结束迭代器
// _Pred 函数或者谓词（返回bool类型的仿函数）

示例：

class GreaterFive
{
public:
	bool operator()(int val)
	{
		return val > 5;
	}
};

void test01()
{
	vector<int> v;
	for (int i = 0; i < 10; ++i)
	{
		v.push_back(i + 1);
	}
	vector<int>::iterator pos = find_if(v.begin(), v.end(), GreaterFive());
	if (pos == v.end())
	{
		cout << "没有找到比5大的数字" << endl;
	}
	else
	{
		cout << "找到比5大的数字：" << *pos << endl;
	}
}

//自定义数据类型
class Person
{
public:
	string name;
	int age;
public:
	Person(string name, int age)
	{
		this->name = name;
		this->age = age;
	}
};

class Greater20
{
public:
	bool operator()(Person& p)
	{
		return p.age > 20;
	}
};

void test02()
{
	vector<Person> v;
	Person p1("张三", 18);
	Person p2("李四", 20);
	Person p3("王五", 40);
	Person p4("老六", 12);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	vector<Person>::iterator pos = find_if(v.begin(), v.end(), Greater20());
	if (pos != v.end())
	{
		cout << "找到比20岁大的人了，name：" << pos->name << "age: " << pos->age << endl;
	}
	else
	{
		cout << "没有找到比20岁大的人了" << endl;
	}
}

2.3 adjacent_find

功能：

  • 查找相邻重复元素

函数原型：

adjacent_find(iterator beg, iterator end);
// 查找相邻重复元素,返回相邻元素的第一个位置的迭代器
// beg 开始迭代器
// end 结束迭代器

示例：

void test01()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(3);
	v.push_back(4);
	vector<int>::iterator it = adjacent_find(v.begin(), v.end());
	if (it != v.end())
	{
		cout << "找到相邻重复的元素了，是：" << *it << endl;
	}
	else
	{
		cout << "没有找到相邻重复的元素" << endl;
	}
}

2.4 binary_search

功能描述：

  • 在有序序列中查找指定元素是否存在

函数原型：

bool binary_search(iterator beg, iterator end, value);
// 查找指定的元素，查到 返回true 否则false
// 注意: 在无序序列中不可用
// beg 开始迭代器
// end 结束迭代器
// value 查找的元素

示例：

void test01()
{
	vector<int> v;
	for (int i = 0; i < 10; ++i) v.push_back(i + 1);
	//二分查找
	bool ret = binary_search(v.begin(), v.end(), 2);
	if (ret) cout << "找到了" << endl;
	else cout << "没有找到" << endl;
}

注意：二分查找的效率很高，但是要注意要查找的容器必须是有序的

2.5 count

功能描述：

  • 统计元素个数

函数原型：

count(iterator beg, iterator end, value);
// 统计元素出现次数
// beg 开始迭代器
// end 结束迭代器
// value 统计的元素

示例：

void test01()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(2);
	v.push_back(4);
	v.push_back(2);
	v.push_back(2);
	int num = count(v.begin(), v.end(), 2);
	cout << "2的个数为：" << num << endl;
}

//自定义数据类型
class Person
{
public:
	string name;
	int age;
public:
	Person(string name, int age)
	{
		this->name = name;
		this->age = age;
	}
	bool operator==(const Person& p)
	{
		if (this->age == p.age) return true;
		else return false;
	}
};

void test02()
{
	vector<Person> v;
	Person p1("张三", 18);
	Person p2("李四", 20);
	Person p3("王五", 18);
	Person p4("老六", 12);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	Person p("老八", 18);
	int num = count(v.begin(), v.end(), p);
	cout << "与p年龄相等的人数为：" << num << endl;
}

注意：统计自定义数据类型时，需要配合重载 operator==

2.6 count_if

功能描述：

  • 按条件统计元素个数

函数原型：

count_if(iterator beg, iterator end, _Pred);
// 按条件统计元素出现次数
// beg 开始迭代器
// end 结束迭代器
// _Pred 谓词

示例：

class Greater5
{
public:
	bool operator()(int val)
	{
		return val > 5;
	}
};

void test01()
{
	vector<int> v;
	for (int i = 0; i < 10; ++i) v.push_back(i + 1);
	int num = count_if(v.begin(), v.end(), Greater5());
	cout << "大于4的个数为：" << num << endl;
}

//自定义数据类型
class Person
{
public:
	string name;
	int age;
public:
	Person(string name, int age)
	{
		this->name = name;
		this->age = age;
	}
};

class AgeLess20
{
public:
	bool operator()(const Person& p)
	{
		return p.age < 20;
	}
};

void test02()
{
	vector<Person> v;
	Person p1("张三", 18);
	Person p2("李四", 20);
	Person p3("王五", 18);
	Person p4("老六", 12);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	int num = count_if(v.begin(), v.end(), AgeLess20());
	cout << "小于20岁的人数：" << num << endl;
}

3. 常用排序算法

算法原型：

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

3.1 sort

功能描述：

  • 对容器内元素进行排序

函数原型：

sort(iterator beg, iterator end, _Pred);
// 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
// beg 开始迭代器
// end 结束迭代器
// _Pred 谓词

示例：

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

void test01()
{
	vector<int> v;
	v.push_back(2);
	v.push_back(4);
	v.push_back(1);
	v.push_back(3);
	v.push_back(5);
	//sort默认排序规则从小到大
	sort(v.begin(), v.end());
	for_each(v.begin(), v.end(), print);
	cout << endl;
	//从大到小排序
	sort(v.begin(), v.end(), greater<int>());
	for_each(v.begin(), v.end(), print);
	cout << endl;
}

3.2 random_shuffle

功能描述：

  • 洗牌，对指定范围内的元素随机调整次序

函数原型：

random_shuffle(iterator beg, iterator end);
// 指定范围内的元素随机调整次序
// beg 开始迭代器
// end 结束迭代器

示例：

void test01()
{
	srand((unsigned int)time(NULL));
	vector<int> v;
	for (int i = 0; i < 10; ++i) v.push_back(i + 1);
	for_each(v.begin(), v.end(), print);
	cout << endl;
	//打乱顺序
	random_shuffle(v.begin(), v.end());
	for_each(v.begin(), v.end(), print);
	cout << endl;
}

注意：random_shuffle洗牌算法比较使用，使用前记得加随机数种子srand（）

3.3 merge

功能描述：

  • 两个有序容器合并，并存储到另一个容器中

函数原型：

merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
// 容器元素合并，并存储到另一容器中
// 注意: 两个容器必须是有序的
// beg1 容器1开始迭代器
// end1 容器1结束迭代器
// beg2 容器2开始迭代器
// end2 容器2结束迭代器
// dest 目标容器开始迭代器

示例：

void test01()
{
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10; ++i)
	{
		v1.push_back(i);
		v2.push_back(i + 1);
	}
	vector<int> target;
	target.resize(v1.size() + v2.size());
	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin());
	for_each(target.begin(), target.end(), print);
	cout << endl;
}

注意：merge合并的两个容器必须是有序的

3.4 reverse

功能描述：

  • 将容器内的元素进行反转

函数原型：

reverse(iterator beg, iterator end);
// 反转指定范围的元素
// beg 开始迭代器
// end 结束迭代器

示例：

void test01()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	cout << "反转前：" << endl;
	for_each(v.begin(), v.end(), print);
	cout << endl;
	cout << "反转后：" << endl;
	reverse(v.begin(), v.end());
	for_each(v.begin(), v.end(), print);
	cout << endl;
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-09-13 11:43:26  更:2022-09-13 11:44:12 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 21:42:41-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码