首页 > 代码库 > 【转】STL算法 <algorithm>中各种算法解析

【转】STL算法 <algorithm>中各种算法解析

原文:http://blog.csdn.net/tianshuai1111/article/details/7674327

一,巡防算法

        for_each(容器起始地址,容器结束地址,要执行的方法) 

#include <iostream>#include <algorithm>#include <vector>using namespace std;template<class T>struct plus2{    void operator()(T&x)const    {        x+=2;    }    };void printElem(int& elem){  cout << elem << endl;}

 

二,find算法

   int *find(int *begin,int *end,int  value)

   前闭后合的区间 begin,end中,查找value如果查找到了就返回第一个符合条件的元素,否则返回end指针

#include <iostream>#include <algorithm>using namespace std;void printElem(int& elem){  cout << elem << endl;}int main(){    int ia[]={0,1,2,3,4,5,6};        int *i= find(ia,ia+7,9);//在整个数组中查找元素 9     int *j= find(ia,ia+7,3);//在整个数组中查找元素 3    int *end=ia+7;//数组最后位置     if(i == end)        cout<<"没有找到元素 9"<<endl;    else        cout<<"找到元素9"<<endl;           if(j == end)        cout<<"没有找到元素 3"<<endl;    else        cout<<"找到元素"<<*j<<endl;    return 0;}

 

 

三,数值算法

        包含在<numeric>头文件中

#include <iostream>#include <numeric>  //数值算法 #include <vector>#include <functional> #include <iterator> #include <math.h>  using namespace std;  int main() {     int ia[]={1,2,3,4,5};     vector<int> iv(ia,ia+5);          cout<<accumulate(iv.begin(),iv.end(),0)<<endl; //累加  初值为0      cout<<accumulate(iv.begin(),iv.end(),0,minus<int>())<<endl; //累加 符号位负         cout<<inner_product(iv.begin(),iv.end(),iv.begin(),10)<<endl;//两个数组内积  初值为10     cout<<inner_product(iv.begin(),iv.end(),iv.begin(),10,minus<int>(),plus<int>())<<endl;//10-(1+1)-(2+2)        ostream_iterator<int> oite(cout," ");//迭代器绑定到cout上作为输出使用    partial_sum(iv.begin(),iv.end(),oite);//依次输出前n个数的和         cout<<endl;     partial_sum(iv.begin(),iv.end(),oite,minus<int>());//依次输出第一个数减去(除第一个数外到当前数的和)        cout<<endl;     adjacent_difference(iv.begin(),iv.end(),oite); //输出相邻元素差值 前面-后面        cout<<endl;     adjacent_difference(iv.begin(),iv.end(),oite,plus<int>()); //输出相邻元素差值 前面+后面  。前面更改影响后面元素               cout<<endl;     cout<<pow(10,3)<<endl; // 平方        /*  VC 不支持   只有安装了才SGI STL支持     int n=3;    iota(iv.begin(),iv.end(),n);//在指定区间填入n  n+1 n+2    for(int i=0;i<iv.size();++i)        cout<<iv[i]<<" ";                 */      return 0; } 

 

四,基本算法

#include <iostream>#include <algorithm>#include <vector>using namespace std;template<typename T>struct display{    void operator()(const T  &x)const    {        cout<<x<<" ";    }    };int main(){    int ia[]={0,1,2,3,4,5,6,7,8};    vector<int> iv1(ia,ia+5);    vector<int> iv2(ia,ia+9);        pair<vector<int>::iterator,vector<int>::iterator> pa;    pa=mismatch(iv1.begin(),iv1.end(),iv2.begin());    cout<<"两个数组不同点--第一个数组点:"<<*(pa.first)<<endl; //这样写很危险,应该判断是否到达end     cout<<"两个数组不同点--第二个数组点:"<<*(pa.second)<<endl;        //更改之后    if(pa.first == iv1.end())        cout<<"第一个数组与第二个数组匹配"<<endl;             cout<<equal(iv1.begin(),iv1.end(),iv2.begin())<<endl;// 1 表示 相等,因为只比较跟 iv1长度大小的数组     cout<<equal(iv1.begin(),iv1.end(),&ia[3])<<endl;// 0 表示 不相等     cout<<equal(iv1.begin(),iv1.end(),&ia[3],less<int>())<<endl;// 1 表示 前者小于后者        fill(iv1.begin(),iv1.end(),9);//将iv1区间内填满 9    for_each(iv1.begin(),iv1.end(),display<int>());    cout<<endl;             fill_n(iv1.begin(),3,6);//从iv1区间开始填 3个6     for_each(iv1.begin(),iv1.end(),display<int>());    cout<<endl;            vector<int>::iterator ite1=iv1.begin();    vector<int>::iterator ite2=ite1;    advance(ite2,3);//向前跳3个        iter_swap(ite1,ite2);//交换迭代器指向的元素    for_each(iv1.begin(),iv1.end(),display<int>());         cout<<"\nmax:"<<max(*ite1,*ite2)<<endl;    cout<<"min:"<<min(*ite1,*ite2)<<endl;        swap(*ite1,*ite2);    for_each(iv1.begin(),iv1.end(),display<int>());            cout<<endl;    string stra1[]={"a","b","c"};    string stra2[]={"d","e","f"};        cout<<lexicographical_compare(stra1,stra1+2,stra2,stra2+2)<<endl;//按照字典序 前者小于后者     cout<<lexicographical_compare(stra1,stra1+2,stra2,stra2+2,greater<string>())<<endl;//按照字典序 前者不大于后者                return 0;}

 

 

五,copy()对不同容器复制;关于输出区间与输入区间重叠的讨论

#include <iostream>#include <algorithm>#include <deque>using namespace std;template<class T>struct display{    void operator()(const T &x)const    {        cout<<x<<" ";    }};int main(){    //以下复制区间没有问题     int ia1[]={0,1,2,3,4,5,6,7,8};    copy(ia1+2,ia1+7,ia1);//将下标2-6复制给 1-5    for_each(ia1,ia1+9,display<int>()); //2,3,4,5,6,5,6,7,8    cout<<endl;         //输出区间的起点与输入区间重叠,可能会有问题。但本例copy采用memmove()执行实际复制操作     int ia2[]={0,1,2,3,4,5,6,7,8};    copy(ia2+2,ia2+7,ia2+4);//将下标2-6复制给 4-8    for_each(ia2,ia2+9,display<int>()); //0,1,2,3,2,3,4,5,6    cout<<endl;        //以下复制区间没有问题     int ia3[]={0,1,2,3,4,5,6,7,8};    deque<int> id(ia3,ia3+9);    deque<int>::iterator first=id.begin();    deque<int>::iterator last=id.end();    deque<int>::iterator result=id.begin();    ++++first;    cout<<*first<<endl;    ----last;    cout<<*last<<endl;    cout<<*result<<endl;    copy(first,last,result);    for_each(id.begin(),id.end(),display<int>());//2,3,4,5,6,5,6,7,8    cout<<endl;        //以下复制区间存在问题,由于实际复制没有采用memove(),结果错误     int ia4[]={0,1,2,3,4,5,6,7,8};    deque<int> ide(ia4,ia4+9);    deque<int>::iterator first1=ide.begin();    deque<int>::iterator last1=ide.end();    deque<int>::iterator result1=ide.begin();    advance(result1,4);//注意这里跟上面不一样     ++++first1;    cout<<*first1<<endl;    ----last1;    cout<<*last1<<endl;    cout<<*result1<<endl;    copy(first1,last1,result1);    for_each(ide.begin(),ide.end(),display<int>());// 0,1,2,3,2,3,2,3,2不是预期的 0,1,2,3,2,3,4,5,6    cout<<endl;                return 0;} 

 

【注意】如果以vector 容器替代deque容器则每种情况都正确,因为vector迭代器其实是个源生指针,调用的copy()算法以mommove()执行实际复制。

                copy_backward(first,last,result);  //逆向复制,将迭代器first - last位置的元素逆向复制到 从result-1开始的逆向区间

 

补充:

        原型:void *memmove( void  * dest, const   void  * src, size_t  count );

 

  用法:#include <string.h>或#include <memory.h>

 

  功能:由src所指内存区域复制count个字节到dest所指内存区域。

 

  说明:src和dest所指内存区域可以重叠,但复制后dest内容会被更改。函数返回指向dest的指针。采取先拷贝再复制的方式,有效解决了dest和src区域重叠问题

 

  相关函数:memset、memcpy、strcpy 参考博文http://blog.csdn.net/tianshuai11/article/details/7624419

 

实例

#include <stdio.h>#include <string.h>int main(){  char s[]="Golden Global View";   memmove(s,s+7,strlen(s)+1-7);   printf("%s",s);      return 0;}

 

六,Set方法

#include <iostream>#include <set>#include <algorithm>#include <iterator>using namespace std;template <class T>struct display{    void operator()(const T &x)    {        cout<<x<<" ";    }    };int main(){    int ia1[]={1,3,5,7,9,11};    int ia2[]={1,1,2,3,5,8,13};        multiset<int> s1(ia1,ia1+6);    multiset<int> s2(ia2,ia2+7);    for_each(s1.begin(),s1.end(),display<int>());    cout<<endl;    for_each(s2.begin(),s2.end(),display<int>());    cout<<endl;        multiset<int>::iterator first1 = s1.begin();    multiset<int>::iterator last1 = s1.end();    multiset<int>::iterator first2 = s2.begin();    multiset<int>::iterator last2 = s2.end();        cout<<"union of s1 and s2: ";    //两个集合合并,相同元素个数取 max(m,n)。     set_union(first1,last1,first2,last2,ostream_iterator<int>(cout," "));    cout<<endl;        first1=s1.begin();    first2=s2.begin();    cout<<"Intersection of s1 and s2: ";    //两个集合交集,相同元素个数取 min(m,n).    set_intersection(first1,last1,first2,last2,ostream_iterator<int>(cout," "));     cout<<endl;        first1=s1.begin();    first2=s2.begin();    cout<<"Intersection of s1 and s2: ";    //两个集合差集 就是去掉S1中 的s2     set_difference(first1,last1,first2,last2,ostream_iterator<int>(cout," "));     cout<<endl;         first1=s1.begin();    first2=s2.begin();    cout<<"Intersection of s1 and s2: ";    //两个集合对称差集:就是取两个集合互相没有的元素 。两个排序区间,元素相等指针后移,不等输出小的并前进     //相同元素的个数 abs(m-n)     set_symmetric_difference(first1,last1,first2,last2,ostream_iterator<int>(cout," "));     cout<<endl;            return 0;}

 

 七,其他算法(运算逻辑相对单纯的算法)

#include <iostream>#include <algorithm>#include <vector>#include <functional>#include <vector> using namespace std;template <class T>struct display{    void operator()(const T &x)const    {        cout<<x<<" ";     }     }; struct even{    bool operator()(int x)const    {        return x%2?false:true;     } };class even_by_two{private:    static int _x; //注意静态变量 public:    int operator()()const    {        return _x+=2;     }         };int even_by_two::_x=0; int main(){    int ia[]={0,1,2,3,4,5,6,6,6,7,8};    vector<int> iv(ia,ia+sizeof(ia)/sizeof(int));        //找出iv之中相邻元素值相等的第一个元素     cout<<*adjacent_find(iv.begin(),iv.end())<<endl;      cout<<*adjacent_find(iv.begin(),iv.end(),equal_to<int>())<<endl; //仿函数        cout<<count(iv.begin(),iv.end(),6)<<endl;//统计6的个数     cout<<count_if(iv.begin(),iv.end(),bind2nd(less<int>(),7))<<endl;//统计小于7的元素的个数 :9个        cout<<*find(iv.begin(),iv.end(),4)<<endl; //返回元素为4的元素的下标位置        cout<<*find_if(iv.begin(),iv.end(),bind2nd(greater<int>(),2))<<endl; //返回大于2的第一个元素的位置:3        vector<int> iv2(ia+6,ia+8);//6 6        for(int i=0;i<iv2.size();++i)      cout<<iv2[i]<<" ";           cout<<endl;     //返回iv序列中 iv2序列 出现的最后一个位置(再往后三个位置的值):8     cout<<"find_end:"<<*(find_end(iv.begin(),iv.end(),iv2.begin(),iv2.end())+3)<<endl;      //返回iv序列中 iv2序列 出现的最后一个位置(再往后三个位置的值):7    cout<<"find_first_of:"<<*(find_first_of(iv.begin(),iv.end(),iv2.begin(),iv2.end())+3)<<endl;              for_each(iv.begin(),iv.end(),display<int>());      cout<<endl;          //遍历整个iv2区间并执行 even_by_two操作      generate(iv2.begin(),iv2.end(),even_by_two());     for_each(iv2.begin(),iv2.end(),display<int>());      cout<<endl;          //遍历区间(给出起点和长度),对每个遍历元素执行even_by_two操作      generate_n(iv.begin(),3,even_by_two());     for_each(iv.begin(),iv.end(),display<int>()); //由于_X是static 所以接着 增长      cout<<endl;          //删除元素6 尾端可能有残余数据      remove(iv.begin(),iv.end(),6);     for_each(iv.begin(),iv.end(),display<int>()); //由于_X是static 所以接着 增长      cout<<endl; //8 10 3 4 5 7 8 6 6 7 8 (最后四个是残留数据)            //去除value 然后将一个容器的元素复制到另一个 容器。仍然可能有残留元素       vector<int> iv3(12);//重新申请空间      remove_copy(iv.begin(),iv.end(),iv3.begin(),6);      for_each(iv3.begin(),iv3.end(),display<int>()); //由于_X是static 所以接着 增长       cout<<endl; //8 10 3 4 5 7 8 7 8 0 0 (最后两个是残留元素)             //将小于6的元素 "删除" iv 此时为 8 10 3 4 5 7 8 6 6 7 8       remove_if(iv.begin(),iv.end(),bind2nd(less<int>,6));      for_each(iv1.begin(),iv1.end(),display<int>()); //由于_X是static 所以接着 增长       cout<<endl; //8 10 7 8 6 6 7 8 6 7 8 (最后三个是残留元素)                   //将小于7的元素 "删除"  iv3元素:8 10 3 4 5 7 8 7 8 0 0 (最后两个是残留元素)      remove_copy_if(iv.begin(),iv.end(),iv3.begin(),bind2nd(less<int>,7));      for_each(iv3.begin(),iv3.end(),display<int>()); //由于_X是static 所以接着 增长       cout<<endl; //8 10 7 8 7 8 7 8 8 0 0(最后三个残留元素)                    return 0; } 

 

 

第二段算法示例:

#include <iostream>#include <algorithm>#include <vector>#include <functional>using namespace std;template <class T>struct display{    void operator()(const T &x)const    {        cout<<x<<" ";     }     };  int main(){    int ia[]={8,10,7,8,6,6,7,8,6,7,8};    vector<int> iv(ia,ia+sizeof(ia)/sizeof(int));        //将容器中6 替换为 3     replace(iv.begin(),iv.end(),6,3);    for_each(iv.begin(),iv.end(),display<int>()); //由于_X是static 所以接着 增长     cout<<endl; //iv:8 10 7 8 3 3 7 8 3 7 8         vector<int> iv2(12);     //将容器中3 替换为 5 放入另一个容器     replace_copy(iv.begin(),iv.end(),iv2.begin(),3,5);    for_each(iv2.begin(),iv2.end(),display<int>()); //由于_X是static 所以接着 增长     cout<<endl; //iv2:8 10 7 8 5 5 7 8 5 7 8 0(最后y一个残留元素)           //将容器中小于 5 替换为 2     replace_if(iv.begin(),iv.end(),bind2nd(less<int>(),5),2);    for_each(iv.begin(),iv.end(),display<int>()); //由于_X是static 所以接着 增长     cout<<endl; //iv:8 10 7 8 2 5 7 8 2 7 8     //将容器中小于 5 替换为 2     replace_copy_if(iv.begin(),iv.end(),iv2.begin(),bind2nd(equal_to<int>(),8),9);    for_each(iv2.begin(),iv2.end(),display<int>()); //由于_X是static 所以接着 增长     cout<<endl; //iv2:9 10 7 8 2 5 7 9 2 7 8 0(最后一个残留元素)         //逆向重排每一个元素 (倒置)     reverse(iv.begin(),iv.end());     for_each(iv.begin(),iv.end(),display<int>());    cout<<endl; //iv:8 7 2 8 7 5 2 8 7 10 8        //逆向重排每一个元素 (倒置)     reverse_copy(iv.begin(),iv.end(),iv2.begin());     for_each(iv2.begin(),iv2.end(),display<int>());    cout<<endl; //iv2:8 10 7 8 2 5 7 8 2 7 8 0 (最后一个残留元素)         // 互换元素  [bigin,middle)  [middle,end)     rotate(iv.begin(),iv.begin()+4,iv.end());    for_each(iv.begin(),iv.end(),display<int>());    cout<<endl;//iv:7 2 2 8 7 10 8 8 7 2 8               // 互换元素  [bigin,middle)  [middle,end)     rotate_copy(iv.begin(),iv.begin()+5,iv.end(),iv2.begin());    for_each(iv2.begin(),iv2.end(),display<int>());    cout<<endl;//iv2:10 8 8 7 2 8 7 2 2 8 7 0 (最后一个是残留元素)             //在iv中查找 子序列 2 8 第一次出现的位置的元素     int ia2[3]={2,8};    vector<int> iv3(ia2,ia2+2);    cout<<*search(iv.begin(),iv.end(),iv3.begin(),iv3.end())<<endl; //2         //在iv中查找 2个8 出现的第一个位置的元素     cout<<*search_n(iv.begin(),iv.end(),2,8)<<endl; //8         //在iv中查找 3个小于8 出现的第一个位置的元素     cout<<*search_n(iv.begin(),iv.end(),3,8,less<int>())<<endl; //7        swap_ranges(iv3.begin(),iv3.end(),iv.begin());    cout<<"iv:";     for_each(iv.begin(),iv.end(),display<int>());//iv:2 8 2 8 7 10 8 8 7 2 8     cout<<endl;    cout<<"iv3:";     for_each(iv3.begin(),iv3.end(),display<int>()); //iv3: 7 2     cout<<endl;          //全部减2     transform(iv.begin(),iv.end(),iv.begin(),bind2nd(minus<int>(),2));    for_each(iv.begin(),iv.end(),display<int>());//0 6 0 6 5 8 6 6 5 0 6     cout<<endl;          //两个区间元素相加然后放到 iv上     transform(iv.begin(),iv.end(),iv.begin(),iv.begin(),plus<int>());    for_each(iv.begin(),iv.end(),display<int>());    cout<<endl; //0 12 0 12 10 16 12 12 10 0 12                return 0; } 

 

 



第三段算法示例:

 

#include <iostream>#include <algorithm>#include <vector>#include <functional>using namespace std;template <class T>struct display{    void operator()(const T &x)const    {        cout<<x<<" ";     }     }; struct even{    bool operator()(int x)const    {        return x%2?false:true;     } }; int main(){    int ia[]={0,1,2,3,4,5,6,6,6,7,8};    vector<int> iv(ia,ia+sizeof(ia)/sizeof(int));    vector<int> iv2(ia+4,ia+8);//4 5 6 6    vector<int> iv3(15);        cout<<*max_element(iv.begin(),iv.end())<<endl;    cout<<*min_element(iv.begin(),iv.end())<<endl;     //判断iv2中元素是否都出现在 iv中     cout<<includes(iv.begin(),iv.end(),iv2.begin(),iv2.end())<<endl;          //iv 和iv2合并到iv3中     merge(iv.begin(),iv.end(),iv2.begin(),iv2.end(),iv3.begin());     for_each(iv3.begin(),iv3.end(),display<int>());    cout<<endl;         //符合条件的 放到前面,不符合条件的放到后面     partition(iv3.begin(),iv3.end(),even());    for_each(iv3.begin(),iv3.end(),display<int>());    cout<<endl;         //去除连续并且重复的元素     unique(iv.begin(),iv.end());     for_each(iv.begin(),iv.end(),display<int>());    cout<<endl;             //去除连续并且重复的元素     unique_copy(iv.begin(),iv.end(),iv3.begin());     for_each(iv3.begin(),iv3.end(),display<int>());    cout<<endl;                return 0; } 

 

八,复杂算法示例(解释在源码中)

 

#include <iostream>#include <vector>#include <functional>#include <algorithm>using namespace std;struct even //是否是奇数 {    bool operator()(int x)const    {        return x%2?false:true;     }     }; template<class T> struct display{    void operator()(T &x)const    {        cout<<x<<" ";     }     }; int main(){    int ia[] = {12,17,20,22,23,30,33,40};    vector<int> iv(ia,ia+sizeof(ia)/sizeof(int));        //返回可以插入的第一个位置     cout<<*lower_bound(iv.begin(),iv.end(),21)<<endl; //22     cout<<*upper_bound(iv.begin(),iv.end(),21)<<endl; //22     //返回可以插入的最后一个位置     cout<<*lower_bound(iv.begin(),iv.end(),22)<<endl; //22     cout<<*upper_bound(iv.begin(),iv.end(),22)<<endl; //23        //二分查找某个元素,返回是否找到     cout<<binary_search(iv.begin(),iv.end(),33)<<endl; //1    cout<<binary_search(iv.begin(),iv.end(),34)<<endl; //0          //生成下一个排列组合(字典序)     next_permutation(iv.begin(),iv.end());     for_each(iv.begin(),iv.end(),display<int>());    cout<<endl;          prev_permutation(iv.begin(),iv.end());     for_each(iv.begin(),iv.end(),display<int>());    cout<<endl;         //打乱顺序     random_shuffle(iv.begin(),iv.end());     for_each(iv.begin(),iv.end(),display<int>());    cout<<endl;        //找出最小的4个元素 放在前四个 后面顺序不一定有序     partial_sort(iv.begin(),iv.begin()+4,iv.end());     for_each(iv.begin(),iv.end(),display<int>());    cout<<endl;        //排序(缺省为递增排序)     sort(iv.begin(),iv.end());    for_each(iv.begin(),iv.end(),display<int>());    cout<<endl;         //排序(设置为递减)     sort(iv.begin(),iv.end(),greater<int>());    for_each(iv.begin(),iv.end(),display<int>());    cout<<endl;        iv.push_back(22);    iv.push_back(30);    iv.push_back(17);            //排序并保持原相对位置     stable_sort(iv.begin(),iv.end());     for_each(iv.begin(),iv.end(),display<int>());    cout<<endl;//12 17 17 20 22 22 23 30 30 33 40         pair<vector<int>::iterator,vector<int>::iterator> pairIte;    //返回等于22的一个小区间     pairIte = equal_range(iv.begin(),iv.end(),22);     cout<<*(pairIte.first)<<endl;//lowerbound 22     cout<<*(pairIte.second)<<endl; //upperbound 23            //这里返回一个空区间     pairIte = equal_range(iv.begin(),iv.end(),25);     cout<<*(pairIte.first)<<endl;//lowerbound 30     cout<<*(pairIte.second)<<endl; //upperbound 30          //打乱顺序     random_shuffle(iv.begin(),iv.end());     for_each(iv.begin(),iv.end(),display<int>());    cout<<endl;        //将小于iv.begin+5的放到左边     nth_element(iv.begin(),iv.begin()+5,iv.end());     for_each(iv.begin(),iv.end(),display<int>());    cout<<endl;        //将小于iv.begin+5的放到右边     nth_element(iv.begin(),iv.begin()+5,iv.end(),greater<int>());     for_each(iv.begin(),iv.end(),display<int>());    cout<<endl;        //排序     stable_sort(iv.begin(),iv.end(),even());    for_each(iv.begin(),iv.end(),display<int>());    cout<<endl;            return 0; }