C++算法与泛型算法(algorithm、numeric)
本文包括的算法有:
- 只读算法:find()、count()、accumulate()、equal()
- 写算法:fill()、fill_n()、back_inserter()、copy()、copy_backward()、replace()、replace_copy()、next_permutation()、prev_permutation()
- 重排元素算法:sort()、stable_sort()、unique()
一、算法简介
大多数算法在头文件algorithm中。标准库还在头文件numeric中定义了一组数值泛型算法
算法是如何工作的:
- 迭代器令算法不依赖于容器类型:算法不依赖于容器所保存的元素类型。只要有一个迭代器可以来访问元素,就可以进行运算
- 但算法依赖于元素类型的操作:虽然迭代器令算法不依赖于容器类型,但大多数算法都是用了一个(多个)元素类型上的操作。例如find用元素类型的==运算符完成每个元素与给定值的比较。其他算法可能要求元素类型支持“<”运算符。不过,我们将看到,大多数算法提供了一种方法,允许我们使用自定义的操作来替代默认的运算符
二、泛型算法
- 标准库提供了超过100个算法,这些算法都对一个范围内的元素来进行操作
- 算法基本上分为3类:是否读取元素、改变元素、重排元素顺序
三、只读算法
- 只可以操作容器元素,不可以改变容器内的值
- 因为是只读,所以建议使用只读迭代器(cbegin()、cend())
find()
- 功能:遍历一个范围中是否包含某元素
- 参数:前2个参数是一个迭代器范围或者指针范围。第3个参数是要查找的元素
- 返回值:成功返回要查找的元素所在的迭代器。失败返回参数2
//判断value在vec中是否存在,因为find如果失败返回的是参数2.所以可以用来判断是否查找成功 vectorvec{1,2,3}; intvalue=2; autoresult=find(vec.cbegin(),vec.cend(),value); cout<<"Thevalue"< vectorvec{"A","B","C"}; autoresult=find(vec.cbegin(),vec.cend(),"B"); cout<<"TheB"<<(result==vec.cend() ?"isnotpresent":"ispresent")< 对数组的操作:可以用内置函数begin()、end()作为数组的迭代器,也可以用指针作为迭代器
intarr[]={1,2,3,4,5}; intval=4; int*result=find(begin(arr),end(arr),val); if(result!=end(arr)){ cout<<"findsucccess,valueis:"<<*result< intarr[]={1,2,3,4,5}; intvalue=3; autoresult=find(arr+1,arr+3,value); cout<<"Thevalue"<count()
- 功能:返回元素在指定迭代器范围内出现的次数
- 返回值:成功返回出现的次数,没有返回0
listli{1,2,3,66,66,66,100}; cout<<"The66countis:" < accumulate()
- 头文件:numeric
- 功能:将指定范围内的元素进行和运算,参数3为和运算的初始值
- 返回值:返回和运算的结果
- 注意:此函数操作的元素必须能够与+运算符进行操作
//计算li元素的和,和的初始值为0 listli{1,2,3}; cout<<"Thesumis:"< 使用string时,必须显示地调用,不能够直接使用字符串,因为这样会被accumulate函数认为是一个constchar*对象而出错
//正确 istli{"A","B","C"}; cout< //错误 listli{"A","B","C"}; cout< //正确 listli{"A","B","C"}; strings="String:"; cout< 附加:如果想要进行别的运行,例如乘、除等,可以使用参数4.例如下面是对一个数组内的元素进行乘操作(备注:初始化不要填0,否则结果就为0)
int*p=newint[4]{1,2,3,4}; cout<())< equal()
- 功能:用来比较两个指定范围内的元素是否都是相同的值(常来比较两个元素是否相同)
- 参数:参数1和参数2指定一个容器的范围。参数3指定另一个容器的开始范围
- 比较规则:将参数1和2指定的范围内的所有元素,查看这些元素是否与参数3所指定的另一个容器的开始处是否都存在(不一定要个数都相同,只要容器1的元素在容器2中都要一一对应)
- 返回值:都相同返回1。不相同返回0
- 因为equal调用迭代器完成操作,所以equal可以用来比较两个不同类型的容器。例如vector
和list 可以进行比较
vectorvec1{1,2}; vector vec2{1,2,3}; vector vec3{1,2,3,4}; vector vec4{1,2,3,4}; cout< vectorvec1{2,3}; vector vec2{1,2,3,4}; cout< vectorvec1{"A","B"}; vector vec2{"B"}; vector vec3{"A","B","C"}; cout< 四、写算法
可以读写容器内的元素,但不可以改变容器的大小。因此操作时要注意容器的大小(例如不能对空容器操作)
因为会改变值,所以不能使用只读迭代器(cbegin()、cend())
fill()
- 用来改变指定位置处的元素
- 参数:参数1、2指定容器的范围,参数3位要设置的值
vectorvec{1,2,3,4,5}; fill(vec.begin(),vec.end(),0);//将vec全部置为0 for(autov=vec.cbegin();v!=vec.cend();v++) cout<<*v< vectorvec{1,2,3,4,5,6}; fill(vec.begin(),vec.begin()+vec.size()/2,66);//将vec的前半部分元素变为66 for(autov=vec.cbegin();v!=vec.cend();v++) cout<<*v< fill_n()
- 用来将指定数量的元素变为某个值
- 参数:参数1为迭代器起始位置。参数2为要改变的元素个数。参数3为要设定的值
- 注意:要注意参数2的设定,不能超出容器的大小,也不能对空容器操作
vectorvec{1,2,3,4,5,6}; fill_n(vec.begin(),3,66);//将vec的前3个元素变为66 for(autov=vec.cbegin();v!=vec.cend();v++) cout<<*v< //下面代码不会出错,但是也不会有效果,因为vec是空向量 vectorvec; fill_n(vec.begin(),vec.size(),66); for(autov=vec.cbegin();v!=vec.cend();v++)//不打印任何信息 cout<<*v< back_inserter()
- 又名插入迭代器
- 参数:为一个容器的引用
- 返回值:返回与该容器绑定的插入迭代器
- 功能:常用来返回一个容器的迭代器,然后对此迭代器进行操作
- 当我们通过返回的插入迭代器赋值时,会自动调用push_back将一个具有给定值的元素添加到容器中
- 头文件iterator
vectorvec;//空容器 autoit=back_inserter(vec);//返回vec的第一个迭代器 *it=42;//此时vec有了一个元素,值为42 现在我们可以使用fill_n来给一个空容器赋值:在每次迭代中,back_inserter返回迭代器,因此每次赋值都会在vec上调用push_back,因此fill_n就能够操作了。下面是在vec的末尾添加10个新的元素
vectorvec; fill_n(back_inserter(vec),10,0);//通过back_inserter创建一个插入迭代器,然后可以向vec添加元素了 for(autov=vec.cbegin();v!=vec.cend();v++)//打印10个0 cout<<*v< copy()
- 将参数1、2指定范围的元素拷贝给参数3指定的容器
- 参数:参数1、2为一个容器的范围。参数3要接受拷贝的容器起始位置
- 注意:参数3要有足够的空间保存拷贝的数据
- 返回值:返回拷贝目的位置的迭代器值
intarr1[]={1,2,3}; intarr2[sizeof(arr1)/sizeof(*arr1)]; autoret=copy(begin(arr1),end(arr1),arr2);//将数组1拷贝给数组2。ret为arr2数组最后元素的下一个位置 for(autoi=0;icopy_backward
- 该函数与copy的不同之处在于:
- copy是从第一个元素开始拷贝,而copy_backward是从最后一个元素开始拷贝
- copy的第3个参数是接受拷贝的容器起始位置,而copy_backward是目的序列的结束迭代器
- 会复制前两个迭代器参数指定的序列。第三个参数是目的序列的结束迭代器
replace()
- 将指定范围内指定的元素替换为另一个值
- 参数:1、2指定替换的范围。3:目标值,4:替换后的值
vectorvec{1,0,0,0,5}; replace(vec.begin(),vec.end(),0,66);//将vec中为0的全部替换为66 for(autov=vec.cbegin();v!=vec.cend();v++){ cout<<*v< replace_copy()
- 此函数会保留原容器不变,然后将替换后的结果保存在另一个容器中
- 参数:参数12位要替换的范围。参数3位另一个容器的起始位置。参数4目标值。参数5替换后的值
vectorvec{1,0,0,0,5}; vector vec2; replace_copy(vec.begin(),vec.end(),back_inserter(vec2),0,66);//vec的元素保持不变,vec2为替换后的值 for(autov=vec2.cbegin();v!=vec2.cend();v++){ cout<<*v< next_permutation()
- 功能:对一个迭代区间的数值进行全排列
- 返回值:会根据前面next_permutation函数的调用,当操作的区间不存在下一个排列时,函数返回false;否则如果可以继续进行全排列,那么就返回true
//函数原型 #includeboolnext_permutation(iteratorstart,iteratorend) 演示案例:下面的程序每调用一次next_permutation就会对我们制定的迭代区间进行一次排列,直到得出全部排列之后,返回false
int*p=newint[3]{1,2,3}; do{ for(inti=0;i<3;++i){ cout<
prev_permutation()
- 与next_permutation的功能显示,区别就是prev_permutation是求当前排列的前一个排列,而next_permutation是求当前排列的下一个排列
五、重排元素算法
sort()、unqie()、stable_sort()
因为会改变值,所以不能使用只读迭代器(cbegin()、cend())
sort()
- 将容器内的元素按照运算符“<”的规则排序,从小到大
- 参数:一个容器的迭代器范围
vectorvec{1,4,2,8,4,1}; sort(vec.begin(),vec.end());//将vec的值从小到大排序 for(autov=vec.cbegin();v!=vec.cend();v++){ cout<<*v< unique()
- 相邻之间如果有重复相同的元素,则删除重复的元素只保留一个
- 参数:一个容器的迭代器范围
- 返回值:返回删除重复元素之后的最后一个元素的后一个位置
- 注意(重点):虽然删除了元素,但是容器的大小依然没有变,迭代器也没有变。所有变为迭代器时一定要注意
vectorvec{1,1,2,3,4,4,4,5,1}; autoend_unique=unique(vec.begin(),vec.end()); //for循环时使用unique的返回值,如果使用vec.cend(),那么会打印后面没有元素位置的乱值 for(autov=vec.cbegin();v!=end_unique;v++){ cout<<*v< stable_sort()
- 也是排序
- 如果非字符串,就先按照数值的个数排序,个数相同时再按照大小排序
- 如果是字符串:按照长度排序,长度相同的按照字典排序
vectorvec{1,10,2,100,4,1}; stable_sort(vec.begin(),vec.end()); //1,1,2,4,10,100 for(autov=vec.cbegin();v!=vec.cend();v++){ cout<<*v< 六、向算法传递函数和lambda表达式
注意事项:
向算法传递函数或者lambda表达式时要注意。该算法支持调用一元谓词(参数)还是多元谓词(参数)
例如:find_if的第3个参数传递的函数/lambda只接受一个参数,如果是两个参数的函数或lambda,那么就不能调用(后面会介绍bind函数解决这个问题)
sort()
boolisMin(constint&s1,constint&s2){ returns1s2; } vector vec{1,2,3,4,5}; sort(vec.begin(),vec.end(),isMin);//从小到大排序 sort(vec.begin(),vec.end(),isMax);//从大到小排序 //使用lambda表达式 sort(vec.begin(),vec.end(), [](constint&a,constint&b){returnab;});//从大到小排序 stable_sort()
//按照长度排序,长度相同的按照字典排序 boolisShorter(conststring&s1,conststring&s2){ returns1.size()vec{"fox","jumps","over","quick","res","slow","the","turtle"}; stable_sort(vec.begin(),vec.end(),isShorter); for(autov=vec.cbegin();v!=vec.cend();v++){ cout<<*v< find_if()
- 用来在指定范围内查找比指定值大/下的元素
- 如果是大于(那么就是最大的那个)。如果是小于(那么就是比他小一个的那个)
- 参数3:为一个函数指针或者lambda表达式
- 返回值:存在就返回这个值,不存在返回尾迭代器
vectorvec{1,2,3,4,5}; intsz=4; //在vec中寻找比sz大的数 autowc=find_if(vec.begin(),vec.end(), [sz](constint&a){returna>sz;});//查找比sz大的 autowc2=find_if(vec.begin(),vec.end(), [sz](constint&a){returna for_each()
- 用来遍历一个集合
- 参数:参数12是一个容器的迭代器范围。参数3lambda表达式
vectorvec{1,2,3,4,5}; for_each(vec.begin(),vec.end(), [](constint&s){cout< vectorvec{"ABC","AB","A","sd"}; for_each(vec.begin(),vec.end(), [](conststring&s){cout< transform()
- 参数:参数12为输入序列。参数3为目的位置
- 该算法对输入序列中每个元素调用课调用对象,并将结果写到目的位置
- 下面使用transform算法和一个lambda表达式来将vector中的每个负数替换为绝对值。因为参数3位vec.begin(),所以就是将vec的全部元素取绝对值然后再写入vec的开头
vectorvec{-1,-2,-3,4}; //将vec的数全部取绝对值 transform(vec.begin(),vec.end(),vec.begin(), [](inti){returni<0?-i:i;}); for(autov=vec.begin();v!=vec.end();++v) cout<<*v< 到此这篇关于C++算法与泛型算法(algorithm、numeric)的文章就介绍到这了,更多相关C++algorithmnumeric内容请搜素毛票票以前的文章或下面相关文章,希望大家以后多多支持毛票票!
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。