空いている領域に効率的にデータを挿入する方法

Program DKUT ProgramIdiom

ども、久々です。d金魚です。
今回は私の考えたコンテナについてのお話です。

ゲームを作るとき、必ず、メモリプールを作って、そこから各オブジェクトにメモリを割り当てたりしますよね＾＾
メモリプールと言えば、



struct DATA{

  BOOL flag;

  int x,y;

  int data,id;

};
//グローバルな領域にでも宣言する。

DATA pool[100];

//検索するプログラムはこんな感じ

for(int i=0;i<100;i++){

  if(pool[i].flag==FALSE){

    pool[i].flag = TRUE;

    return i;

  }

  return -1;

}

こんな感じのプログラムしか当時は知りませんでした。

効率的な方法は無いものだろうか・・・。と、高校一年の時に考えた事があります。
そこで、条件を列挙して考える事にしました。

  • 先にメモリを確保しておく
  • フラグは使わない
  • 線形探索をしない
  • 速く空き領域を知る事が出来る。
  • どんな状態でも挿入、削除が簡単に出来る。

というルールを設け、考えた結果、

  • 空き領域を記憶しておく

という考えにたどり着きました。*1

もちろん、このようなライブラリは既にあるのでは？と思われるかもしれませんが、私が知る限りありませんでした。
例えば、

  • std::vector イテレータが無効になる。削除すると詰める処理が行われる。
  • std::list 双方向リストなのでポインタ２つ分*2無駄になる。
  • std::map std::set 二分木なんて要らない。
  • std::deque 挿入とかは結構イイ感じだが、要素の削除が遅そう。*3
  • boost::pool 直接ポインタをいじる事になり、コンテナとしては使いにくい。
  • glibのmemchunk まだ、触っていないが、これもboost::poolと同

と、まぁ、やっぱり何かとダメだったんですよ＾＾；

で、その試行錯誤で生まれたのがdKingyo_ArrayOneByOneというヘナチョコクラスでした。

それを改良してarray_onebyoneというテンプレートクラスも出来ました。*4

さらに、仕様をきめて組んでみる事にしました。

  • 配列の空き領域への配列の添え字（以下 参照ID)をStackに入れておく。
  • 挿入するときはStackから空き領域を得る、そして参照IDを返す。
  • 削除するときは参照IDを受け取り、そのIDをStackに返す。
  • 初期化フラグによって自動的に内部バッファが動的拡張されたりする。
  • バッファをいつでもリサイズする事が出来る。（しかし、内部にデータがある場合はバッファを小さくは出来ない。）

そして、今日、C言語版ArrayOneByOneを作ったのでアップしておきます。
BSD Licenceでご自由にお使いください。m(_ _)m

ではでは。

本体
http://cvs.sourceforge.jp/cgi-bin/viewcvs.cgi/dkingyoutility/dkutil/dkutil_c/dkcArrayOneByOne.c
http://cvs.sourceforge.jp/cgi-bin/viewcvs.cgi/dkingyoutility/dkutil/dkutil_c/dkcArrayOneByOne.h


サンプル

void Test_ArrayOneByOne(){

  const int num = 10;

  int i=0;

  int id[num];

  DKC_ARRAY_ONEBYONE *p = dkcAllocArrayOneByOneStatic(sizeof(int),num);

  

  {

    for(i=0;i<num;i++){

      id[i] = dkcArrayOneByOnePush(p,&i);

    }

    for(i=0;i<num;i++){

      int temp;

      dkcArrayOneByOneReference(p,id[i],(void *)&temp);

      printf("id[%d]==%d -> %d,\n",i,id[i],temp);

    }

    printf("\n");

  }
  {

    //開放

    for(i=0;i<num;i+=2){

      dkcArrayOneByOnePop(p,id[i]);

    }

    //挿入

    for(i=0;i<num/2;i++){

      id[i*2] = dkcArrayOneByOnePush(p,&i);

    }

    //次はもう入らないので-1を返すはず

    dkcmNOT_ASSERT(-1 != dkcArrayOneByOnePush(p,&i));

    for(i=0;i<num;i++){

      int temp;

      dkcArrayOneByOneReference(p,id[i],(void *)&temp);

      printf("id[%d]==%d -> %d,\n",i,id[i],temp);

    }

    printf("\n");

  }
  dkcFreeArrayOneByOne(&p);
}

*1:イヤ＾＾；普通は皆さん、そう考えるはずですが、当時の私はこれは画期的な方法だと思ったのです・・・。

*2:32bit機だと8バイトだよね？

*3:例えば中ほどの要素を削除するとか

*4:詳しくはdkutilにて http://www.vector.co.jp/soft/win95/prog/se309230.html