×

[PR]この広告は3ヶ月以上更新がないため表示されています。
ホームページを更新後24時間以内に表示されなくなります。

 001-02  前へ←  ホームへ  →次へ  001-まとめ

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を省略するか、またn==-1のとき追加位置はリスト末尾になります。
追加されるアイテムは引数のコピーになります

・int p_push(T *t=NULL, int n=-1);
引数ポインタをリストに追加します
戻り値 必ず0が返ります

引数のポインタ(とその先の確保されてるメモリ)をリストのn番目の位置に追加します。
nを省略するか、またn==-1のとき追加位置はリスト末尾になります。
ポインタに確保するメモリは必ずnew演算子を使ってください(pop関数でddeleteを使用しているため)。
引数 *t ==NULLのとき関数内でメモリを確保します。

・T *a_push(int n=-1);
自動でリストにアイテムを追加します
戻り値 新しいアイテムへのポインタを返します

new演算子を使ってメモリ確保して、リストのn番目の位置にアイテムを追加します。
nを省略するか、またn==-1のとき追加位置はリスト末尾になります。

・pop(int n);
           (PLIST版と少し違います)
リストからアイテムを削除します
戻り値 新しいアイテム数を返します

リストのn番目のアイテムを削除します
nを省略するか、またn==-1のとき削除位置はリスト末尾になります。
このときメモリの解放はしません。

・mem_pop(int n=-1)
リストからアイテムを削除しメモリを解放します。
戻り値 新しいアイテム数を返します

リストのn番目のアイテムを削除します
nを省略するか、またn==-1のとき削除位置はリスト末尾になります。
このときメモリを解放します。

・size();
リストのアイテムの数を取得
戻り値 アイテム数を返します。

・mem_size();
リスト上に確保しているメモリのアイテム数を取得
戻り値 メモリのアイテム数を返します。

変数名[n];
配列的にアクセスします
戻り値 n番目のアイテムのポインタへの参照

リストの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個に変更します
戻り値 アイテム数を返します

変更前のアイテム数がn個より大きければn+1番目以降のアイテムは削除されます。
メモリ解放はしません。

・mem_resize(int n)
アイテム数を強制的にn個に変更します
戻り値 アイテム数を返します

変更前のアイテム数が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);                                     // アイテムの数を4個にする
    return 0;
}
実行結果

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

 001-02  前へ← ホームへ  →次へ  001-まとめ