無料CGI

No.001-03 拡張リスト・クラスのテンプレート(クイック・リスト編)

XLIST、PLISTは高速な（ミリ秒単位の）アイテム追加、削除の繰り返しにとても弱いです。
それは new と delete に原因があります。
メモリの確保、解放は他の処理にくらべて非常に時間がかかります（といっても人間には高速に見えますが）。
そのためメモリの確保、解放が完了しないまま処理が進むとメモリ・リークやフリーズといった現象が引き起こされます。
とはいえpush、popを遅延させるわけにもいきません。

そこでpop時にdeleteしないで、クラス外から「アクセス不可」にするだけにして、
次にpush する時そのdelete しなかったメモリを使います。

QLIST　(クイック・リスト)
push系の使い方はPLISTと同じです。
pop系の使い方も基本的に同じですがメモリを解放しないので注意が必要です。
PLISTのようにメモリ解放する pop は mem_pop として名前を変えて残してあります。

主な使い方
QLIST<クラス名> 変数名;	・・・宣言（内部でXLIST<クラス名*>を宣言している）
p_push(アイテムポインタ);	・・・アイテムへのポインタをリストに追加
a_push(void)	・・・メモリがあるならそのポインタをリストに追加。メモリが無ければ内部でnew 演算して、リストに追加
pop(n);	・・・n番目のアイテムをリストから削除
mem_pop(n)	・・・n番目のアイテムをリストから削除（メモリも解放する）。
変数名[n];	・・・配列的にアクセス
size();	・・・現在のアイテム数の取得

qlist.h


#ifndef _QLIST_H_
#define _QLIST_H_

#include <stdio>
#include <stdlib>
#include "plist.h"

//==========================================
//              QLIST   クイック・リスト                        
//==========================================
template <class T> class QLIST {
        public :
        int pret_size;
        PLIST<T> plist; // has a型（多態push作成のためis aでない）

        swap(int n1, int n2){
                plist.swap(n1, n2);
        };
        T* &last(){     return plist.last(); };
        size()          { return pret_size; };          // アイテム数を返す
        mem_size()      { return plist.size(); };       // メモリ・アイテム数を返す
        resize(int n){
                if (n>plist.size()) plist.resize(n);    // 追加
                return pret_size=n;
        };
        mem_resize(int n){ return plist.resize(n); };
        T *a_push(int n=-1){    // オート・プッシュ
                if (n<0 || n>pret_size) n=pret_size;
                if (pret_size>=plist.size()) plist.a_push(n);
                else if (n>=0 && n<pret_size) {
                        plist.roll(pret_size, n);
                //      *(plist[n])=t;  // 通常プッシュ
                }
                pret_size++;
                return plist[n];
        }
        pop(int n=-1){
                if (pret_size<=0) return 0;
                if (n>0) plist.roll(n, pret_size);
                pret_size--;
        }
        mem_pop(int n=-1){      return plist.pop(n);    }
        // ランダムアクセス
        T* &operator [](int n){
                if (pret_size<=n) return plist[-1];
                return plist[n];
        };

        // コンストラクタ
        QLIST(){
                pret_size=0;
        };
        del_all(){
                pret_size=0;
        }
        mem_del_all(){
                pret_size=0;
                plist.del_all();
        }
};

#endif  // _QLIST_H_

●リファレンス

【QLIST】 クイック・リスト構造

・	基本は上記のPLISTですが高速push/popの実現のために、pop時にメモリ解放せず配列的アクセスをできなくするだけにします。そして次回push時にメモリを使い回します。
・	ポインタでリスト構造を組み立て、配列的アクセス時に各アイテムへのポインタが返るようにします。
・	不意のデストラクタを防ぎ、配列外アクセス時にはNULLが返るようになってます。
・	QLISTのデストラクタで各アイテムのデストラクタが呼び出されます

汎用関数

*・T push(T &t, int n);**
	リストにアイテムを追加します戻り値新しいアイテムへのポインタを返しますリストのｎ番目の位置にアイテムを追加します。 nを省略するか、またn==-1のとき追加位置はリスト末尾になります。追加されるアイテムは引数のコピーになります
*・int p_push(T t=NULL, int n=-1);**
	引数ポインタをリストに追加します戻り値必ず0が返ります引数のポインタ（とその先の確保されてるメモリ）をリストのｎ番目の位置に追加します。 nを省略するか、またn==-1のとき追加位置はリスト末尾になります。ポインタに確保するメモリは必ずnew演算子を使ってください(pop関数でｄdeleteを使用しているため）。引数 *ｔ ==NULLのとき関数内でメモリを確保します。
*・T a_push(int n=-1);**
	自動でリストにアイテムを追加します戻り値新しいアイテムへのポインタを返します new演算子を使ってメモリ確保して、リストのｎ番目の位置にアイテムを追加します。 nを省略するか、またn==-1のとき追加位置はリスト末尾になります。
・pop(int n); 　　　　　　　　　　　（PLIST版と少し違います）
	リストからアイテムを削除します戻り値新しいアイテム数を返しますリストのｎ番目のアイテムを削除します nを省略するか、またn==-1のとき削除位置はリスト末尾になります。このときメモリの解放はしません。
・mem_pop(int n=-1)
	リストからアイテムを削除しメモリを解放します。戻り値新しいアイテム数を返しますリストのｎ番目のアイテムを削除します nを省略するか、またn==-1のとき削除位置はリスト末尾になります。このときメモリを解放します。
・size();
	リストのアイテムの数を取得戻り値アイテム数を返します。
・mem_size();
	リスト上に確保しているメモリのアイテム数を取得戻り値メモリのアイテム数を返します。
変数名[n];
	配列的にアクセスします戻り値ｎ番目のアイテムのポインタへの参照リストのｎ番目のアイテムのポインタを参照します。じかに代入もできますもできますがお奨めしません。
・del_all();
	アイテムをすべて削除します戻り値必ず0が返りますリストのアイテム全てを削除します。メモリは解放しません。
・mem_del_all();
	アイテムをすべて削除し、そのメモリも解放します。戻り値必ず0が返りますリストのアイテム全てを削除し、そのメモリを解放します。PLISTのdel_all()関数と同じです。
・swap(int n1, int n2) 　　　　　　　　　　　（XLIST版と同じ）
	リストのn1番目とn2番目を入れ替えます戻り値必ず0が返ります
・resize(int n); 　　　　　　　　　　　（PLIST版と少し違います）
	アイテム数を強制的にｎ個に変更します戻り値アイテム数を返します変更前のアイテム数がｎ個より大きければn+1番目以降のアイテムは削除されます。メモリ解放はしません。
・mem_resize(int n)
	アイテム数を強制的にｎ個に変更します戻り値アイテム数を返します変更前のアイテム数がｎ個より大きければ n+1番目以降のアイテムを削除し、そのメモリを解放します。 PLIST版のresize()関数と同じです。

●QLIST　サンプル

int main(){
    QLIST<int> list;    // int型のクイック・リストを宣言
    int n=100, *pn;
    pn=list.a_push();   // アイテムを追加しそのアイテムへのポインタを得る
    *pn=n++;            // 追加したアイテムに値を代入
    pn=list.a_push();*pn=n++;
    pn=list.a_push();*pn=n++;
    pn=list.a_push();*pn=n++;
    pn=list.a_push();*pn=n++;
    pn=list.a_push();*pn=n++;
    list.pop(3);                                        // list[3]をリストから削除
    for(int i=0;i<list.size();i++){
        printf("list[%d]=%d\n", i, *list[i]);           // list[i]を表示
    }

    printf("list.size(); %d\n", list.size());           // リストアイテム数を表示

    list.del_all();                                     // アイテムの全削除、ただしメモリは解放しない。
    printf("list.del_all();呼び出し \n");

    printf("list.size(); %d\n", list.size());           // リストアイテム数を表示
    printf("list.mem_size(); %d\n", list.mem_size());   // リストアイテムの現在のメモリ確保数を表示

    list.mem_del_all();
    printf("list.mem_del_all();呼び出し \n");

    printf("list.mem_size(); %d\n", list.mem_size());   // アイテムの全削除、アイテム用メモリも解放。
    list.resize(4);                                     // アイテムの数を４個にする
    return 0;
}

実行結果

上記ソースは全て自由に改編して使ってかまいませんが必ず自己責任でね。

001-02 前へ←

ホームへ

→次へ 001-まとめ