トップ->C++入門

あなたは

人目のC++(C)言語入門受講生です。

C++入門内検索

目次
C++入門〜トップ
C言語入門〜トップ
0. はじめに

1. オブジェクト指向とは?
   1. オブジェクト指向とクラス
   2. 継承
   3. カプセル化
   4. ポリモーフィズム

2. ストリーム
   1. 出力
   2. マニピュレータ
   3. 入力
   4. ファイル
   5. 練習問題1
   6. 文字列
   7. 練習問題2

3. C++の新しい文法
   1. 新しい型bool
   2. デフォルト引数
   3. newとdelete
   4. 参照型
   5. const
   6. 変数の宣言
   7. 例外
   8. オーバーロード
   9. テンプレート関数
   10. 名前空間

4. クラス
   1. クラスとは
   2. クラスの宣言
   3. クラスの実装
   4. コンストラクタとデストラクタ
   5. クラスの使用法
   6. 例題)スタッククラス
   7. テンプレートクラス
   8. 練習問題
   9. 参照型
   10. 代入演算子
   11. コピーコンストラクタ
   12. 構造体
   13. メンバー変数の初期化
   14. 内部クラス
   15. 無名クラス
   16. 無名共用体
   17. 演算子の作り方
   18. friend
   19. 練習問題
   20. クラス変数(静的変数)
   21. 静的関数
   22. クラスと関数ポインタ

5. クラスの包含
   1. 包含とは
   2. クラスの作成・破壊
   3. メンバーイニシャライザ
   4. ポインタによる包含
   5. 参照による包含
   6. 練習問題

6. 継承
   1. 継承とは
   2. スーパークラスのコンストラクタ
   3. 継承とキャスト
   4. スコープ
   5. クラスの作成・破壊
   6. 派生の種類
   7. 仮装関数
   8. 純粋仮装関数
   9. 仮装デストラクタ
   10. 例題)例外クラス
   11. V-table(VF-table)
   12. 例題)お絵かきソフト
   13. 継承と包含
   14. 多重継承
   15. 多重継承の用途
   16. 仮想クラス
   17. 実行時型情報(RTTI)
   18. dynamic_cast

7. STL
   1. STLとは
   2. STLの歴史
   3. STLの構成
   4. コンテナ
   5. vector
   6. イタレーター
   7. クラスとSTL
   8. list
   9. queue
   10. deque
   11. priority_queue
   12. stack
   13. map
   14. mutimap
   15. set
   16. multiset
   17. bitset
   18. アルゴリズム
   19. basic_string
   20. コンテナを作ろう
   21. アルゴリズムを作ろう
   22. 配列とアルゴリズム

8. その他
   1. 変数名について

9. その後は
   1. ヒューマンアカデミー C言語講座
   2. el school C言語講座


・ トップページに戻る



・ トップページに戻る

トップ-> C++入門:7章 STL-> アルゴリズムを作ろう

←前ページへ :  トップへ :  次ページへ→

21. アルゴリズムを作ろう


  アルゴリズムは、コンテナを知らなくてもいいように記述しなければなりません。また、 テンプレートを利用して、int型、float型、ポインタ型、さらにはクラスや構造体など、 どんな型にも対応させなければなりません。

// T型の要素を探索する
//見つかった時はその要素を指すiteratorを返す。
//見つからなかった時はlastを返す。
template<class InIt,class T>
InIt find(InIt first,InIt last,const T& val){
    InIt itr = first;
    for( ; itr != last ; itr++ ){
        if( *itr == val )
            break;
	}
    return itr;
}
のように記述します。

  それでは自前で作ったアルゴリズムを紹介します。
Algorithm.h

#ifndef ALGOLITHM_H
#define ALGOLITHM_H

#include<iostream>
#include<time.h>

namespace Algorithm{
/*------------------------------------------------------
//OutIt--出力反復子を示す
//intIt--入力反復子を示す
//FwdIt--前方反復子を示す
//BidIt--双方向反復子を示す
//RanIt--ランダムアクセス反復子を示す
//Pred -- 条件式で真か偽を返す
-------------------------------------------------------*/
template<class T>                            void   swap(T& x,T& y);
template<class FwdIt1,class FwdIt2>          void   iter_swap(FwdIt1 x,FwdIt2 y);
template<class FwdIt1,class FwdIt2>          FwdIt2 swap_ranges(FwdIt1 first, FwdIt1 last, FwdIt2 x);
template<class InIt,  class T>               InIt   find(InIt first,InIt last,const T& val);
template<class InIt,  class Pred>            InIt   find_if(InIt first,InIt last,Pred pr);
template<class InIt,  class T>               int    count(InIt first,InIt last,const T& val);
template<class InIt,  class Pred>            int    count_if(InIt first,InIt last,Pred pr);
template<class FwdIt, class T>               FwdIt  remove(FwdIt first,FwdIt last,const T& val);
template<class InIt,  class Fun>             Fun    for_each(InIt first, InIt, Fun f);
template<class InIt,  class OutIt,class Fun> OutIt  transform(InIt first, InIt last, OutIt res, Fun f);
template<class InIt,  class OutIt>           OutIt  copy(InIt first, InIt last, OutIt);
template<class FwdIt, class T>               void   replace(FwdIt first, FwdIt last, const T& vold, const T& vnew);
template<class FwdIt, class Pred, class T>   void   replace_if(FwdIt first, FwdIt last, Pred pr, const T& val);
template<class RandIt>                       void   random_shuffle(RandIt first,RandIt last);
template<class RandIt>                       void   sort(RandIt first,RandIt last);


template<class T>
void swap(T& x, T& y){
    T tmp = x;
    x     = y;
    y     = tmp;
}


//反復子引数が指す要素を交換する
template<class FwdIt1,class FwdIt2>
void iter_swap(FwdIt1 x,FwdIt2 y){
    swap( *x, *y );
}

//firstからlastの要素をxから始まる要素と交換する
template<class FwdIt1,class FwdIt2> 
FwdIt2 swap_ranges(FwdIt1 first, FwdIt1 last, FwdIt2 x){
    while(first!=last)
        iter_swap(first++, x++);

    return x;
}

// T型の要素を探索する
//見つかった時はその要素を指すiteratorを返す。
//見つからなかった時は、lastを返す。
template<class InIt,class T>
InIt find(InIt first,InIt last,const T& val){
    InIt itr = first;
    for( ; itr != last ; itr++ ){
        if( *itr == val )
            break;
	}
    return itr;
}


//見つかった時はその要素を指すiteratorを返す。
template<class InIt,class Pred>
InIt find_if(InIt first,InIt last,Pred pr){
    InIt itr = first;
    while( itr != last )
        if( pr( *itr ) )
            return itr;
	
    return itr
}

//val要素の数を数える
template<class InIt,class T>
int count(InIt first,InIt last,const T& val){
    InIt itr   = first;
    int  count = 0;

    for( ; (itr=find(itr,last,val) ) != last ; itr++ )
        count++;
    return count;
}

//条件を満たす要素の個数を返す
template<class InIt,class Pred>
int count_if(InIt first,InIt last,Pred pr){
    InIt itr  = first;
    int count = 0;

    for( ; itr != last ; itr++ )
        count += pr(*itr);

    return count; //条件に満たした個数を返す
}

//要素valを格納するセルを削除し、戻り値は変更された終端のiteratorを返す
template<class FwdIt,class T>
FwdIt remove(FwdIt first,FwdIt last,const T& val){
    FwdIt itr = first;
    FwdIt current_itr;       //removeするiteratorを指す
    FwdIt root_itr;          //removeする値が連続した場合、連続する最初のiteratorを保持する	
    bool  flag = false;      //取り去る値が連続してる時、フラグを立てる。

    while( (itr=find(itr,last,val)) != last) {	
        current_itr=itr;
        itr++;                               // 次の要素を知るためiteratorを1つ進める.

        if( *current_itr != *itr ){
            if( flag ){
                *last     = *root_itr;       //取り去る値の最初の位置に連続終端の次に現れる値を交換する
                *root_itr = *itr;
                *itr      = *last;
				
                root_itr++;                  //連続した最初の位置の次にiteratorを進め、またそこから検索する     
                itr  = root_itr;
                flag = false;
			}
            else{
                *last        = *current_itr; //現在位置の要素をエンド領域に格納さしてもらう。
                *current_itr = *itr;
                *itr         = *last;
            }
        }
        else if( !flag ){                    //取り去る値が連続する時
            root_itr = current_itr;
            flag     = true;
        }
    }
	
    itr = find( first,last,val );    //取り除かれた値は後ろに積められたので
                                     //itrはゴミ領域の最初のiteratorを返す。
    return itr;
}


template<class InIt,class Fun>
Fun for_each(InIt first, InIt last, Fun f){
    while( first != last)
        f( *first++ );

    return f;
}

template<class InIt,class OutIt,class Fun>
OutIt transform(InIt first, InIt last, OutIt res, Fun f){
    while( first != last )
        *res++ = f(*first++);

    return res;
}

template<class InIt,class OutIt>
OutIt copy(InIt first, InIt last, OutIt){
    while( first != last )
        *res++ = *first++;

    return res;
}

template<class FwdIt,class T>
void replace(FwdIt first, FwdIt last, const T& vold, const T& vnew){
    for( ; first != last ; first++ ){
        if( *first == vold )
            *first=vnew;
    }
}

template<class FwdIt,class Pred, class T>
void replace_if(FwdIt first, FwdIt last, Pred pr, const T& val){
    for( ; first != last ; first++ ){
        if(pr(*first))
             *first = val;
    }
}

template<class RandIt>
void random_shuffle(RandIt first,RandIt last){
    int num;
    int count  = 0;
    RandIt tmp = first;

    for( ; tmp != last ; count++, tmp++ );

    srand( (unsigned)time( NULL ) );  
 
    for( ; count > 1 ; first++, count-- ){
        rand();
        num = (int)(count*(rand()/32767.1)+1);	 
        tmp = first;

        for( ; num > 1 ; tmp++, num-- );

		swap( *first, *tmp );
	}
}

// クイックソート
template<class RandIt>
void sort( RandIt first, RandIt last ){
    last--;

    RandIt i;
    RandIt j;
    RandIt x;

    x = first;                // ピボット
    i = first;                // first は 左境界,lastは 右境界
    j = last;

    while(true) {             //無限ループ
        while( *i < *x )
            i++;              // 交換する要素の決定
        while( *x < *j )
            j--;
        if( i >= j )
            break;            // 左境界が右境界を越えたら ループ終了
        swap( *i, *j );       // i と jを交換
        i++;                  // 境界をさらにせばめる.
        j--;
    }

    if( first < i-1 )
        sort( first, i );     // i, jの変換があれば もう一度行なう
    if( j+1 < last )
        sort( j+1, last+1 );  // +1がポイント
}

};
#endif

main.cpp

#include<iostream>

#include<vector>
#include "Algorthm.h"

using namespace Algorithm;
using namespace std;

// 表示する関数
// これも一種のアルゴリズムと考えられる
template<class InIt>
void disp(InIt first, InIt last){
    for( ; first != last ; first++ )
        cout << *first << ' ';
    cout << endl;
}

void main(){
    vector<int>	v;
    int i;
    for( i = 0 ; i < 10 ; i++ )
        v.push_back( i );

    disp( v.begin(), v.end() );

    random_shuffle( v.begin(), v.end() );
    disp( v.begin(), v.end() );

    sort( v.begin(), v.end() );
    disp( v.begin(), v.end() );
}
0 1 2 3 4 5 6 7 8 9
6 1 5 9 8 4 2 7 3 0
0 1 2 3 4 5 6 7 8 9


←前ページへ :  トップへ :  次ページへ→