-
【STL】常见遍历算法、查找算法、排序算法
概述
STL常用算法主要是由头文件《algorithm》、《functional》、《numeric》组成
《algorithm》是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历、赋值、修改等等
《numeric》体积较小，只包括几个在序列上面进行简单数学运算的模板函数
《functional》定义了一些模板类，用来声明函数对象（仿函数）1. 常用遍历算法
算法原型：
for_each //遍历容器 transform //搬运容器到另一个容器中- 1
- 2
1.1 for_each
功能描述：
- 实现容器的遍历
函数原型：
for_each(iterator beg, iterator end, _func); // 遍历算法 遍历容器元素 // beg 开始迭代器 // end 结束迭代器 // _func 函数或者函数对象- 1
- 2
- 3
- 4
- 5
示例：
//普通函数 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
- 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
1.2 transform
功能描述：
- 搬运容器到另一个容器中
函数原型：
transform(iterator beg1, iterator end1, iterator beg2, _func); //beg1 源容器开始迭代器 //end1 源容器结束迭代器 //beg2 目标容器开始迭代器 //_func 函数或者函数对象- 1
- 2
- 3
- 4
- 5
示例：
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; }- 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
注意：搬运的目标容器必须提前开辟空间，否则无法正常搬运
2. 常用查找算法
算法原型：
find //查找元素 find_if //按条件查找元素 adjacent_find //查找相邻重复元素 binary_search //二分查找法 count //统计元素个数 count_if //按条件统计元素个数- 1
- 2
- 3
- 4
- 5
- 6
2.1 find
功能描述：
- 查找指定元素，找到了返回元素的迭代器，找不到返回结束迭代器end()
函数原型：
ind(iterator beg, iterator end, value); // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // value 查找的元素- 1
- 2
- 3
- 4
- 5
示例：
//内置数据类型 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; }- 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
注意：利用find查找容器中的指定元素，返回的是迭代器
2.2 find_if
功能描述：
- 按条件查找元素
函数原型：
find_if(iterator beg, iterator end, _Pred); // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // _Pred 函数或者谓词（返回bool类型的仿函数）- 1
- 2
- 3
- 4
- 5
示例：
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; } }- 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
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
2.3 adjacent_find
功能：
- 查找相邻重复元素
函数原型：
adjacent_find(iterator beg, iterator end); // 查找相邻重复元素,返回相邻元素的第一个位置的迭代器 // beg 开始迭代器 // end 结束迭代器- 1
- 2
- 3
- 4
示例：
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; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
2.4 binary_search
功能描述：
- 在有序序列中查找指定元素是否存在
函数原型：
bool binary_search(iterator beg, iterator end, value); // 查找指定的元素，查到 返回true 否则false // 注意: 在无序序列中不可用 // beg 开始迭代器 // end 结束迭代器 // value 查找的元素- 1
- 2
- 3
- 4
- 5
- 6
示例：
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; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
注意：二分查找的效率很高，但是要注意要查找的容器必须是有序的
2.5 count
功能描述：
- 统计元素个数
函数原型：
count(iterator beg, iterator end, value); // 统计元素出现次数 // beg 开始迭代器 // end 结束迭代器 // value 统计的元素- 1
- 2
- 3
- 4
- 5
示例：
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; }- 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
注意：统计自定义数据类型时，需要配合重载 operator==
2.6 count_if
功能描述：
- 按条件统计元素个数
函数原型：
count_if(iterator beg, iterator end, _Pred); // 按条件统计元素出现次数 // beg 开始迭代器 // end 结束迭代器 // _Pred 谓词- 1
- 2
- 3
- 4
- 5
示例：
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; }- 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
3. 常用排序算法
算法原型：
sort //对容器内元素进行排序 random_shuffle //洗牌 指定范围内的元素随机调整次序 merge // 容器元素合并，并存储到另一容器中 reverse // 反转指定范围的元素- 1
- 2
- 3
- 4
3.1 sort
功能描述：
- 对容器内元素进行排序
函数原型：
sort(iterator beg, iterator end, _Pred); // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // _Pred 谓词- 1
- 2
- 3
- 4
- 5
示例：
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; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
3.2 random_shuffle
功能描述：
- 洗牌，对指定范围内的元素随机调整次序
函数原型：
random_shuffle(iterator beg, iterator end); // 指定范围内的元素随机调整次序 // beg 开始迭代器 // end 结束迭代器- 1
- 2
- 3
- 4
示例：
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; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
注意：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 目标容器开始迭代器- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
示例：
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; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
注意：merge合并的两个容器必须是有序的
3.4 reverse
功能描述：
- 将容器内的元素进行反转
函数原型：
reverse(iterator beg, iterator end); // 反转指定范围的元素 // beg 开始迭代器 // end 结束迭代器- 1
- 2
- 3
- 4
示例：
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; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
-
相关阅读:
如何区分小角X射线散射和小角X射线衍射？
Allegro Design Entry HDL（OrCAD Capture HDL）原理图是设计快速入门图文教程
Linux 动、静态库原理深剖
字节一面：css选择器有哪些？优先级？哪些属性可以继承？
CTFHub | 弱口令
C# NModbus TCP 主从站通信样例
STM32_ESP8266 连接阿里云 操作图解
接口自动化测试小结
如何设置负载均衡EasySLB后端服务器网关
【TWS API 问题2】如何用盈透证券的TWS API持续获取5分钟K线的问题？
- 原文地址：https://blog.csdn.net/qq_59702185/article/details/126797442
