線形探索c++

配列からある条件に合う最初の要素のインデックスを返す関数を例に線形探索のバリエーションを挙げてみる。
/* ここから前振り */
#include <vector>
#include <algorithm>

using namespace std;

int cond(int)
{
  return 0;
}

#define SIZE (100)
int ary[SIZE];  

int
main(int argc, char *argv[])
{
  return 0;
}
/* ここまで前振り */




/* パターンA
  ループ脱出後にもう一度条件判断して見つかったどうか
  判定する。
 */
int func_a()
{
  int i;
  for( i=0; i<SIZE; ++i){
    if( cond(ary[i])){
      break;
    }
  }
  if( i<SIZE ){
    return i;
  }
  else{
    return -1;
  }
}
 /* これが一番シンプルで堅牢だと思う。*/


/* パターンB
  見つけた位置を記録する変数(見つけた変数)を別途用意し
  てフラグ代わりに 使う。ループ脱出後にはその見つけた
  変数をチェックする。*/
int func_b()
{
  int found=-1;
  int i;
  for( i=0; i<SIZE; ++i){
    if(cond(ary[i])){
      found=i;
      break;
    }
  }
  if( found>=0 ){
    return found;
  }
  else{
    return -1;
  }
}
/* よく見かけるパターン。foundの初期化し忘れに弱い。
   ループの外ではiを使っていないのでiのスコープを狭くしたときは 
   有効?
*/

  

/* パターンC A,
   Bの合せ技。念のためにループ脱出後にルー
   プ変数をチェックしてい更に見つけた変数もチェック。
*/

int func_c()
{
  int i;
  int found = -1;
  for( i=0; i<SIZE; ++i){
    if(cond(ary[i])){
      found=i;
      break;
    }
  }
  if( i<SIZE ){
    if( found>=0 ){
      return found;
    }
    else{
      // never reach here
      return i;
    }
  }
  else{
    return -1;
  }
}
/* 記述が冗長かも */


/* パターンD
   STLのベクタとイテレータを使った場合
*/
int func_d()
{
  vector<int> a(10,0);

  vector<int>::iterator it;
  for( it = a.begin(); it != a.end(); it++){
    if(cond(*it)){
      break;
    }
  }
  if( it != a.end()){
    return it-a.begin();
  }
  else{
    return -1;
  }
  
}
/* stlを使う場合はこれが普通。ケースAに近い。 */

/* ケースE
   findを使う
*/
int func_e()
{
  vector<int> a(10,0);
  vector<int>::iterator it = find_if( a.begin(),
                                      a.end(),
                                      cond);
  if( it != a.end()){
    return it-a.begin();
  }
  else{
    return -1;
  }
}
/* algorithm::find_if()を使う。楽チン */

/* ケースF
   boost::arrayを使って
*/
int func_f()
{
  // TODO
}
/* 配列にfind_ifかませればと思ったら簡単ではなかった。というか
   boostが必要。(あるいは自分で相当な記述をする必要?)
*/
最新の20件
