STL之涉及到的算法

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>

using namespace std;

 

void main()

{

int num_to_find = 6;

vector<int> v1;

for( int i = 0; i < 10; i++ )

v1.push_back(2*i);

vector<int>::iterator result;

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>

using namespace std;

 

bool divby5(int x)

{

return x%5?0:1;

}

void main()

{

vector<int> v(20);

for(int i=0;i<v.size();i++)

{

v[i]=(i+1)*(i+3);

cout<<v[i]<<‘ ‘;

}

cout<<endl;

vector<int>::iterator ilocation;

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>

using namespace std;

 

void main()

{

vector<int> v1;

cout<<“v1:”;

for(int i=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>::iterator ilocation;

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>

using namespace std;

 

void main()

{

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>::iterator i;

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>

using namespace std;

 

void main()

{

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>::iterator i;

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>

using namespace std;

 

void main()

{

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>::iterator i;

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>

using namespace std;

 

int square(int x)

{

return x*x;

}

void main()

{

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>::iterator i;

for(i=l.begin();i!=l.end();i++)

cout<<*i<<‘ ‘;

cout<<endl;

}

3替换replace

replace算法将指定元素值替换为新值。

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

 

void main()

{

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>::iterator i;

for(i=v.begin();i!=v.end();i++)

cout<<*i<<‘ ‘;

cout<<endl;

}

输出结果为13 100 27 100 29

 

 

4条件替换replace_if

函数原型:replace_if(v.begin(),v.end(),odd,100);

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

 

bool odd(int x)

{

return x%2;

}

void main()

{

vector<int> v;

for(int i=1;i<10;i++)

v.push_back(i);

replace_if(v.begin(),v.end(),odd,100);

vector<int>::iterator ilocation;

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>

using namespace std;

void main()

{

vector<int> v(10);

fill_n(v.begin(),5,-1);

vector<int>::iterator ilocation;

for(ilocation=v.begin();ilocation!=v.end();ilocation++)

cout<<*ilocation<<‘ ‘;

cout<<endl;

}

输出结果:-1 -1 -1 -1 -1 0 0 0 0 0

 

6随机生成n个元素generate

函数原型:generate_n(v.begin(),5,rand);向从v.begin開始的后面5个位置随机填写数据。

 

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

void main()

{

vector<int> v(10);

generate_n(v.begin(),5,rand);

vector<int>::iterator ilocation;

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>

using namespace std;

 

bool even(int x)

{

return x%2?0:1;

}

void main()

{

vector<int> v;

for(int i=1;i<=10;i++)

v.push_back(i);

vector<int>::iterator ilocation,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>

using namespace std;

 

void main()

{

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>::iterator ilocation,result;

result=unique(v.begin(),v.end());

for(ilocation=v.begin();ilocation!=result;ilocation++)

cout<<*ilocation<<‘ ‘;

cout<<endl;

}

输出结果:2 6 9 6 3

 

三、排序算法

1、创建堆make_heap

2、元素入堆push_heap(默认插入最后一个元素)

3、元素出堆pop_heap(与push_heap一样,pop_heap必须对堆操作才有意义)

#include <vector>??????

#include <algorithm>

#include <iostream>

using namespace std;

void main()

{

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>::iterator ilocation;

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>

using namespace std;

void main()

{

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>::iterator ilocation;

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;

}

输出结果:

3 9 6 3 17 20 12

3 3 6 9 12 17 20

5排序sort

函数原型:sort(v.begin(),v.end());

 

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

void main()

{

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>::iterator ilocation;

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;

}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118228.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • docker导出容器为镜像_docker如何将容器打包成镜像

    docker导出容器为镜像_docker如何将容器打包成镜像1、docker镜像、容器导出方式dockersave#IDor#Namedockerexport#IDor#Name2、save和export区别(1)、对于DockerSave方法,会保存该镜像的所有历史记录(2)、对于DockerExport方法,不会保留历史记录,即没有commit历史(3)、dockersave保存的是镜像(image),dockerexport保存的是容器(container);(4)、dockerload用来载入镜像包,dock

  • html表格基础及案例示图代码。[通俗易懂]

    html表格基础及案例示图代码。[通俗易懂]html的表格基础事例图片及代码

  • 傅里叶变换及其实现(MATLAB)

    傅里叶变换及其实现(MATLAB)傅立叶变换傅立叶变换是一种常见的分析方法,傅立叶变换将满足一定条件的函数表示为一些函数的加权和(或者积分)。可以分为四个类别:1.非周期连续性信号对应于傅里叶变换,频域连续非周期2.周期性连续性信号对应于傅立叶级数,频域离散非周期3.非周期离散信号对应于DTFT(离散时间傅立叶变换),频域连续周期4.周期性离散信号对应于D

  • 图的基本算法(BFS和DFS)(转载)

    图的基本算法(BFS和DFS)(转载)

  • 5个最佳拖放式WordPress网页生成器比较(2018)

    5个最佳拖放式WordPress网页生成器比较(2018)你想要一个简单的方法来建立和定制你的WordPress网站?这就是拖放WordPress网页生成器插件派上用场的地方。这些WordPress网页生成器允许您在不编写任何代码的情况下创建、编辑和自定义您的网站布局。在本文中,我们将比较和回顾5个最好的WordPress拖放网页构建器。为什么使用拖放页面生成器的WordPress?当开始一个博客时,许多WordPress初学者发现很难在他们的网站上更改或自定义页面布局。虽然很多优质的WordPress主题都有不同的页面布局,但对于不懂HTML代码的人来说,

  • Config ConnectionStrings

    Config ConnectionStrings<connectionStrings><addname=”MyschoolConnectionString”connectionString=”DataSource=.;InitialCatalog=MySchool1;uid=sa;pwd=123456″/></connectionStrings>stringcon…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号