STL学习笔记（三）——常用算法
琐记
这是STL学习笔记的第三篇, 前两篇分别是关于容器和函数对象的
第一篇:STL学习笔记（一）——容器
第二篇:STL学习笔记（二）
概述
算法主要是由头文件
<algorithm>，<numeric>和<functional>组成。
<algorithm>是所有STL头文件中最大的一个,其中常用的功能涉及到比较，交换，查找, 遍历，复制，修改，反转，排序，合并等…
<numeric>体积很小，只包括在几个序列容器上进行的简单运算的模板函数.包括加法乘法在序列上的一些操作。
<functional>定义了一些模板类,用以声明函数对象
1.常用遍历算法
for_each //遍历容器
transform //搬运容器到另一个容器中
1.1 for_each
/* 遍历算法 遍历容器元素 @param beg 开始迭代器 @param end 结束迭代器 @param _callback 函数回调或者函数对象 @return 函数对象 */ for_each(iterator beg, iterator end, _callback);总结: for_each既可以用普通参数,也可以用仿函数;不过用普通函数仅需函数名即可,用仿函数时候,需要用到仿函数的匿名对象
void myPrint1(int val){
cout<<val<<" ";
}
class myPrint2{
public:
void operator()(int val){
cout<<val<<" ";
}
};
for_each(v.begin(),v.end(),myPrint1);
for_each(v.begin(),v.end(),myPrint2());
1.2 transform
功能描述:
将指定容器区间元素搬运到另一容器中
函数原型:/* transform算法 将指定容器区间元素搬运到另一容器中 注意 : transform 不会给目标容器分配内存，所以需要我们提前分配好内存 @param beg1 源容器开始迭代器 @param end1 源容器结束迭代器 @param beg2 目标容器开始迭代器 @param _cakkback 回调函数或者函数对象 @return 返回目标容器迭代器 */ transform(iterator beg1, iterator end1, iterator beg2, _func);
示例:
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
class myPrint{//函数用来遍历
public:
void operator()(int val){
cout<<val<<" ";
}
};
class myTransform{//函数用来 搬运容器的同时对值进行操作
public:
int operator()(int val){
return val+100;
}
};
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(),myTransform());
for_each(v2.begin(),v2.end(),myPrint());
}
int main(){
test01();
system("pause");
return 0;
}
2.常用查找算法
find //查找元素
find_if //按条件查找元素
adjacent_find //查找相邻重复元素
binary_search //二分查找法
count //统计元素个数
count_if //按条件统计元素个数
2.1 find
功能描述:
查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()
函数原型:
find(iterator beg, iterator end, value); // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // value 查找的元素注意: 自定义数据类型在查找时需要重载==操作符; 不论是否找到都会返回迭代器;
内置数据类型
vector<int>::iterator it = find(v.begin(),v.end(),5);
if(it != v.end()){
cout<< *it <<endl;
}else
cout<<"not found"<<endl;
自定义数据类型
class Person{
public:
Person(string name,int age):_name(name),_age(age){}
//重载==
bool operator==(const Person&p) {
if(this->_name == p._name && this->_age == p._age){
return true;
}
else{
return false;
}
}
string _name;
int _age;
};
void test02(){
vector<Person>v;
v.push_back(Person("zhangsan",20));
v.push_back(Person("lisi",30));
v.push_back(Person("wangwu",40));
vector<Person>::iterator it = find(v.begin(),v.end(),Person("lisi",30));
if(it != v.end()){
cout<< it-> _name <<endl;
}else
cout<<"not found"<<endl;
}
2.2 find_if
功能描述:
按条件查找元素
函数原型:
find_if(iterator beg, iterator end, _Pred); // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置 // beg 开始迭代器// end 结束迭代器 // _Pred 函数或者谓词（返回bool类型的仿函数）注意:
内置数据类型
class greaterFive{
public:
bool operator()(int a){
return a>5;
}
};
void test01(){
vector<int>v;
for(int i=0;i<10;i++)
v.push_back(i);
vector<int>::iterator it = find_if(v.begin(),v.end(),greaterFive());
if (it == v.end())
cout << "没找到!" << endl;
else
cout << "找到大于5的数字:" << *it << endl;
}
自定义数据类型
class Person{
public:
Person(string name, int age):_name(name),_age(age){}
string _name;
int _age;
};
class greater9{
public:
bool operator()(Person& p){
return p._age>9;
}
};
void test02(){
vector<Person>v;
v.push_back(Person("aaa", 10));
v.push_back(Person("bbb", 20));
v.push_back(Person("ccc", 30));
v.push_back(Person("ddd", 40));
vector<Person>::iterator it = find_if(v.begin(),v.end(),greater9());
cout<<it->_age<<endl;
}
2.3 adjacent_find
功能描述：
查找相邻重复元素
函数原型：
adjacent_find(iterator beg, iterator end); // 查找相邻重复元素,返回相邻元素的第一个位置的迭代器 // beg 开始迭代器 // end 结束迭代器
2.4 binary_search
功能描述：
查找指定元素是否存在, 注意: 在无序序列中不可用
函数原型：
bool binary_search(iterator beg, iterator end, value); // 查找指定的元素，查到 返回true 否则false // 注意: 在无序序列中不可用 // beg 开始迭代器 // end 结束迭代器 // value 查找的元素注意: 所谓有序序列就是说从大到小或者从小到大排列的序列;如果我在一到十递增的容器末尾插入一个2,那本算法就不能应用于此容器.
2.5 count
功能描述：
统计元素个数
函数原型：
count(iterator beg, iterator end, value); // 统计元素出现次数 // beg 开始迭代器 // end 结束迭代器 // value 统计的元素
统计内置数据类型
int num=count(v.begin(),v.end(),10);
cout<<num<<endl;
统计自定义数据类型
class Person{
public:
Person(int id,string name):_id(id),_name(name){}
bool operator==(const Person& p){
if(p._id==this->_id)
return true;
else
return false;
}
int _id;
string _name;
};
//怎么用
int num=count(v.begin(), v.end(), Person(3,"adsf")) ;
2.6 count_if
功能描述：
按条件统计元素出现次数
函数原型：
count_if(iterator beg, iterator end,_Pred); // 按条件统计元素出现次数 // beg 开始迭代器 // end 结束迭代器 // _Pred 谓词由于这节的示例和find_if那一节基本一样,就不写了;
3.常用排序算法
算法简介:
sort//对容器内元素进行排序
random_shuffle//洗牌指定范围内的元素随机调整次序
merge//容器元素合并，并存储到另一容器中
reverse //反转指定范围的元素
3.1 sort
功能描述:
对容器内元素进行排序
函数原型
sort(iterator beg, iterator end, _Pred); //按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置 //beg 开始迭代器 //end 结束迭代器 /*_Pred 谓词,不写默认升序排列; 需要一个返回值是bool类型的()重载 也可以是STL内部的函数对象 */
sort(v1.begin(),v1.end());
for(auto i:v1) cout<<i<<" ";
cout<<endl;
sort(v1.begin(), v1.end(),greater<int>());
for(auto i:v1) cout<<i<<" ";
cout<<endl;
3.2 random_shuffle
random_shuffle 功能描述:
洗牌指定范围内的元素随机调整次序
函数原型：
random shuffle(iterator beg, iterator end); //指定范围内的元素随机调整次序 //beg 开始迭代器 //end 结束迭代器这个打乱算法依赖随机函数种子，所以在使用时要加上随机种子srand((unsigned int)time(NULL));，确保每次打乱的结果不同。记得包含time.h头文件
/*示例*/
#include<time.h>
void test02(){
srand((unsigned int)time(NULL));//随机数种子
vector<int> v1;
for(int i=0;i<10;i++)
v1.push_back(i);
random_shuffle(v1.begin(), v1.end());
for(auto i : v1)
cout << i << " ";
}
3.3 merge
merge 功能描述：
两个容器元素合并，并存储到另一容器中
函数原型:
merge(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest); //容器元素合并，并存储到另一容器中 //注意：两个容器必须是有序的 //beg1 容器1开始迭代器 //end1 容器1结束迭代器 //beg2 容器2开始迭代器 //end2 容器2结束迭代器 //dest 目标容器开始迭代器
警告:
①两个容器应均为有序序列,且排序方式相同
②在用目标容器之前需要提前给目标容器分配空间
vTarget.resize(v1.size() + v2.size());
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
3.4 reverse
reverse 功能描述:
将容器内元素进行反转, 反转指定范围的元素
函数原型:
reverse(iterator beg, iterator end); //反转指定范围的元素 //beg开始迭代器 //end结束迭代器
4.常用拷贝和替换算法
算法简介:
copy//容器内指定范围的元素拷贝到另一容器中
replace//将容器内指定范围的旧元素修改为新元素
replace_if //容器内指定范围满足条件的元素替换为新元素
swap //互换两个容器的元素
4.1 copy
copy 功能描述:
容器内指定范围的元素拷贝到另一容器中
函数原型:
copy(iterator beg,iterator end,iterator dest); //beg开始迭代器 //end结束迭代器 //dest目标起始迭代器注意:
dest应该提前 reszie 分配空间
意义不大,可以直接用=赋值;
4.2 replace
replace 功能描述
将区间内旧元素 替换成 新元素
函数原型:
replace(iterator beg,iterator end,oldvalue,newvalue) //将区间内旧元素 替换成 新元素 //beg开始迭代器 //end结束迭代器 //oldvalue 旧元素 //newvalue 新元素
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
class MyPrint{
public:
void operator()(int val){
cout << val << " ";
}
};
//常用拷贝和替换算法 replace
void test01(){
vector<int>v;
v.push_back(20);
v.push_back(30);
v.push_back(50);
v.push_back(20);
v.push_back(40);
cout << "替换前：" << endl;
for_each(v.begin(), v.end(), MyPrint());
cout << endl;
//将20替换为2000
replace(v.begin(), v.end(),20,2000);
cout << "替换后：" << endl;
for_each(v.begin(), v.end(), MyPrint());
cout << endl;
}
int main() {
test01();
system("pause");
return 0;
}
4.3 replace_if
replace 功能描述
将区间内满足条件的旧元素 替换成 新元素,需要重载()符号
函数原型:
replace_if(iterator beg,iterator end,_pred,newvalue) //将区间内旧元素 替换成 新元素 //beg开始迭代器 //end结束迭代器 //_pred 谓词 重载()符号 //newvalue 新元素
4.4 swap
swap 功能描述
互换两个容器的元素,应是两个相同类型的容器
函数原型:
swap(container c1,container c2); //将区间内旧元素 替换成 新元素 //互换两个容器的元素 //c1容器1 //c2容器2
5.常用算术生成算法
注意:
算术生成算法属于小型算法，使用时包含头文件为#include< numeric>
算法简介:
accumulate//计算区间内 容器元素累计总和
fill //向容器中添加元素
5.1 accumulate
accumulate 功能描述
计算容器元素累计总和
函数原型:
accumulate<iterator beg,iterator end,value> //beg开始迭代器 //end结束迭代器 //value 起始值例子:
int total = accumulate(v.begin(),v.end(),0);
5.2 fill
fill 功能描述
向容器中填充元素
函数原型:
fill(iterator beg,iterator end,value) //向容器中填充元素 //beg开始迭代器 //end结束迭代器 //value 填充的值例子:
fill(v.begin(), v.end(), 100);
注意:如果容器没有分配空间应该先分配空间再调用此函数
6.常用集合算法
算法简介:
set_intersection //求两个容器的交集
set_union//求两个容器的并集
set_difference //求两个容器的差集
6.1 set_intersection
set_intersection 功能描述
求两个集合的交集,两个集合必须是有序序列
函数原型:
set_intersection(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest); //求两个容器的交集 //beg1容器1开始迭代器 //end1容器1结束迭代器 //beg2容器2开始迭代器 //end2容器2结束迭代器 //dest 目标容器开始迭代器例子:
vTarget.resize(min(v1.size(), v2.size()));
vector::iterator itEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
注意:目标容器应该提前开辟空间(取小容器的size)
两个集合必须是有序序列
会返回交集中最后一个元素的位置
6.2 set_union
set_union 功能描述
求两个集合的并集
函数原型:
set_union(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest); //求两个容器的并集 //beg1容器1开始迭代器 //end1容器1结束迭代器 //beg2容器2开始迭代器 //end2容器2结束迭代器 //dest 目标容器开始迭代器例子:
vTarget.resize(v1.size() + v2.size());
vector::iterator itEnd = vector::iterator itEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());注意:
两个集合必须是有序序列
特殊情况 两个大容器没有交集，并集就是两个容器size相加
会返回交集中最后一个元素的位置
6.3 set_difference
功能描述:
求两个集合的差集
函数原型:
set_difference(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest); //求两个集合的差集 //注意：两个集合必须是有序序列 //beg1容器1开始迭代器 //end1容器1结束迭代器 //beg2容器2开始迭代器 //end2容器2结束迭代器 //dest 目标容器开始迭代器例子:
vTarget.resize(max(v1.size() , v2.size()));
vector::iterator itEnd = vector::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());注意:
两个集合必须是有序序列
特殊情况 两个大容器没有交集，并集就是取大的size
会返回交集中最后一个元素的位置