1. STL常用算法
STL的算法主要是由下面的头文件组成的。
<algorithm> <functional> <numeric>
1.algorithm是所有STL头文件中最大的一个范围涉及到比较、交换、查找、遍历操作、复制、修改等等算法的头文件。
2.numeric体积很小,只包括几个再序列上面进行简单数学运算的模板函数。
3.functional定义了一些模板类,用以声明函数对象。
4.如果读者还未知晓什么是仿函数,建议了解一下。
link:[https://blog.csdn.net/toby54king/article/details/105103111]
2. algorithm中常用的算法
2.1 STL常用遍历算法
for_each //遍历容器
transform //搬运容器中的元素到另一个容器
2.1.1 for_each函数
//遍历容器
//函数原型
for_each(iterator beg,iterator end,fund);
//遍历容器中的元素
//beg 开始迭代器
//end 结束迭起器
//_func 函数或仿函数,通过该参数对遍历的元素进行对应的操作
2.1.2 for_each案例:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//函数
void print1(int val)
{
cout<<val<<" ";
}
//仿函数
class print2
{
public:
void operator()(int val)
{
cout<<val<<" ";
}
};
int main()
{
vector<int>arr={1,2,3,4,5,6,7,8};
//函数传参
for_each(arr.begin(),arr.end(),print1);
cout<<endl;
//仿函数传参
for_each(arr.begin(),arr.end(),print2());
//要注意的是,for_each的参数之间是逗号,并非分号。
//最后的参数如果是函数,传参时不需要扩号,如果是仿函数,则需要扩号。
return 0;
}
2.1.3 transform函数
//将容器内的元素搬运到另外一个容器中。
//函数原型
tranform(iterator beg1, iterator end1, iterator beg2, _fund);
// beg1 源容器的开始迭代器
// end1 源容器的结束迭代器
// beg2 目标容器的开始迭代器
// _func函数或者仿函数,通过该参数,可以对源容器中的元素进行相应的 操作
2.1.4 transform案例
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//函数
int Transform1(int val)
{
return val+100;
}
//仿函数
class Transform2
{
public:
int operator()(int val)
{
return val+100;
}
};
void print(vector<int> arr)
{
for(auto i=arr.begin();i!=arr.end();i++)
{
cout<<*i<<" ";
}
cout<<endl;
}
int main()
{
vector<int>arr1={1,2,3,4,5,6,7,8};
vector<int>arr2={12,13,14,15,16};
print(arr1);
cout<<endl;
//函数传参
transform(arr1.begin(),arr1.end(),arr2.begin(),Transform1);
print(arr1);
print(arr2);
cout<<endl;
cout<<endl;
//仿函数传参
transform(arr1.begin(), arr1.end(), arr2.begin()+3, Transform2());
print(arr1);
print(arr2);
//要注意的是,transform的参数之间是逗号,并非分号。
//最后的参数如果是函数,传参时不需要扩号,如果是仿函数,则需要扩号。
//结果为:
//1 2 3 4 5 6 7 8
//1 2 3 4 5 6 7 8
//101 102 103 104 105
//1 2 3 4 5 6 7 8
//101 102 103 101 102
return 0;
}
从该结果可以看出,
transform函数搬运完成后,并不会对源容器产生影响。当目标容器在搬运区间内有元素时,原来的元素值会被覆盖,搬运只会在目标容器已有的空间进行,并不会开辟新的空间,当迭代器来到目标容器的end迭代器时,搬运就会结束。
2.2 STL常用的查找算法
find //查找元素
find_if // 按条件查找元素
adjacent_find // 查找相邻元素
binary_search //二分查找
cout //统计元素个数
cout_if //按条件统计元素个数
2.2.1 find函数
// 查找指定元素,返回找到元素的迭代器或end迭代器。
//函数原型
find(iterator beg, iterator end, value);
// beg 源容器的开始迭代器
// end 源容器的结束迭代器
// value 查找的元素
2.2.2 find案例
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int>arr={1,4,2,3,5,7,7,8};
auto it=find(arr.begin(),arr.end(),5);
if(it == arr.end())
{
cout<<"没有该元素"<<endl;
}
else
{
cout<<*it<<endl;
}
return 0;
}
// 该函数和部分容器内的find函数重名,但要注意的是,两者并不相同
// 前者只能应用于对应容器,后者可以所有容器使用。
2.2.3 find_if 函数
//按条件查找元素
//函数原型
find_if(iterator beg,iterator end, _Pred);
// beg 源容器的开始迭代器
// end 源容器的结束迭代器
// _Pred 函数或谓词(返回bool类型的仿函数)
2.2.4 find_if 案例
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Find1 {
public:
bool operator()(int val)
{
return val > 3;
}
};
bool Find2(int val)
{
return val > 5;
}
int main()
{
vector<int>arr = { 1,2,3,4,5,6,7,8 };
auto it = find_if(arr.begin(), arr.end(), Find2);
if (it == arr.end())
{
cout << "没有该元素" << endl;
}
else
{
cout << *it << endl;
}
cout << endl;
auto it1 = find_if(arr.begin(), arr.end(), Find1());
if (it1 == arr.end())
{
cout << "没有该元素" << endl;
}
else
{
cout << *it1 << endl;
}
return 0;
}
2.2.5 adjacent_find 函数
//查找相邻元素
//函数原型
adjacent_find(iterator beg,iterator end);
// beg 源容器的开始迭代器
// end 源容器的结束迭代器
2.2.6 adjacent_find 案例
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int>arr={1,2,2,3,3,4,5,6,7,8};
auto it=adjacent_find(arr.begin(),arr.end());
if(it == arr.end())
{
cout<<"没有该元素"<<endl;
}
else
{
cout<<*it<<endl;
}
//显然,adjacent_find函数只会找到第一组相邻重复的元素
return 0;
}
2.2.7 binary_search 函数
//查找指定元素是否存在
//要求查找序列为有序
//速度相对普通查找较快
//函数原型
bool binary_search(iterator beg, iterator end, value);
//跟find 相比,只会返回true或false
//且要求有序序列
// beg 源容器的开始迭代器
// end 源容器的结束迭代器
// value 查找的元素
2.2.8 binary_search 案例
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int>arr={1,2,3,4,5,6,7,8};
auto it=binary_search(arr.begin(),arr.end(),5);
if(!it)
{
cout<<"没有该元素"<<endl;
}
else
{
cout<<"存在该元素"<<endl;
}
//要注意的是,binary_search只能查找有序序列
return 0;
}
2.3 STL 的计数算法
cout //统计元素个数
cout_if //按条件统计元素个数
2.3.1 count 函数
//统计元素个数
//函数原型
count(iterator beg, iterator end, value);
// beg 源容器的开始迭代器
// end 源容器的结束迭代器
// value 统计的元素
// 通过返回值来接收统计的元素个数
2.3.2 cout_if 函数
//按条件统计元素个数
//函数原型
cout_if(iterator beg, iterator end, _Pred);
// beg 源容器的开始迭代器
// end 源容器的结束迭代器
// _pred 函数或谓词
2.3.3 count和count_if案例
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class count1{
public:
bool operator()(int val)
{
return val>4;
}
};
bool count2(int val)
{
return val>3;
}
int main()
{
vector<int>arr={1,2,9,2,5,3,11,7,4,6};
auto it=count(arr.begin(),arr.end(),2);
cout<<it<<endl<<endl;
auto it1=count_if(arr.begin(), arr.end(), count1());
cout<<it1<<endl<<endl;
int it2=count_if(arr.begin(),arr.end(), count2);
cout<<it2<<endl<<endl;
return 0;
}
2.4 STL 常用的排序算法
sort //对容器内的元素进行排序
random_shuffle //洗mergee牌 指定范围内的元素进行随机调整
merge //合并两个容器,存储在另外一个容器内
reverse //反转指定范围内的元素
2.4.1 sort 函数
//对容器内的元素进行排序
//函数原型
sort(iterator beg, iterator end, _Pred);
//beg 开始迭代器
//end 结束迭代器
//_Pred 函数或谓词
2.4.2 sort 案例
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Grater{
public:
bool operator()(int v1,int v2)
{
return v1<v2;
}
};
bool Grater1(int val1,int val2)
{
return val1<val2;
}
void Print(int val)
{
cout<<val<<" ";
}
int main()
{
vector<int>arr={12,22,29,34,5,13,21,17,14,6};
vector<int>arr1={33,45,11,0,4,3,22,67,94,16};
for_each(arr.begin(),arr.end(),Print);
cout<<endl;
for_each(arr1.begin(),arr1.end(),Print);
cout<<endl<<endl;
sort(arr.begin(),arr.end(),Grater1);
for_each(arr.begin(),arr.end(),Print);
cout<<endl<<endl;
sort(arr1.begin(),arr1.end(),Grater());
for_each(arr1.begin(),arr1.end(),Print);
return 0;
}
2.4.3 random_shuffle 函数
//洗牌 指定范围内的元素随机调整
//函数原型
random_shuffle(iterator beg, iterator end);
//beg 开始迭代器
//end 结束迭代器
2.4.4 random_shuffle 案例
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<ctime>
using namespace std;
class Print{
public:
void operator()(int val)
{
cout<<val<<" ";
}
};
int main()
{
vector<int>arr={1,2,6,7,8,12,13,17,24,36};
srand((unsigned int)time(NULL));
//使用random_shuffle函数时,跟使用random一样,一定要设置随机种子。
for_each(arr.begin(),arr.end(),Print());
cout<<endl;
random_shuffle(arr.begin(),arr.end());
for_each(arr.begin(),arr.end(),Print());
cout<<endl;
return 0;
}
2.4.5 merge 函数
//两个容器元素合并,存储在另外一个容器
//函数原型
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
//注意,两个容器必须是有序的
// beg1 容器1的开始迭代器
// end1 容器1的结束迭代器
// beg2 容器2的开始迭代器
// end2 容器2的结束迭代器
//dest 目标容器的开始迭代器
// 目标容器必须要提前分配足够大的空间
2.4.6 merge 案例
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Print{
public:
void operator()(int val)
{
cout<<val<<" ";
}
};
int main()
{
vector<int>arr={1,2,4,5,8,9,11,21,33,45};
vector<int>arr1={2,5,8,10,12,17,23,66};
vector<int>arr2;
arr2.resize(arr.size()+arr1.size());
for_each(arr2.begin(),arr2.end(),Print());
cout<<endl;
merge(arr.begin(),arr.end(),arr1.begin(),arr1.end(),arr2.begin());
for_each(arr2.begin(),arr2.end(),Print());
//两个源容器必须是有序的
//目标容器必须要提前分配好足够大的空间
//合并后的目标容器仍然是有序的
cout<<endl;
return 0;
}
reverse 函数
//将容器内元素进行反转
//函数原型
reverse(iterator beg, iterator end);
//beg 开始迭代器
//end 结束迭代器
2.4.7 reverse 案例
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Print{
public:
void operator()(int val)
{
cout<<val<<" ";
}
};
int main()
{
vector<int>arr={1,2,4,5,8,9,11,21,33,45};
vector<int>arr1={12,5,82,120,42,17,73,66};
for_each(arr.begin(),arr.end(),Print());
cout<<endl<<endl;
for_each(arr1.begin(),arr1.end(),Print());
cout<<endl<<endl;
reverse(arr.begin(),arr.end());
reverse(arr1.begin(),arr1.end());
for_each(arr.begin(),arr.end(),Print());
cout<<endl<<endl;
for_each(arr1.begin(),arr1.end(),Print());
cout<<endl<<endl;
return 0;
}
2.5 STL常用的拷贝和替换函数
copy //将容器内指定的范围拷贝到另外一个容器内
copy_if //将容器内指定范围满足条件的元素拷贝到另外一个容器内
replace // 将容器指定的范围的旧元素修改为新元素
repalce_if // 容器内指定范围满足条件的元素替换成新元素
swap //交换两个容器的元素
2.5.1 copy 函数
//将容器内指定的范围拷贝到另外一个容器内
//函数原型
copy(iterator beg, iterator end, iterator dest);
//beg 开始迭代器
//end 结束迭代器
//dest 目标开始拷贝的迭代器
2.5.2 copy_if 函数
//将容器内指定范围满足条件的元素拷贝到另外一个容器内
//函数原型
copy(iterator beg, iterator end, iterator dest, _Pred);
//beg 开始迭代器
//end 结束迭代器
//dest 目标开始拷贝的迭代器
//_pred 函数或谓词
2.5.3 copy 和 copy_ if 案例
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Print {
public:
void operator()(int val)
{
cout << val << " ";
}
};
bool Graver(int val)
{
return val > 3;
}
class Graver1 {
public:
bool operator()(int val)
{
return val < 3;
}
};
int main()
{
vector<int>arr = { 1,2,4,5,8,9,11,21,33,45 };
vector<int>arr1 = { 12,5,82,9 };
arr1.resize(arr.size());
copy(arr.begin(), arr.end(), arr1.begin());
for_each(arr1.begin(), arr1.end(), Print());
cout << endl << endl;
//结果 1 2 4
//这里的结果可以看出copy同上面的merge一样,需要开辟足够
//且拷贝的值会覆盖原来的容器内的值。
vector<int>arr3 = { 1,2,4,5,8,9,11,21,33,45 };
vector<int>arr4 = { 12,5,82,9 };
arr4.resize(arr3.size());
copy_if(arr3.begin(), arr3.end(), arr4.begin(), Graver1());
for_each(arr4.begin(), arr4.end(), Print());
cout << endl << endl;
vector<int>arr5 = { 1,2,4,5,8,9,11,21,33,45 };
vector<int>arr6 = { 12,5,82,9 };
arr6.resize(arr5.size());
copy_if(arr5.begin(), arr5.end(), arr6.begin(), Graver);
for_each(arr6.begin(), arr6.end(), Print());
cout << endl << endl;
return 0;
}
2.5.4 replace 函数
//将指定容器内范围的旧元素替换成新元素
//函数原型
replace(iterator beg, iterator end, oldvalue, newvalue);
//beg 开始迭代器
//end 结束迭代器
//oldvalue 旧元素
//newvalue 新元素
2.5.6 replace_if 函数
//将区间内满足条件的元素替换成指定元素
//函数原型
replace_if (iterator beg, iterator end, _pred, newvalue);
//beg 开始迭代器
//end 结束迭代器
//_Pred 函数或谓词
//newvalue 新元素
2.5.7 replace 和 replace_if 案例
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Print{
public:
void operator()(int val)
{
cout<<val<<" ";
}
};
class change{
public:
bool operator()(int val)
{
return val<20;
}
};
int main()
{
vector<int>arr={1,1,4,5,8,9,1,1,33,1};
vector<int>arr1={12,5,82,120,42,17,73,66};
for_each(arr.begin(),arr.end(),Print());
cout<<endl;
for_each(arr1.begin(),arr1.end(),Print());
cout<<endl;
replace(arr.begin(),arr.end(),1,10);
replace_if(arr1.begin(),arr1.end(),change(),10);
for_each(arr.begin(),arr.end(),Print());
cout<<endl;
for_each(arr1.begin(),arr1.end(),Print());
cout<<endl;
return 0;
}
2.5.8 swap 函数
//交换两个容器内的元素
//函数原型
swap(container c1, container c2);
// c1 容器1
// c2 容器2
2.5.9 swap 案例
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Print {
public:
void operator()(int val)
{
cout << val << " ";
}
};
int main()
{
vector<int>arr = { 1,1,4,5,8,9,1,1,33,1 };
vector<int>arr1;
for_each(arr.begin(), arr.end(), Print());
cout << endl;
for_each(arr1.begin(), arr1.end(), Print());
cout << endl;
swap(arr, arr1);
for_each(arr.begin(), arr.end(), Print());
cout << endl;
for_each(arr1.begin(), arr1.end(), Print());
cout << endl;
//swap函数并没有要求交换的两个容器有足够大的空间,它会自动调整两个容器的空间大小。
return 0;
}
2.6 STL 的常用集合算法
set_intersection //求两个容器的交集
set_union // 求两个容器的并集
set_difference // 求两个容器的差集
2.6.1 set_intersection 函数
//求两个容器的并集
//函数原型
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
// beg1 容器1的开始迭代器
// end1 容器1的结束迭代器
// beg2 容器2的开始迭代器
// end2 容器2的结束迭代器
// dest 目标容器的开始迭代器
// 两个源容器必须时升序
// 目标容器必须要有足够大的空间
// 返回最后一个交集元素的下一个位置
2.6.2 intersecton 案例
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
using namespace std;
class Print {
public:
void operator()(int val)
{
cout << val << " ";
}
};
int main()
{
vector<int>arr = { 1,2,4,5,8,9,45,17,33,10 };
vector<int>arr1 = { 33,5,2,10,42,17,73,66 };
sort(arr.begin(), arr.end());
sort(arr1.begin(), arr1.end());
//这里要记住,两个源容器必须时有序的
vector<int>arr2;
arr2.resize(min(arr.size(), arr1.size()));
auto post =set_intersection(arr.begin(), arr.end(), arr1.begin(), arr1.end(), arr2.begin());
for_each(arr2.begin(), arr2.end(), Print());
cout << endl;
//因为交集并不一定跟预设的空间大小一样大,所以打印的时候,我们会用set_intersection的返回值作为参数
for_each(arr2.begin(), post, Print());
return 0;
}
注意事项:
求交集的两个集合必须是有序序列
目标容器开辟空间需要从两个容器中去小值文章来源:https://www.toymoban.com/news/detail-610740.html
set_intersection返回值即是交集中最后一个元素的下一个位置文章来源地址https://www.toymoban.com/news/detail-610740.html
2.6.3 set_union 函数
// 求两个集合的并集
// 函数原型
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
// beg1 容器1的开始迭代器
// end1 容器1的结束迭代器
// beg2 容器2的开始迭代器
// end2 容器2的结束迭代器
// dest 目标容器的开始迭代器
// 两个源容器必须时升序
// 目标容器必须要有足够大的空间
// 返回最后一个并集元素的下一个位置
2.6.4 set_union 案例
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
using namespace std;
class Print {
public:
void operator()(int val)
{
cout << val << " ";
}
};
int main()
{
vector<int>arr = { 1,2,4,5,8,9,45,17,33,10 };
vector<int>arr1 = { 33,5,2,10,42,17,73,66 };
sort(arr.begin(), arr.end());
sort(arr1.begin(), arr1.end());
//这里要记住,两个源容器必须时有序的
vector<int>arr2;
arr2.resize(arr.size() + arr1.size());
auto post =set_union(arr.begin(), arr.end(), arr1.begin(), arr1.end(), arr2.begin());
cout << *post << endl;
//返回值的位置
for_each(arr2.begin(), arr2.end(), Print());
cout << endl;
//因为并集自动去重,并不一定跟预设的空间大小一样大,所以打印的时候,我们会用set_union的返回值作为参数
for_each(arr2.begin(), post, Print());
//结果:
//0
//1 2 4 5 8 9 10 17 33 42 45 66 73 0 0 0 0 0
//1 2 4 5 8 9 10 17 33 42 45 66 73
return 0;
}
2.6.5 set_difference 函数
//求两个集合的差集
// 函数原型
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
// beg1 容器1的开始迭代器
// end1 容器1的结束迭代器
// beg2 容器2的开始迭代器
// end2 容器2的结束迭代器
// dest 目标容器的开始迭代器
// 两个源容器必须时升序
// 目标容器必须要有足够大的空间
// 返回最后一个差集元素的下一个位置
2.6.6 set_difference 案例
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
using namespace std;
class Print {
public:
void operator()(int val)
{
cout << val << " ";
}
};
int main()
{
vector<int>arr = { 1,2,4,5,8,9,45,17,33,10 };
vector<int>arr1 = { 33,5,2,10,42,17,73,66 };
sort(arr.begin(), arr.end());
sort(arr1.begin(), arr1.end());
//这里要记住,两个源容器必须时有序的
vector<int>arr2;
arr2.resize(max(arr.size(),arr1.size()));
auto post =set_difference(arr.begin(), arr.end(), arr1.begin(), arr1.end(), arr2.begin());
for_each(arr2.begin(), post, Print());
cout << endl;
auto post1 = set_difference(arr1.begin(), arr1.end(), arr.begin(), arr.end(), arr2.begin());
for_each(arr2.begin(), post1, Print());
cout << endl;
//因为差集并不一定跟预设的空间大小一样大,所以打印的时候,我们会用set_difference的返回值作为参数
//传参的时候,两个容器的先后顺序不一样,结果也不一样。
return 0;
}
3. numeric 中常用的算法
3.1 STL 的常用算术生成算法
accumulate //计算容器元素累计总和
fill // 向容器中添加元素
3.1.1 accumulate 函数
// 计算区间内容器元素累计总和
// 函数原型:
accumalate(iterator beg, iterator end, value);
// beg 开始迭代器
// end 结束迭代器
// value 起始值
3.1.2 fill 函数
//向容器内中填充指定元素
//函数原型
fill(iterator beg, iterator end, value);
// beg 开始迭代器
// end 结束迭代器
// value 填充值
3.1.3 accumulate 和 fill 案例
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
using namespace std;
class Print {
public:
void operator()(int val)
{
cout << val << " ";
}
};
int main()
{
vector<int>arr = { 1,1,4,5,8,9,1,1,33,1 };
vector<int>arr1 = { 12,5,82,120,42,17,73,66 };
cout << accumulate(arr.begin(), arr.end(), 5) << endl << endl;
fill(arr1.begin(), arr1.end(), 5);
for_each(arr1.begin(), arr1.end(), Print());
//结果为:
// 69
//5 5 5 5 5 5 5
//可以看到,在fill的填充范围内,容器内原来的值会被覆盖
return 0;
}
到了这里,关于STL中的常用算法详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!