#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を１つ進める.
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
#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() );
}
トップページに戻る
前ページへ :
トップへ :
次ページへ