C++泛型算法

1.概述

泛型算法位于algorithm，numeric等头部文件内

只读算法：

accumulate(beg,end,start)

count(beg,end,n)

vector<int> ve{1,2,3,4,4,5,6,43,2,1,23,4}; auto beg=ve.cbegin(); auto end=ve.cend(); int sum=accumulate(beg,end,0); cout<<sum<<endl; cout<<count(beg,end,4)<<endl;

写容器算法：

算法不检查写操作

fill(beg,end,s):在[beg,end）范围内写入s;

fill_n(beg,n,s)

vector<int> ve{1,2,3,4,4,5,6,43,2,1,23,4}; auto beg=ve.begin(); auto end=ve.end(); fill(beg,end,2); for(int i:ve){ cout<<to_string(i)+" "; } cout<<endl; vector<int> ve{1,2,3,4,4,5,6,43,2,1,23,4}; auto beg=ve.begin(); auto end=ve.end(); fill_n(beg,5,2); for(int i:ve){ cout<<to_string(i)+" "; } cout<<endl;

上面的n如果过大会导致内存溢出

back_insert:插入迭代器，得到与容器绑定的指向插入位置的迭代器

下面的方法一定不会内存溢出。

vector<int> ve{1,2,3,4,4,5,6,43,2,1,23,4}; auto beg=ve.begin(); auto end=ve.end(); auto it=back_inserter(ve); int i=0; fill_n(it,10,4); for(int i:ve){ cout<<to_string(i)+" "; } cout<<endl;

拷贝算法

copy(begin(a1),end(a1),a2)

拷贝数组

int a1[]={1,2,3,4,5}; int a2[5]; copy(begin(a1),end(a1),a2); for (int i = 0; i < 5; ++i) { cout<<a2[i]<<endl; }

replace(beg,end,oldValue,newValue):

用新值替换迭代器范围内的旧值，不支持正则表达式

vector<string> ve{"aa","bb","cc","dd","ee","dd","cc","bb","aa"}; auto beg=ve.begin(); auto end=ve.end(); replace(beg,end,"aa","xx"); for(auto s:ve){ cout<<s<<endl; }

replace_copy(beg,end,back_inserter(veCopy),“aa”,“xx”):

不改变原容器的值，将改改变后的值拷贝在另一个容器中。

vector<string> ve{"aa","bb","cc","dd","ee","dd","cc","bb","aa"}; vector<string> veCopy; auto beg=ve.begin(); auto end=ve.end(); replace_copy(beg,end,back_inserter(veCopy),"aa","xx"); for(auto s:veCopy){ cout<<s<<" "; } cout<<endl; for(auto s:ve){ cout<<s<<" "; } cout<<endl;

2.排重容器算法

unique(words.begin(),words.end()):

将迭代器范围内的元素重新排列，每个元素只保存一次，返回最后一个不重复元素的之后的一个位置；

#include<algorithm> #include<numeric> using namespace std; void elimDups(vector<string> &); int main() { vector<string> ve={"the","quick","fox","jumps","over","the","slow","red","turtle"}; elimDups(ve); for(string s:ve){ cout<<s<<endl; } } void elimDups(vector<string> &words){ sort(words.begin(),words.end()); auto end_unique=unique(words.begin(),words.end()); words.erase(end_unique,words.end()); }

3.定制操作

sort(iterator,iterator,pred表达式),

传进一个函数，作为排序的依据

#include <iostream> #include <string> #include <vector> #include<algorithm> #include<numeric> using namespace std; void elimDups(vector<string> &); int main() { vector<string> ve={"the","quick","fox","jumps","over","the","slow","red","turtle"}; sort(ve.begin(),ve.end(),[](const string &s1,const string& s2){return s1.size()<s2.size();}); for(string s:ve){ cout<<s<<endl; } }

find_if(ve.begin(),ve.end(),[sz](const string &s){return s.size()>sz;})

下面的find_if找到第一个符合lambda表达式的值，并且使用的捕获值。

#include <iostream> #include <string> #include <vector> #include<algorithm> #include<numeric> using namespace std; void elimDups(vector<string> &); int main() { vector<string> ve={"the","quick","fox","jumps","over","the","slow","red","turtle"}; int sz=4; auto w=find_if(ve.begin(),ve.end(),[sz](const string &s){return s.size()>sz;}); cout<<*w<<endl; /*for(string s:ve){ cout<<s<<endl; }*/ }

for_each(ve.begin(),ve.end(),[](const string &s){cout<<s<<" ";})

for_each对迭代器范围的参数进行lambda表达式内的参数。

#include <iostream> #include <string> #include <vector> #include<algorithm> #include<numeric> using namespace std; void elimDups(vector<string> &); int main() { vector<string> ve={"the","quick","fox","jumps","over","the","slow","red","turtle"}; int sz=4; for_each(ve.begin(),ve.end(),[](const string &s){cout<<s<<" ";}); }

biggest（vector<string> &,vector::size_type）

将容器按长度从小到大排列，并且相同长度单词按照字典顺序。

void biggest(vector<string> &words,vector<string>::size_type sz){ elimDups(words); stable_sort(words.begin(),words.end(),[](const string &a,const string &b){return a.size()<b.size();}); auto wc=find_if(words.begin(),words.end(),[sz](const string &a){return a.size()>=sz;}); auto count=words.end()-wc; cout<<count<<" "<<"words"<<endl; for_each(wc,words.end(),[](const string &s){cout<<s<<" ";}); cout<<endl; } void elimDups(vector<string> &words){ sort(words.begin(),words.end()); auto end_unique=unique(words.begin(),words.end()); words.erase(end_unique,words.end()); }

隐式捕获

count_if(ve.begin(),ve.end(),[=](const string &s){return s.size()>4;})

查找迭代器范围内长度大于4的字符串，=是隐式捕获的写法，表示拷贝，&表示引用

#include <iostream> #include <string> #include <vector> #include<algorithm> #include<numeric> using namespace std; void elimDups(vector<string> &); void biggest(vector<string> &,vector<string>::size_type); int main() { vector<string>::size_type sz=4; vector<string> ve={"the","quick","fox","jumps","over","the","slow","red","turtle"}; auto n=count_if(ve.begin(),ve.end(),[=](const string &s){return s.size()>4;}); cout<<n<<endl; }

auto check_sz=bind(check_size,_1,sz)；

_1在命名空间placeholder中,表示函数check_size第一个参数与sz绑定

使用bind ( )函数将函数和参数绑定

#include <functional> using namespace std; void elimDups(vector<string> &); bool check_size(const string &a,string::size_type sz); void biggest(vector<string> &,vector<string>::size_type); using namespace placeholders; int main() { vector<string>::size_type sz=4; vector<string> ve={"the","quick","fox","jumps","over","the","slow","red","turtle"}; auto check_sz=bind(check_size,_1,sz); auto n=count_if(ve.begin(),ve.end(),check_sz); cout<<n<<endl; } bool check_size(const string &a,string::size_type sz){ return a.size()>sz; } auto isSmaller=bind(compared,_2,_1); cout<<compared(3,1)<<endl; cout<<isSmaller(3,1)<<endl;

4.流迭代器

istream_iterator<int>从输入流获取数据，Int_eof标记流的结尾

#include <iostream> #include <string> #include <vector> #include <list> #include <regex> #include <algorithm> #include <numeric> using namespace std; int main() { istream_iterator<int> int_it(std::cin),int_eof; vector<int> ve(int_it,int_eof); for(int i:ve){ cout<<i<<" "; } }

ostream_iterator

//ostream_iterator<T> out(os) 构造方法，out将类型为T的值写入输入流OS //ostream_iterator<T> out(os,c) 构造方法，out将类型为T的值写入输入流OS，并在每个值后加一个c istream_iterator<int> int_it(std::cin),int_eof; vector<int> ve(int_it,int_eof); ostream_iterator<int> out_iter(cout," "); for (auto e:ve) { //使用迭代器给cout赋值，并将迭代器向后移一位； *out_iter++=e; }

获取文件输入流的迭代器

#include <iostream> #include <fstream> #include <zconf.h> #include <sstream> #include <iterator> #include "resource/PersonInfo.h" using namespace std; int main() { vector<PersonInfo> ve; PersonInfo personInfo; ifstream in("D:/CLProj/IO/resource/a.text"); //得到流的迭代器和尾后迭代器，一旦IO遇到错误或读到文件结尾，迭代器的值就会和尾后迭代器相等； istream_iterator<string> in_iter(in), in_end; while (in_iter!=in_end){ cout<<*in_iter++<<endl; } }

获取文件输出流的迭代器

#include <iostream> #include <fstream> #include <zconf.h> #include <sstream> #include <iterator> #include "resource/PersonInfo.h" using namespace std; int main() { vector<PersonInfo> ve; PersonInfo personInfo; personInfo.setName("何宇"); personInfo.setPhones({"1231221234","12131357624"}); ve.push_back(personInfo); ofstream out("D:/CLProj/IO/resource/a.text",ofstream::app); ostream_iterator<string> in_iter(out," "); for(PersonInfo pI:ve){ *in_iter++=pI.name; for(auto phone:pI.phones) *in_iter++=phone; *in_iter++="\n"; } } 何必 13788889999 13277778888 吴洋 18955557777 13877772222 鲁中 17833332222 17833332222 郭德纲 13922228888 李云 17233339999 18712348976 汪悦 17233332299 18712444476 何世清 18023458921 13476324587 何宇 1231221234 12131357624

反向迭代器

#include <iostream> #include <fstream> #include <zconf.h> #include <sstream> #include <iterator> #include "resource/PersonInfo.h" using namespace std; int main() { // 反向迭代器的结尾指向迭代器开头之前的一个位置 string s("Hello World!"); auto rbeg=s.crbegin(); auto rend=s.crend(); while (rbeg!=rend){ cout<<*rbeg<<" "; ++rbeg; } }

总结：

unique(beg,end) //排重算法 uniuqe(beg,end,comp)//使用comp来比较两个元素是否相等，即调用==来判断是否相等 find(beg,end,val)//在迭代器范围内寻找变量val第一次出现的位置 find_if(beg,end,pred)//查找第一个令pred判断为真的元素 reverse(beg,end)//反转迭代器内的元素 reverse(beg,end,dest)//将反转后的元素拷贝至dest，不改变原来的值； remove_if(beg,end,lambda)//lambda表达式为真，则将迭代器范围内的值移除 remove_if(v1.beg,v1.end,back_inserter(v2),pred)//将移除的元素拷贝到v2中 replace(beg,end,oldValue,newValue)//在迭代器范围内使用新值代替旧值 replace_if(beg,end,pred,newValue)//,如果元素使pred为真在迭代器范围内使用新值代替旧值。 replace_copy_if(beg,end,dest,pred,newValue)//如果元素使pred为真在迭代器范围内使用新值代替旧值,并将旧值拷贝至dest中 list和forward_list容器中的算法： list.merge(list2) 将list2中的元素并入list，并且将List2中的元素删除，两者必须是有序的，合并后使用<排序 list.merge(list2,comp) 将list2中的元素并入list，并且将List2中的元素删除，使用comp中的规则排序 list.remove(val) 删除元素val; list.remove(val,pred),删除使函数为真的元素 list.reverse()，是list的元素反转; list.sort() 按照默认顺序以"<"排序 list.sort(comp) 以comp比较大小排序 list.unique() 删除重复元素 list.unique(comp) 使用给定的二元谓词判断是否相等