×

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

     -      ホームへ  →次へ  001-02

No.001-01  拡張リスト・クラスのテンプレート

C++でリスト構造をいちいち作んのめんどくさい
かといってSTLの<vector>やら<list>もなんか今ひとつ使いづらい
   ・・・ので簡単リスト化テンプレートで作ってみました。そして公開。

使い方はシンプル
XLIST<クラス名> 変数名; ・・・宣言
push(値); ・・・アイテムをリストに追加
pop(n); ・・・n番目のアイテムをリストから削除
変数名[n]; ・・・配列的にアクセス
size(); ・・・現在のアイテム数の取得

例えば

#include "xlist.h";
int main(){
    XLIST<int> num;   // 宣言
    num.push(20);      // リストに20という値を追加
    num.push(21);      // リストに21という値を追加
    num.push(22);      // リストに22という値を追加
    num.pop();           // リストから末尾のアイテム(22の値)を削除
    printf("%d\n", num[1]);   // 画面にリストの2番目の値を出力
    return 0;
};

というコードを書けば画面(MS-DOSプロンプト)には"21"が表示されます

 xlist.h
#ifndef _XLIST_H_
#define _XLIST_H_

#include <stdio>
#include <stdlib>

//==========================================
//              リスト型テンプレート                            
//==========================================

// 連結アイテム・クラス
template <class T> class LIST_ITEM{
        public:
        T t;                                    // ←アイテム本体   
        LIST_ITEM *next, *before;                       // ノード
        LIST_ITEM(){ next=before=NULL; }        // コンストラクタ
};

//==========================================
//              XLIST   拡張リスト                                      
//==========================================
template <class T> class XLIST {
        private:
        // メンバ変数
        LIST_ITEM<T> *head, *tail;
        LIST_ITEM<T>    *last_use;
        int                             last_use_id;
        int item_length;

        public :
        XLIST();                // コンストラクタ
        ~XLIST();               // デストラクタ
        push(T t);              // アイテム追加
        push(T t, int n);               // アイテム追加
        pop(int n=-1);  // 第n番目のアイテム削除
        val_pop(T t);   // tの値と同じアイテムの削除
        // ランダムアクセス
        LIST_ITEM<T>*   get_ptr_abs(int n);
        LIST_ITEM<T>*   get_ptr_rel(LIST_ITEM<T>* pitem, int n);
        virtual LIST_ITEM<T>*   get_ptr(int n);
        T &operator [](int n);
        T &last();
        del_all();
        init();
        set_default(T &t);
        size();         // アイテム数を返す
        resize(int n);
        swap(int n1, int n2){
                LIST_ITEM<T> *p
                T tmp_t=*get_ptr(n1);
                *get_ptr(n1)=*get_ptr(n2);
                *get_ptr(n2)=tmp_t;
                return 0;
        };
        roll(int n1, int n2);
};

// コンストラクタ 
template <class T> XLIST<T>::XLIST(){ init(); }

// デストラクタ
template <class T> XLIST<T>::~XLIST(){ del_all(); delete head; }

// 初期化               
template <class T> XLIST<T>::init(){
        head = new LIST_ITEM<T>;
        last_use        = tail = head;
        last_use_id     = item_length= 0;
        return 0;
}

// アイテム数           
template <class T> XLIST<T>::size(){
        return item_length;
}
// アイテム数変更               
template <class T> XLIST<T>::resize(int n){
        if (n<0) n=0;
        int i, add_size = n - item_length;
        if (!add_size){
                return item_length;
        }
        else if (add_size>0){
                T t;
                for(i=0;i<add_size;i++) push(t);
                return add_size;
        }
        else if (add_size<0){
                add_size=-add_size;
                for(i=0;i<add_size;i++) pop();
                return -add_size;
        }
        return item_length;
}

// アクセスエラー時の返り値 設定                
template <class T> XLIST<T>::set_default(T &t){ head->t = t; return 0; }

// 全破棄               
template <class T> XLIST<T>::del_all(){
        int i, del_len=size()+1;
        for(i=0;i<del_len;i++) pop();
        return 0;
}
// ====== ランダムアクセス =====================================================
// 演算子 []    
template <class T> T& XLIST<T>::operator [](int n){
        LIST_ITEM<T> *p=get_ptr(n);
        return p->t;
}
// 演算子 []    
template <class T> T& XLIST<T>::last(){
        return tail->t;
}


// 相対パスから    
template <class T> LIST_ITEM<T>* XLIST<T>::get_ptr_rel(LIST_ITEM<T>* pitem, int n){
        if (n>0){
                for(int i=0;i<n;i++) if (pitem->next)   pitem=pitem->next;
        } else if (n<0){
                n=-n;
                for(int i=0;i<n;i++) if (pitem->before) pitem=pitem->before;
        }
//      printf("rel  ");
        return pitem;
};

// 絶対パスから    
template <class T> LIST_ITEM<T>* XLIST<T>::get_ptr_abs(int n){
        LIST_ITEM<T> *pitem=head->next;
        for(int i=0;i<n;i++) if (pitem->next)   pitem=pitem->next;
        return pitem;
}

// ランダムアクセス総括関数    
template <class T> LIST_ITEM<T>* XLIST<T>::get_ptr(int n){
        LIST_ITEM<T> *pitem;
        int i = n-last_use_id, len=size();
        if (n>=len || n<0) return head;

        if (n > abs(i)){
                if ((len-n-1) > abs(i)) pitem = get_ptr_rel(last_use, i);
                else                                    pitem = get_ptr_rel(tail, n-len+1);
        }
        else pitem = get_ptr_abs(n);    // 先頭からノード検索

        if (pitem) {    // 最後にアクセスしたアイテム更新
                last_use        =pitem;
                last_use_id     =n;
        }
        return pitem;
}

// アイテム移動    (第n1番目のアイテムを第n2番目に移動)   
template <class T> XLIST<T>::roll(int n1, int n2){
        if (item_length<=0) return 0;           // LISTアイテムなし
        LIST_ITEM<T> *bef, *nex, *org, *dst;
        if (n1<0 || n1>=item_length) org=tail;  // n1 が範囲外なら末尾を削除
        else org = get_ptr(n1);
        if (n2<0 || n2>=item_length) dst=tail;  // n2 が範囲外なら末尾を削除
        else dst = get_ptr(n2);
        if (!org || !dst || org==head || dst==head || org==dst) return 0;

        // ターゲット・アイテムを一時リストからはずす
        bef=org->before;
        nex=org->next;
        if (bef) bef->next=nex;
        if (nex) nex->before=bef;

        // 一時リストからはずしていたターゲット・アイテムを目的位置にセット
        bef=dst->before;        bef->next=org;  // ■-□-□             ■の設定
        dst->before=org;                                        // □-□-■             ■の設定
        org->next=dst;          // □-■-□             ■の設定
        org->before=bef;        // □-■-□             ■の設定
        tail = last_use =get_ptr_abs(item_length);
                last_use_id     =item_length-1;
        return item_length;
}
// アイテム追加   
template <class T> XLIST<T>::push(T t){
        LIST_ITEM<T> *old_tail=tail;            // 更新前の末尾ポインタ保持
        tail->next = new LIST_ITEM<T>;          // 末尾アイテムのnextに新リスト作成
        tail=tail->next;                                // 新リストにtailポインタを合わせる
        tail->t = t;                                    // 新リストにアイテム代入
        tail->before=old_tail;
        item_length++;
        return item_length;
};
// アイテム追加 (挿入型)  
template <class T> XLIST<T>::push(T t, int n){
        if (n>=item_length) return push(t);
        if (n<=0) n=0;
        LIST_ITEM<T> *bef_pitem, *nex_pitem, *pitem;
        bef_pitem=get_ptr(n-1);                 // 挿入先の前ポインタ取得(確実に存在)
        nex_pitem=bef_pitem->next;              // 挿入先の次ポインタ保持(NULLのときもあり)
        pitem = new LIST_ITEM<T>;       // 末尾アイテムのnextに新リスト作成
        pitem->t = t;                                   // 新リストにアイテム代入
        pitem->before=bef_pitem;
        pitem->next=nex_pitem;
        bef_pitem->next = pitem;
        if (nex_pitem) nex_pitem->before = pitem;
                item_length++;
                last_use        =pitem;
                last_use_id     =n;
        return item_length;
};

// アイテム削除    (第n番目のアイテム削除)   
template <class T> XLIST<T>::pop(int n){
        if (item_length<=0) return 0;           // LISTアイテムなし
        LIST_ITEM<T> *del, *bef, *nex;
        if (n<0 || n>=item_length) del=tail;    // n が範囲外なら末尾を削除
        else del = get_ptr(n);
        if (del==head) return 0;
        bef = del->before;      // 削除アイテムの前のノードGET
        nex = del->next;        // 削除アイテムの次のノードGET
        bef->next=nex;          // 前のノードは確実に存在するのでじかに更新
        if (nex) {
                nex->before=bef;        // 削除アイテムが末尾なときnexはNULLなので回避
        }
        else tail=bef;
        delete del;
        item_length--;
                last_use        =bef;   // 最後にアクセスしたアイテム更新(前のノードに代入)
                last_use_id     =n-1;
        return item_length;
}

// tの値と同じアイテムの削除
template <class T> XLIST<T>::val_pop(T t){
        LIST_ITEM<T> *p;
        for(int i=0;i<item_length;i++){
                p=get_ptr(i);
                if (p->t==t) {
                        pop(i);
                        return 1;
                }
        }
        return 0;
};


#endif  // _XLIST_H_



         


リファレンス

【XLIST】
     拡張リスト構造
アイテム追加(push)は必ず引数のコピーが渡されますので、cstringクラスのような内部でメモリ確保してるようなクラスは引数コピーでデストラクタが呼ばれます。
XLISTのデストラクタで各アイテムのデストラクタが呼び出されます
汎用関数

・push(T t, int n);
   リストにアイテムを追加します
戻り値 新しいアイテム数を返します

リストのn番目の位置にアイテムを追加します
nを省略するか、またn==-1のとき追加位置はリスト末尾になります
追加されるアイテムは引数のコピーになります

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

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

・val_pop(T t);
リストからアイテムを削除します
戻り値 削除に成功したら1、削除するアイテムがなかったら0を返します

リスト内のアイテムで引数と同じ値のアイテムを1つ削除します

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

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

リストのn番目のアイテムを参照します。じかに代入もできます。

・del_all();
アイテムをすべて削除します
戻り値 必ず0が返ります

リストのアイテム全てを削除します。
各アイテムのデストラクタも自動で呼ばれます

・roll(int n1, int n2);
第n1番目のアイテムを第n2番目に移動します
戻り値 アイテム数を返します


例:1番目のアイテムを末尾に移動したりすると2番目以降の順番が全て繰り上がり2番目のアイテムが先頭になります

・swap(int n1, int n2)
リストのn1番目とn2番目を入れ替えます
戻り値 必ず0が返ります

・set_default(T &t);
リスト外アクセス時の値を 引数の値t に設定します
戻り値 必ず0が返ります

リストにまったくアイテムが無かったり
第n番目のアイテムにアクセスしようとしたときにアイテム数がnより少ないときに返る値が 引数の値t になります

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

変更前のアイテム数がn個より大きければn+1番目以降のアイテムは削除されます

●XLIST サンプル
#include "xlist.h"

int main(){
    XLIST<int> list;    // int型のリストを宣言
    list.push(20);      // アイテムを追加
    list.push(21);
    list.push(22);
    list.push(23);
    list.push(24);
    list.push(25);
    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());   // リストアイテム数を表示
    list.resize(4);                             // アイテムの数を4個にする
    printf("list.size(); %d\n", list.size());   // リストアイテム数を表示
    return 0;
}
実行結果


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

     -      ホームへ  →次へ  001-02