五. STL-常用算法

概述：

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

1. 常用遍历算法

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

1.1 for_each

功能：实现遍历容器
原型：

for_each(iterator beg, iterator end ,_func())
/*iterator beg为开始迭代器，iterator end为结束迭代器，_func()为函数或者函数对象*/

示例：

//普通函数
void print01(int val)
{cout<<val<<" ";
}//函数对象
class Print02
{public:void operator()(int val){cout<<val<<" "}
};vector<int>v;
for_each(v.begin(),v.end(),print01);
for_each(v.begin(),v.end(),print02());

总结：for_each是最常用的遍历算法，需要熟练掌握。

1.2 transform

搬运容器到另一个容器中；
原型：

transform(iterator beg1,iterator end1,iterator beg2,_func)

示例：

class TransForm
{public:int  operator()(int val){return val + 100;}
};
... ...
vTarget.resize(v.size()); //目标容器需要提前开辟空间
transform(v.begin(),v.end(),vTarget.begin(),TransForm());

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

2. 常用查找算法

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

2.1 find

功能：查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()。
原型：

find(iterator beg , iterator end ,value) 
//value为查找的元素

示例：

//查找容器中是否有5这个元素
vector<int>::iterator it = find(v.begin(),v.end(),5);
if(it == v.end())
{cout<<"没有找到"<<endl;
}
else
{cout<<"找到："<<*it<<endl;
}//查找容器中是否有P2这个对象
class Person
{public:Person (string name ,int age){this->m_name = name;this->mAge = age;}
//重载 ==bool operator == (const Person & p){if(this->m_Name == p.m_Name && this->m_Age == p.m_Age){return true;}return false;}public:string m_Name;int m_Age;
};vector<Person>v;
Person p1("aaa",10);
Person p2("bbb",20);
Person p3("ccc",30);
v.push_back(p1);
v.push_back(p2);
v.push_back(p3);
vector<Person>::iterator it = find(v.begin(),v.end(),p2);
if(it == v.end())
{... ...
}

总结：利用find可以在容器中找到指定的元素，返回值是迭代器。

2.2 find_if

功能：按条件查找元素
原型：

find_if(iterator beg,iterator end, _pred);
//_pred为谓词

示例：

//内置数据类型
class GreaterFive
{public:bool operator()(int val){return val > 5;}
};
... ...
vector<int>::iterator it = find_if(v.begin(),v.end(),GreaterFive());
if(it == v.end())
{cout<<"没有找到"<<endl;
}
else
{cout<<"找到大于5的数字："<<*it<<endl;
}//自定义数据类型
class Person
{... ...
};
class Greater20
{public:bool operator()(Person & p){return p.m_Age > 20;}
};
... ...
vector<Person>::iterator it = find_if(v.begin(),v.end(),Greater20());
if(it == v.end())
{... ...
}

总结：find_if按条件查找使查找更加灵活，提供的仿函数可以改变不同的策略。

2.3 adjacent_find

功能：查找相邻重复元素
原型：

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

vector<int>::iterator it = adjacent_find(v.begin(),v.end());
if(it == v.end())
{cout<<"找不到"<<endl;
}
else
{cout<<"找到相邻重复元素为："<<*it<<endl;
}

2.4 binary_search

功能：查找指定元素是否存在
原型：

bool binary_search (iterator beg , iterator end, value);
//查找指定元素，查到返回true，否则false
//注意，在无序序列中不可用

示例：

//二分查找
bool ret = binary_search(v.begin(),v.end(),2);

总结：二分查找法效率很高，但是查找的容器中元素必须是有序序列。

2.5 count

功能：统计元素个数
原型：

count(iterator beg, iterator end, value);
//统计元素出现的个数

示例：

//内置数据类型
int num = count(v.begin(),v.end(),4);
... ...
//自定义数据类型
class Person
{public:Person (string name ,int age){this->m_name = name;this->mAge = age;}
//重载 ==bool operator == (const Person & p){if(this->m_Name == p.m_Name && this->m_Age == p.m_Age){return true;}return false;}public:string m_Name;int m_Age;
};
Person p ("aaa",10);
int num = count(v.begin(),v.end(),p);

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

2.6 count_if

功能：按条件统计元素个数
原型：

count_if(iterator beg , iterator end, _Pred);
// _Pred为谓词

示例：

class Greater4
{public:bool operator()(int val){return val >= 4;}
};int num = count_if(v.begin(),v.end(),Grearer4());
cout<<"大于4的个数为："<<num<<endl;