【C++STL】アルゴリズムにおける各種アルゴリズム解析

転自:アルゴリズム内の各種アルゴリズム解析
一、巡回防止アルゴリズム

    for_each(      ，      ，      )

#include 
#include 
#include 

using namespace std;

template<class T>
struct plus2
{
    void operator()(T&x)const
    {
        x+=2;
    }

};

void printElem(int& elem)
{
  cout << elem << endl;
}
int main()
{
    int ia[]={0,1,2,3,4,5,6};
    for_each(ia,ia+7,printElem);//  

    int ib[]={7,8,9,10,11,12,13};
    vector<int> iv(ib,ib+7);
    for_each(iv.begin(),iv.end(),plus2<int>());//    
    for_each(iv.begin(),iv.end(),printElem);//  


    return 0;
}

二、findアルゴリズム
int *find(int *begin,int *end,int value)
前閉後合の区間begin,endでは、検索valueが検索されたら最初の条件に合致する要素を返し、そうでなければendポインタを返します.

#include 
#include 

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"<else 
       cout<<"    9"<if(j == end) 
       cout<<"       3"<else 
       cout<<"    "<return 0;
}

三、数値アルゴリズム

#include 
#include   //     
#include 
#include  
#include  

#include  
 using namespace std;

 int main()
 {
    int ia[]={1,2,3,4,5};
    vector<int> iv(ia,ia+5);

    cout<0)<//       0 
    cout<0,minus<int>())<//       

    cout<10)<//           10 
    cout<10,minus<int>(),plus<int>())<//10-(1+1)-(2+2)

    ostream_iterator<int> oite(cout," ");//      cout       
    partial_sum(iv.begin(),iv.end(),oite);//     n     

    cout<int>());//          （            ）

    cout<//           -  

    cout<int>()); //           +    。           


    cout<cout<<pow(10,3)<//   

    /*  VC             SGI STL   
    int n=3;
    iota(iv.begin(),iv.end(),n);//       n  n+1 n+2
    for(int i=0;i 
    return 0;
 }

四、基本アルゴリズム

#include 
#include 
#include 

using namespace std;

template<typename T>
struct display
{
    void operator()(const T  &x)const
    {
        cout<" ";
    }

};
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<<"       --      :"<//      ，        end 
    cout<<"       --      :"<//    
    if(pa.first == iv1.end())
        cout<<"             "<cout<// 1      ，       iv1        
    cout<3])<// 0        
    cout<3],less<int>())<// 1          

    fill(iv1.begin(),iv1.end(),9);// iv1      9
    for_each(iv1.begin(),iv1.end(),display<int>());
    cout<3,6);// iv1      3 6 
    for_each(iv1.begin(),iv1.end(),display<int>());
    cout<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<<"
max:"<cout<<"min:"<int>());


    cout<string stra1[]={"a","b","c"};
    string stra2[]={"d","e","f"};

    cout<2,stra2,stra2+2)<//             
    cout<2,stra2,stra2+2,greater<string>())<//             


    return 0;
}

五、copy()は異なる容器に対して複製する;出力区間と入力区間が重なることについての討論

#include 
#include 
#include 

using namespace std;
template<class T>
struct display
{
    void operator()(const T &x)const
    {
        cout<" ";
    }
};
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<//              ，      。   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<//           
    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<cout<cout<int>());//2,3,4,5,6,5,6,7,8
    cout<//          ，          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<cout<cout<int>());// 0,1,2,3,2,3,2,3,2      0,1,2,3,2,3,4,5,6
    cout<return 0;
} 

【注意】dequeコンテナの代わりにvectorコンテナを使用する場合、vector反復器はソースポインタであるため、呼び出されたcopy()アルゴリズムはmommove()で実際のレプリケーションを実行する.
copy_backward(first,last,result);//逆レプリケーション、反復器first-last位置の要素をresult-1から始まる逆区間に逆レプリケーション
補足:プロトタイプ:void memmove(void dest,const void*src,size_t count);
使用法:#include

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

六、Setメソッド

#include 
#include 
#include 
#include 
using namespace std;

template <class T>
struct display
{
    void operator()(const T &x)
    {
        cout<" ";
    }

};
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<int>());
    cout<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<cout<<"Intersection of s1 and s2: ";
    //      ，        min(m,n).
    set_intersection(first1,last1,first2,last2,ostream_iterator<int>(cout," ")); 
    cout<cout<<"Intersection of s1 and s2: ";
    //           S1   s2 
    set_difference(first1,last1,first2,last2,ostream_iterator<int>(cout," ")); 
    cout<cout<<"Intersection of s1 and s2: ";
    //        ：               。      ，        ，          
    //        abs(m-n) 
    set_symmetric_difference(first1,last1,first2,last2,ostream_iterator<int>(cout," ")); 
    cout<return 0;
}

七、その他のアルゴリズム(演算ロジックが比較的単純なアルゴリズム)
セグメント1のアルゴリズムの例:

#include 
#include 
#include 
#include 
#include  


using namespace std;

template <class T>
struct display
{
    void operator()(const T &x)const
    {
        cout<" "; 
    } 

}; 
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<cout<int>())<//   

    cout<6)<//  6    
    cout<int>(),7))<//    7       :9 

    cout<4)<//     4        

    cout<int>(),2))<//    2         ：3

    vector<int> iv2(ia+6,ia+8);//6 6

    for(int i=0;icout<" "; 

    cout<//  iv    iv2            （         ）：8 
    cout<<"find_end:"<3)<//  iv    iv2            （         ）：7
    cout<<"find_first_of:"<3)<int>()); 
     cout<//    iv2      even_by_two   
     generate(iv2.begin(),iv2.end(),even_by_two());
     for_each(iv2.begin(),iv2.end(),display<int>()); 
     cout<//    （       ），         even_by_two   
     generate_n(iv.begin(),3,even_by_two());
     for_each(iv.begin(),iv.end(),display<int>()); //  _X static         
     cout<//    6           
     remove(iv.begin(),iv.end(),6);
     for_each(iv.begin(),iv.end(),display<int>()); //  _X static         
     cout<//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<//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<//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<//8 10 7 8 7 8 7 8 8 0 0（        ） 


     return 0; 
} 

セグメント2のアルゴリズムの例:

#include 
#include 
#include 
#include 

using namespace std;

template <class T>
struct display
{
    void operator()(const T &x)const
    {
        cout<" "; 
    } 

}; 

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<//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<//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<//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<//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<//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<//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<//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<//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<//2 

    // iv    2 8             
    cout<2,8)<//8 

    // iv    3   8             
    cout<3,8,less<int>())<//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<cout<<"iv3:"; 
    for_each(iv3.begin(),iv3.end(),display<int>()); //iv3: 7 2 
    cout<//   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<//             iv  
    transform(iv.begin(),iv.end(),iv.begin(),iv.begin(),plus<int>());
    for_each(iv.begin(),iv.end(),display<int>());
    cout<//0 12 0 12 10 16 12 12 10 0 12


     return 0; 
} 

セグメント3のアルゴリズムの例:

#include 
#include 
#include 
#include 

using namespace std;

template <class T>
struct display
{
    void operator()(const T &x)const
    {
        cout<" "; 
    } 

}; 
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<cout<//  iv2          iv  
    cout<//iv  iv2   iv3  
    merge(iv.begin(),iv.end(),iv2.begin(),iv2.end(),iv3.begin()); 
    for_each(iv3.begin(),iv3.end(),display<int>());
    cout<//          ，           
    partition(iv3.begin(),iv3.end(),even());
    for_each(iv3.begin(),iv3.end(),display<int>());
    cout<//            
    unique(iv.begin(),iv.end()); 
    for_each(iv.begin(),iv.end(),display<int>());
    cout<//            
    unique_copy(iv.begin(),iv.end(),iv3.begin()); 
    for_each(iv3.begin(),iv3.end(),display<int>());
    cout<return 0; 
} 

八、複雑なアルゴリズムの例(ソースコードで説明)

#include 
#include 
#include 
#include 

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<" "; 
    } 

}; 
int main()
{
    int ia[] = {12,17,20,22,23,30,33,40};
    vector<int> iv(ia,ia+sizeof(ia)/sizeof(int));

    //             
    cout<21)<//22 
    cout<21)<//22 
    //              
    cout<22)<//22 
    cout<22)<//23

    //        ，       
    cout<33)<//1
    cout<34)<//0 

    //         （   ） 
    next_permutation(iv.begin(),iv.end()); 
    for_each(iv.begin(),iv.end(),display<int>());
    cout<int>());
    cout<//     
    random_shuffle(iv.begin(),iv.end()); 
    for_each(iv.begin(),iv.end(),display<int>());
    cout<//     4                    
    partial_sort(iv.begin(),iv.begin()+4,iv.end()); 
    for_each(iv.begin(),iv.end(),display<int>());
    cout<//  （       ） 
    sort(iv.begin(),iv.end());
    for_each(iv.begin(),iv.end(),display<int>());
    cout<//  （     ） 
    sort(iv.begin(),iv.end(),greater<int>());
    for_each(iv.begin(),iv.end(),display<int>());
    cout<22);
    iv.push_back(30);
    iv.push_back(17);


    //           
    stable_sort(iv.begin(),iv.end()); 
    for_each(iv.begin(),iv.end(),display<int>());
    cout<//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<//lowerbound 22 
    cout<//upperbound 23


    //          
    pairIte = equal_range(iv.begin(),iv.end(),25); 
    cout<//lowerbound 30 
    cout<//upperbound 30

     //     
    random_shuffle(iv.begin(),iv.end()); 
    for_each(iv.begin(),iv.end(),display<int>());
    cout<//   iv.begin+5      
    nth_element(iv.begin(),iv.begin()+5,iv.end()); 
    for_each(iv.begin(),iv.end(),display<int>());
    cout<//   iv.begin+5      
    nth_element(iv.begin(),iv.begin()+5,iv.end(),greater<int>()); 
    for_each(iv.begin(),iv.end(),display<int>());
    cout<//   
    stable_sort(iv.begin(),iv.end(),even());
    for_each(iv.begin(),iv.end(),display<int>());
    cout<return 0; 
}