c++ stl 遍历算法和查找算法

概述：

算法主要由头文件<algorithm> <functional> <numeric> 提供
<algorithm> 是所有 STL 头文件中最大的一个，提供了超过 90 个支持各种各样算法的函数，包括排序、合并、搜索、去重、分解、遍历、数值交换、拷贝和替换、插入和删除等
<functional> 定义了一些模板类，用以声明函数对象。函数对象（function object）是一个重载了函数调用操作符（operator()）的类。
<numeric> 定义了执行算术运算的一些模板函数。

1. 常用遍历算法

学习目标：

掌握常用的遍历算法

算法简介：

for＿each // 遍历容器
transform // 搬运容器到另一个容器中

1.1 for_each

函数原型

for_each(iterator beg, iterator end, _func) 
beg 起始迭代器
end 结束迭代器
_func 函数或者函数对象

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <functional>
using namespace std;#define CEHUA 0
#define MEISHU 1
#define YANFA 2//  普通函数
void print01(int val){cout << val << " ";
}// 防函数
class PrintData{
public:void operator()(int val){cout << val << " ";}
};void test01()
{// 逻辑非vector<int> v;for(int i = 0; i < 10; i++){v.push_back(i);}for_each(v.begin(), v.end(), print01);cout << endl;// 防函数for_each(v.begin(), v.end(), PrintData());cout << endl;// Lambda 表达式for_each(v.begin(), v.end(), [](int val){cout << val << " ";});cout << endl;
}int main(int argc, char const *argv[])
{test01();return 0;
}

1.2 transform

概念：

搬运容器到另一个容器中

函数原型：

transform(iterator beg1, iterator end1, iteartor beg2, _fuc); 
beg1 原容器开始迭代器
end1 原容器结束迭代器
beg2 目标起始迭代器
_fuc 函数或者函数对象

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <functional>
using namespace std;#define CEHUA 0
#define MEISHU 1
#define YANFA 2//  stL 常用算法   transform// transform(iterator beg1, iterator end1, iteartor beg2, _fuc); class Transform{
public:int operator()(int val){// 将数字翻倍return val * 2;}};void test01()
{vector<int> v;for (int i = 0; i < 10; i++){v.push_back(i);}vector<int> v2;v2.resize(v.size()); // 目标容器需要提前开辟空间transform(v.begin(), v.end(), v2.begin(),Transform());// 遍历容器for_each(v2.begin(), v2.end(), [](int val){cout << val << " ";});
}int main(int argc, char const *argv[])
{test01();return 0;
}

2. 常用查找算法

算法简介

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

2.1 find

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

函数原型

find(begin, end, val) 
begin 开始迭代器
end 结束迭代器
val 查找的元素

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <functional>
using namespace std;#define CEHUA 0
#define MEISHU 1
#define YANFA 2//  stL 常用查找算法// find // 查找内置的数据类型
void test01()
{vector<int> v;for (int i = 0; i < 10; i++){v.push_back(i);}// 查找容器中是否有6vector<int>::iterator it = find(v.begin(), v.end(), 6);if(it == v.end()){cout << "没有找到" << endl;}else{cout << "找到元素为：" << *it << endl;}}// 查找自定义数据类型
class Person{
public:Person(string name, int age):m_Name(name),m_Age(age){}string m_Name;int m_Age;// 重载==bool operator==(const Person &p){if(this->m_Name == p.m_Name && this->m_Age == p.m_Age){return true;}else{return false;}}
};void test02(){vector<Person> v;Person p1("西施", 18);Person p2("王昭君", 19);Person p3("杨玉环", 17);Person p4("貂蝉", 16);Person p5("小乔", 15);v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);v.push_back(p5);Person p("貂蝉", 16);vector<Person>::iterator it =  find(v.begin(), v.end(), p);if(it == v.end()){cout << "没有找到" << endl;}else{cout << "找到元素为：" << it->m_Name << " " << it->m_Age << endl;}
}int main(int argc, char const *argv[])
{test02();return 0;
}

查找自定义数据，必须重载==

2.2 find_if

功能描述：

按条件查找元素

函数原型

find_if(iterator beg, iterator end, _Pred) 
功能描述：按条件查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
注意：_Pred为谓词(返回bool类型的防函数) 或 函数
beg 开始迭代器
end 结束迭代器

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <functional>
using namespace std;#define CEHUA 0
#define MEISHU 1
#define YANFA 2//  stL 常用查找算法// find_if// 查找内置的数据类型
void test01()
{vector<int> v;for (int i = 0; i < 10; i++){v.push_back(i);}// 用lambda表达式实现 查找容器中是有大于6 vector<int>::iterator it = find_if(v.begin(), v.end(), [&](int val){return val > 6;});if(it == v.end()){cout << "没有找到" << endl;}else{cout << "找到元素为：" << *it << endl;}}// 查找自定义数据类型
class Person{
public:Person(string name, int age):m_Name(name),m_Age(age){}string m_Name;int m_Age;bool operator==(const Person &p){if(this->m_Name == p.m_Name && this->m_Age == p.m_Age){return true;}else{return false;}}
};class findPerson{
public:bool operator()(const Person &p){// 查找年龄大于17的if (p.m_Age > 17){return true;}else{return false;}}
};void test02(){vector<Person> v;Person p1("西施", 18);Person p2("王昭君", 19);Person p3("杨玉环", 17);Person p4("貂蝉", 16);Person p5("小乔", 15);v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);v.push_back(p5);Person p("貂蝉", 16);vector<Person>::iterator it =  find_if(v.begin(), v.end(), findPerson());if(it == v.end()){cout << "没有找到" << endl;}else{cout << "找到元素为：" << it->m_Name << " " << it->m_Age << endl;}
}int main(int argc, char const *argv[])
{test02();return 0;
}

2.3 adjacent_find

功能描述：

查找相邻重复元素

函数原型：

adjacent_find(iterator first, iterator last, binary_predicate pred);
功能描述：
查找相邻重复元素，返回相邻元素的第一个位置的迭代器
参数说明：
first：开始迭代器
last：结束迭代器
pred：二元谓词

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <functional>
using namespace std;#define CEHUA 0
#define MEISHU 1
#define YANFA 2//  stL 常用查找算法// adjacent_find// 查找内置的数据类型
void test01()
{vector<int> v;v.push_back(10);v.push_back(20);v.push_back(20);v.push_back(30);v.push_back(40);v.push_back(30);v.push_back(50);vector<int>::iterator it = adjacent_find(v.begin(), v.end());if (it == v.end()){cout << "找不到" << endl;}else{cout << "找到相邻重复元素为：" << *it << endl;}}// 查找自定义数据类型
class Person{
public:Person(string name, int age):m_Name(name),m_Age(age){}string m_Name;int m_Age;bool operator==(const Person &p){if(this->m_Name == p.m_Name && this->m_Age == p.m_Age){return true;}else{return false;}}
};class findPerson{
public:bool operator()(const Person &p , const Person &p2){// 查找年龄相同的if (p.m_Age == p2.m_Age){return true;}else{return false;}}
};// 查找自定义数据类型
void test02(){vector<Person> v;Person p1("西施", 18);Person p2("王昭君", 19);Person p3("杨玉环", 19);Person p4("貂蝉", 16);Person p5("小乔", 15);v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);v.push_back(p5);vector<Person>::iterator it =  adjacent_find(v.begin(), v.end(), findPerson());if(it == v.end()){cout << "没有找到" << endl;}else{cout << "找到元素为：" << it->m_Name << " " << it->m_Age << endl;}
}int main(int argc, char const *argv[])
{test02();return 0;
}

2.4 binary_search

查找指定元素是否存在

函数原型

bool binary_search(InputIterator first, InputIterator last, const T& val);

功能描述：

查找到val在[first, last)区间中，则返回true，否则返回false。
注意：在无序序列中不可用。
beg 开始迭代器
end 结束迭代器
val 查找的元素

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <functional>
using namespace std;#define CEHUA 0
#define MEISHU 1
#define YANFA 2//  binary_searchvoid test01()
{vector<int> v;for(int i = 0; i < 10; i++){v.push_back(i);}bool result = binary_search(v.begin(), v.end(), 10);if (result){cout << "find" << endl;}else{cout << "not find" << endl;}}int main(int argc, char const *argv[])
{test01();return 0;
}

2.5 count

功能描述：

统计元素个数

函数原型

count(InputIterator first, InputIterator last, const T& val);

功能描述：

统计出元素次数
beg 开始迭代器
end 结束迭代器
val 查找的元素

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <functional>
using namespace std;#define CEHUA 0
#define MEISHU 1
#define YANFA 2//  count// 统计内置数据类型
void test01()
{vector<int> v;for(int i = 0; i < 10; i++){v.push_back(i);}v.push_back(10);v.push_back(10);int result = count(v.begin(), v.end(), 10);cout << result << endl;}// 统计自定义数据类型
class Person{
public:Person(string name, int age):m_Name(name), m_Age(age){}bool operator==(const Person &p){if(this->m_Age == p.m_Age){return true;}else{return false;}}string m_Name;int m_Age;
};void test02(){vector<Person> v;v.push_back(Person("西施", 18));v.push_back(Person("小龙女", 18));v.push_back(Person("貂蝉", 20));v.push_back(Person("杨玉环", 18));v.push_back(Person("王昭君", 19));Person p("小乔",18);int result = count(v.begin(), v.end(), p);cout << "和小乔年龄相同的人有" << result << "个";
}int main(int argc, char const *argv[])
{test02();return 0;
}

总结：统计自定义类型的时候，需要重载 operator==

2.6 count_if

功能描述： 按照条件在容器中统计元素个数

函数原型：

count_if(iterator beg, iterator end, _Pred)
beg 开始迭代器
end 结束迭代器
_Pred 谓词

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;#define CEHUA 0
#define MEISHU 1
#define YANFA 2//   count_ifclass Greater{
public:Greater(int val):m_Val(val){}bool operator()(int val){return val > m_Val;}int m_Val; // 可以改变条件
};// 统计内置数据类型
void test01()
{vector<int> v;for(int i = 0; i < 10; i++){v.push_back(i);}v.push_back(10);v.push_back(10);// 统计大于8的数字有多少个int result = count_if(v.begin(), v.end(), Greater(8));cout << result << endl;
}// 统计自定义数据类型
class Person{
public:Person(string name, int age):m_Name(name), m_Age(age){}bool operator==(const Person &p){if(this->m_Age == p.m_Age){return true;}else{return false;}}string m_Name;int m_Age;
};class CountPerson{
public:CountPerson(int age):m_Age(age){}bool operator()(const Person &p){return p.m_Age > m_Age;}int m_Age;
};void test02(){vector<Person> v;v.push_back(Person("西施", 18));v.push_back(Person("小龙女", 18));v.push_back(Person("貂蝉", 20));v.push_back(Person("杨玉环", 18));v.push_back(Person("王昭君", 19));Person p("小乔",18);v.push_back(p);int result = count_if(v.begin(), v.end(), CountPerson(17));cout << "年龄大于17的美女： " << result << "个";
}int main(int argc, char const *argv[])
{test02();return 0;
}