C言語でdequeを実装する為のメモ

Program DKUT 備忘録

　昔、dkutil_cというライブラリでdouble ended queue（ＳＴＬのdeque）を実装するのをあきらめた事がある。理由は以下の通りだ。

  • double ended list(双方向リスト構造）で代用できる
  • 一つ一つのメモリブロックを管理するにはdequeオブジェクトに多数のvectorオブジェクトを格納し、それらを参照させる為にはvectorオブジェクトをlistオブジェクトやmapオブジェクトで管理させる必要がある。

以下Ｃ＋＋風の擬似コード



class deque{

 list mList; もしくは map mMap;

};

  • なんだか複雑になって想定外のバグが起こりそう。よってバグのチェックが大変。さらには誰かが使用する価値が無さそう。
  • dequeはvectorオブジェクトのサイズによっては無駄にメモリ領域を使う。

なので、やはりＣ言語でこんなせせこましいコードを書くのは良くないと思っていたのだ。今、改めて考えてもＣ言語でdequeを実装するならば双方向リスト構造で十分だ。


　逆説的な解決策としては、双方向リスト構造につかうリストの要素ひとつひとつを多数プールしておいて、使用するときになったらプールから確保していく事だ。これにより毎回、リストに挿入するときのメモリ確保のオーバーヘッドは回避できる。

以下Ｃ＋＋風の擬似コード



class list{
list_elem *mChunk;

unsigned int mCounter;

 void alloc_listelem(){

  mChunk = new list_elem[256];

　mCounter = 0;

 }

 void push_back(){

  p = mChunk[mCounter++];

  //つなぎかえごにょごにょ
};

//削除処理やプールの管理は各自考えてね。