浅析STL中的常用算法
是一组不破坏操作数据的模板函数,用来对序列数据进行逐个处理、元素查找、子序列搜索、统计和匹配。非变异算法具有极为广泛的适用性,基本上可应用与各种容器。
1查找容器元素find
它用于查找等于某值的元素。它在迭代器区间[first,last)(闭开区间)上查找等于value值的元素,如果迭代器i所指的元素满足*i=value,则返回迭代器i;未找到满足条件的元素,返回last。函数原型:find(v1.begin(),v1.end(),num_to_find);
#include<vector>
#include<algorithm>
#include<iostream>
usingnamespacestd;
voidmain()
{
intnum_to_find=6;
vector<int>v1;
for(inti=0;i<10;i++)
v1.push_back(2*i);
vector<int>::iteratorresult;
result=find(v1.begin(),v1.end(),num_to_find);
if(result==v1.end())
cout<<"未找到任何元素匹配"<<num_to_find<<endl;
else
cout<<"匹配元素的索引值是"<<result-v1.begin()<<endl;
}
2条件查找容器元素find_if
利用返回布尔值的谓词判断pred,检查迭代器区间[first,last)(闭开区间)上的每一个元素,如果迭代器i满足pred(*i)=true,表示找到元素并返回迭代值i(找到的第一个符合条件的元素);未找到元素,返回末位置last。函数原型:find_if(v.begin(),v.end(),divby5);
#include<vector>
#include<algorithm>
#include<iostream>
usingnamespacestd;
booldivby5(intx)
{
returnx%5?0:1;
}
voidmain()
{
vector<int>v(20);
for(inti=0;i<v.size();i++)
{
v[i]=(i+1)*(i+3);
cout<<v[i]<<"";
}
cout<<endl;
vector<int>::iteratorilocation;
ilocation=find_if(v.begin(),v.end(),divby5);
if(ilocation!=v.end())
cout<<"找到第一个能被5整除的元素:"<<*ilocation<<endl<<"元素的索引位置是:"<<ilocation-v.begin()<<endl;
}
3统计等于某值的容器元素个数count
list<int>l;
count(l.begin(),l.end(),value)
4条件统计count_if
count_if(l.begin(),l.end(),pred)。谓词pred含义同find_if中的谓词。例子可以参考例2.
5子序列搜索search
search算法函数在一个序列中搜索与另一序列匹配的子序列。参数分别为一个序列的开始位置,结束位置和另一个序列的开始,结束位置。
函数原型:search(v1.begin(),v1.end(),v2.begin(),v2.end());
#include<vector>
#include<algorithm>
#include<iostream>
usingnamespacestd;
voidmain()
{
vector<int>v1;
cout<<"v1:";
for(inti=0;i<5;i++)
{
v1.push_back(i+5);
//注意:v1定义时没有给定大小,因此这里不能直接使用赋值语句。
cout<<v1[i]<<"";
}
cout<<endl;
vector<int>v2;
cout<<"v2:";
for(i=0;i<2;i++)
{
v2.push_back(i+7);
cout<<v2[i]<<"";
}
cout<<endl;
vector<int>::iteratorilocation;
ilocation=search(v1.begin(),v1.end(),v2.begin(),v2.end());
if(ilocation!=v1.end())
cout<<"v2的元素包含在v1中,起始元素为"<<"v1["<<ilocation-v1.begin()<<"]"<<endl;
else
cout<<"v2的元素不包含在v1中"<<endl;
}
6重复元素子序列搜索search_n
search_n算法函数搜索序列中是否有一系列元素值均为某个给定值的子序列。函数原型:search_n(v.begin(),v.end(),3,8),在v中找到3个连续的元素8
#include<vector>
#include<algorithm>
#include<iostream>
usingnamespacestd;
voidmain()
{
vector<int>v;
v.push_back(1);
v.push_back(8);
v.push_back(8);
v.push_back(8);
v.push_back(6);
v.push_back(6);
v.push_back(8);
vector<int>::iteratori;
i=search_n(v.begin(),v.end(),3,8);
if(i!=v.end())
cout<<"在v中找到3个连续的元素8"<<endl;
else
cout<<"在v中未找到3个连续的元素8"<<endl;
}
7最后一个子序列搜索find_end
函数原型find_end(v1.begin(),v1.end(),v2.begin(),v2.end());在V1中要求的位置查找V2中要求的序列。
#include<vector>
#include<algorithm>
#include<iostream>
usingnamespacestd;
voidmain()
{
vector<int>v1;
v1.push_back(-5);
v1.push_back(1);
v1.push_back(2);
v1.push_back(-6);
v1.push_back(-8);
v1.push_back(1);
v1.push_back(2);
v1.push_back(-11);
vector<int>v2;
v2.push_back(1);
v2.push_back(2);
vector<int>::iteratori;
i=find_end(v1.begin(),v1.end(),v2.begin(),v2.end());
if(i!=v1.end())
cout<<"v1中找到最后一个匹配v2的子序列,位置在"<<"v1["<<i-v1.begin()<<"]"<<endl;
}
是一组能够修改容器元素数据的模板函数。copy(v.begin(),v.end(),l.begin());将v中的元素复制到l中。
1元素复制copy
#include<vector>
#include<list>
#include<algorithm>
#include<iostream>
usingnamespacestd;
voidmain()
{
vector<int>v;
v.push_back(1);
v.push_back(3);
v.push_back(5);
list<int>l;
l.push_back(2);
l.push_back(4);
l.push_back(6);
l.push_back(8);
l.push_back(10);
copy(v.begin(),v.end(),l.begin());
list<int>::iteratori;
for(i=l.begin();i!=l.end();i++)
cout<<*i<<"";
cout<<endl;
}
2元素变换transform改变
函数原型:transform(v.begin(),v.end(),l.begin(),square);也是复制,但是要按某种方案复制。
#include<vector>
#include<list>
#include<algorithm>
#include<iostream>
usingnamespacestd;
intsquare(intx)
{
returnx*x;
}
voidmain()
{
vector<int>v;
v.push_back(5);
v.push_back(15);
v.push_back(25);
list<int>l(3);
transform(v.begin(),v.end(),l.begin(),square);
list<int>::iteratori;
for(i=l.begin();i!=l.end();i++)
cout<<*i<<"";
cout<<endl;
}
3替换replace
replace算法将指定元素值替换为新值。
#include<vector>
#include<algorithm>
#include<iostream>
usingnamespacestd;
voidmain()
{
vector<int>v;
v.push_back(13);
v.push_back(25);
v.push_back(27);
v.push_back(25);
v.push_back(29);
replace(v.begin(),v.end(),25,100);
vector<int>::iteratori;
for(i=v.begin();i!=v.end();i++)
cout<<*i<<"";
cout<<endl;
}
输出结果为131002710029
4条件替换replace_if
函数原型:replace_if(v.begin(),v.end(),odd,100);
#include<vector>
#include<algorithm>
#include<iostream>
usingnamespacestd;
boolodd(intx)
{
returnx%2;
}
voidmain()
{
vector<int>v;
for(inti=1;i<10;i++)
v.push_back(i);
replace_if(v.begin(),v.end(),odd,100);
vector<int>::iteratorilocation;
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<"";
cout<<endl;
}
5n次填充fill_n
函数原型fill_n(v.begin(),5,-1);向从v.begin开始的后面5个位置跳入-1
#include<vector>
#include<algorithm>
#include<iostream>
usingnamespacestd;
voidmain()
{
vector<int>v(10);
fill_n(v.begin(),5,-1);
vector<int>::iteratorilocation;
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<"";
cout<<endl;
}
输出结果:-1-1-1-1-100000
6随机生成n个元素generate
函数原型:generate_n(v.begin(),5,rand);向从v.begin开始的后面5个位置随机填写数据。
#include<vector>
#include<algorithm>
#include<iostream>
usingnamespacestd;
voidmain()
{
vector<int>v(10);
generate_n(v.begin(),5,rand);
vector<int>::iteratorilocation;
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<"";
cout<<endl;
}
7条件移除remove_if
返回值相当于移除满足条件的元素后形成的新向量的end()值。
函数原型:remove_if(v.begin(),v.end(),even);
#include<vector>
#include<algorithm>
#include<iostream>
usingnamespacestd;
booleven(intx)
{
returnx%2?0:1;
}
voidmain()
{
vector<int>v;
for(inti=1;i<=10;i++)
v.push_back(i);
vector<int>::iteratorilocation,result;
cout<<"移除前:";
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<"";
cout<<endl;
result=remove_if(v.begin(),v.end(),even);
cout<<"移除后:";
for(ilocation=v.begin();ilocation!=result;ilocation++)
cout<<*ilocation<<"";
cout<<endl;
}
8剔除连续重复元素unique
函数原型:unique(v.begin(),v.end());
#include<vector>
#include<algorithm>
#include<iostream>
usingnamespacestd;
voidmain()
{
vector<int>v;
v.push_back(2);
v.push_back(6);
v.push_back(6);
v.push_back(6);
v.push_back(9);
v.push_back(6);
v.push_back(3);
vector<int>::iteratorilocation,result;
result=unique(v.begin(),v.end());
for(ilocation=v.begin();ilocation!=result;ilocation++)
cout<<*ilocation<<"";
cout<<endl;
}
输出结果:26963
1、创建堆make_heap
2、元素入堆push_heap(默认插入最后一个元素)
3、元素出堆pop_heap(与push_heap一样,pop_heap必须对堆操作才有意义)
#include<vector>
#include<algorithm>
#include<iostream>
usingnamespacestd;
voidmain()
{
vector<int>v;
v.push_back(5);
v.push_back(6);
v.push_back(4);
v.push_back(8);
v.push_back(2);
v.push_back(3);
v.push_back(7);
v.push_back(1);
v.push_back(9);
make_heap(v.begin(),v.end());
v.push_back(20);
push_heap(v.begin(),v.end());
vector<int>::iteratorilocation;
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<"";
cout<<endl;
pop_heap(v.begin(),v.end());
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<"";
cout<<endl;
}
4堆排序sort_heap
使用:
make_heap(v.begin(),v.end());
sort_heap(v.begin(),v.end());
#include<vector>
#include<algorithm>
#include<iostream>
usingnamespacestd;
voidmain()
{
vector<int>v;
v.push_back(3);
v.push_back(9);
v.push_back(6);
v.push_back(3);
v.push_back(17);
v.push_back(20);
v.push_back(12);
vector<int>::iteratorilocation;
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<"";
cout<<endl;
make_heap(v.begin(),v.end());
sort_heap(v.begin(),v.end());
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<"";
cout<<endl;
}
输出结果:
3963172012
3369121720
5排序sort
函数原型:sort(v.begin(),v.end());
#include<vector>
#include<algorithm>
#include<iostream>
usingnamespacestd;
voidmain()
{
vector<int>v;
v.push_back(2);
v.push_back(8);
v.push_back(-15);
v.push_back(90);
v.push_back(26);
v.push_back(7);
v.push_back(23);
v.push_back(30);
v.push_back(-27);
v.push_back(39);
v.push_back(55);
vector<int>::iteratorilocation;
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<"";
cout<<endl;
sort(v.begin(),v.end());//比较函数默认
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<"";
cout<<endl;
}
相关文章
- 常用的算法和数据结构 面试_数据结构与算法面试题80道
- 操作系统实验一进程调度算法模拟_常用的进程调度算法有
- 常用图像处理算法()[通俗易懂]
- 游戏常用算法-洗牌算法
- JS生成随机数的算法
- 五大常用算法之三:贪心算法[通俗易懂]
- 智能分析网关新增算法分析结果展示列表,支持多方式检索
- RAFT算法详解
- Paxos算法详解
- 10大常用的排序算法(算法分析+动图演示)
- 马拉车算法 (最长回文串 例题 密码截获)----C语言—菜鸟级
- 各种常用排序算法(C/C++,Java)动态显示
- 最新综述 | 图数据挖掘中的算法公平性
- JavaScript算法笔试[通俗易懂]
- 八种常用激光雷达和视觉SLAM算法的评估与比较
- 算法练习之相同的树,对称二叉树详解编程语言
- 展现SQLServer新算法的精彩世界(sqlserver算法)
- 先进先出Oracle调度技术的优势(Oracle先进先出算法)
- 利用Redis实现有序排队算法(排队算法 redis)
- Java常用排序算法及性能测试集合
- php常用算法和时间复杂度
- Javascript实现的数独解题算法网页实例
- 浅析常用分词算法的比较与设想
- stl常用算法(Algorithms)介绍(stl排序算法、非变序型队列)
- PHP冒泡算法详解(递归实现)
- Java中常用的6种排序算法详细分解