本家のオンラインマニュアル

データ構造：便利なクラス

　wxWidgetsはGUI構築だけでなく，データ処理に関しても便利で有用なクラスを提供しています． 具体的には配列（wxArray），リスト（wxList）， ハッシュマップ（wxHashMap）というものです． これらのデータ構造のクラスに類似のものはC++の標準ライブラリにもありますが， それらよりも柔軟性の高いものが提供されており， ここではサンプルプログラムを例に挙げながらwxWidgetsが提供するデータ構造のクラスに関して説明します．

■配列　　 ■リスト　　 ■ハッシュマップ

■ 扱うデータのサンプル

　下に英和辞書のデータ"edic.txt"を示します．このデータは4万件以上のレコードから成るもので， これを格納するケースを例に，様々なデータ構造について説明します．

英和辞書データ：edic.txt 
　　　　　：
　　　　　：
petrel	ウミツバメ 
Petri dish	ペトリ皿(細菌培養などに用いる,ゆるいふたの付いた浅いガラス製またはプラスチック製の透明な
petrifaction	石化[作用];〈C〉石化物,化石 
petrify	〈有機物など〉‘を'石化する,化石にする / (恐怖・驚きなどが)〈人〉‘の'体を石のようにする,すく
petrochemical	石油化学製品 / 石油化学[製品]の
petrography	岩石分類学,記載岩石学 
　　　　　：
　　　　　：
データ提供：「くじらはんど」

　このデータはくじらはんど で配信されているものを加工して，各レコードを

　　　英単語 ＜TAB＞ 日本語での意味

の形に整形したものです．レコードを1つづつ読み取り， 英語と日本語に分離して格納してゆくプログラムを考えることにします．

■ 配列　

　wxWidgetsには，指定したクラスのオブジェクトを複数格納する配列のクラス wxArray があります．このクラスで扱う配列のサイズ（要素の個数の上限）は予め固定されたものではなく， データの追加に応じて順次拡張されます． wxArrayクラスを元にして配列のクラスを定義するためのマクロ WX_DECLARE_OBJARRAY があり，これを使うのが便利です．

　下のサンプルプログラム "edic3.cpp" を見てください．プログラムの前半で定義されている関数 split は，ファイル "edic.txt" から読み込んだレコードを英語と日本語の部分に分離して， それぞれをe,jのポインタが示す記憶に複写するものです． また関数splitで得られた英語，日本語のデータへのポインタからなるクラスCellClassがあり， このクラスのインスタンスcellを配列（DicClassのインスタンスdic）に順番に追加します．

　ファイルから読み込んだ全てのデータを配列dicに読み取った後は， キーボードから「〜番目」のインデックスを与えて，配列の要素を表示します．

プログラム全体：edic3.cpp 
#include　　＜wx/wx.h＞
#include　　＜iostream＞

//////////////////////////////////////////////////////////
// Splitting English / Japanese				//
//////////////////////////////////////////////////////////

void split(char *buf, char *e, char *j)
{
    int	i, k, l;

    l = strlen(buf) - 1;
    for ( i = 0; i < l; i++ ) {
        if ( buf[i] == '\t' ) {
            e[i] = 0;
            break;
        } else {
            e[i] = buf[i];
        }
    }
    i++;

    for ( k = i; k < l; k++ ) {
        j[k-i] = buf[k];
    }
    j[k-i] = 0;
}


//////////////////////////////////////////////////////////
// Main Routine						//
//////////////////////////////////////////////////////////

class CellClass	{
  public:
    char	*E;
    char	*J;
    //--- constructor ---
    CellClass(char *E, char *J);
};

//--- constructor ---
CellClass::CellClass(char *e, char *j)
{
    E = e;
    J = j;
}

WX_DECLARE_OBJARRAY( CellClass, DicClass );

DicClass::~DicClass()
{
}

int main()
{
    long	n;
    FILE	*f;
    char	buf[4096], e[256], j[4096], *e2, *j2;

    CellClass	*cell;
    DicClass	dic;

    //--- Reading Dictionary ---
    f = fopen("edic.txt","r");
    while ( -1 ) {
        if ( fgets(buf,4096,f) == NULL ) {
            break;
        } else {
            split(buf,e,j);
            e2 = (char *)malloc(strlen(e));
            strcpy(e2,e);
            j2 = (char *)malloc(strlen(j));
            strcpy(j2,j);
            cell = new CellClass(e2,j2);
            dic.Add(cell);
        }
    }
    fclose(f);

    //--- Size Check ---
    printf("size of array: %lu\n",dic.size());

    while ( -1 ) {
        printf("Idx: ");
        scanf("%lu",&n);
        if ( n == -1 ) {
            break;
        } else {
            cell = &(dic.Item(n));
            printf("Eng: %s\n",cell->E);
            printf("Jpn: %s\n\n",cell->J);
        }
    }
}

【解説】

　マクロの記述　WX_DECLARE_OBJARRAY( CellClass, DicClass );　は
　　　「CellClassのオブジェクトへのポインタを要素として持つ配列のクラスを
　　　　　DicClass として定義する」
ことを意味します．

　main関数の中で，CellClassのインスタンスとして *cell， DicClassのインスタンスとして dic を生成しています．cellが示す記憶に辞書のデータをセットした後， Add()関数 を使ってそのアドレスを要素として dic に追加しています．

　配列の要素の数（配列のサイズ）はsize()関数を使って調べることができます．

　インデックス（〜番目の数値）を指定して配列の要素にアクセスするにはItem()関数を使用します．

● wxArrayの特徴

　配列はインデックスの指定に対して迅速に要素にアクセスするためのデータ構造です． 特徴として，任意のインデックス位置に対して要素の追加削除を頻繁に行う処理にはあまり向きません． 要素の挿入と削除を頻繁に行う処理には，次に紹介するリストの方が向いています．

［ページトップへ］

■ リスト　

　wxWidgetsには，指定したクラスのオブジェクトを複数格納する連結リストのクラス wxList があります．連結リストは「セル」と呼ばれる記憶単位を次々と連結してデータを格納するものです． wxListクラスを元にしてリストのクラスを定義するためのマクロ WX_DECLARE_LIST, WX_DEFINE_LIST があり，これらを使うのが便利です．

　下のサンプルプログラム "edic2.cpp" を見てください．先のプログラムと全く同じ関数 split と， クラス CellClass があり，ファイル "edic.txt" から読み込んだレコードを英語と日本語の部分に分離して， 記憶に複写して保持します． CellClassのインスタンスcellを要素とする連結リスト（DicClassのインスタンスdic）を作成します．

　ファイルから読み込んだ全てのデータをリストdicに連結した後は， キーボードから「〜番目」のインデックスを与えて，リストの要素（セル）の中身を表示します．

プログラム全体：edic2.cpp 
#include　　＜wx/wx.h＞
#include　　＜iostream＞

//////////////////////////////////////////////////////////
// Splitting English / Japanese				//
//////////////////////////////////////////////////////////

void split(char *buf, char *e, char *j)
{
    int	i, k, l;

    l = strlen(buf) - 1;
    for ( i = 0; i < l; i++ ) {
        if ( buf[i] == '\t' ) {
            e[i] = 0;
            break;
        } else {
            e[i] = buf[i];
        }
    }
    i++;

    for ( k = i; k < l; k++ ) {
        j[k-i] = buf[k];
    }
    j[k-i] = 0;
}


//////////////////////////////////////////////////////////
// Main Routine						//
//////////////////////////////////////////////////////////

class CellClass	{
  public:
    char	*E;
    char	*J;
    //--- constructor ---
    CellClass(char *E, char *J);
};

//--- constructor ---
CellClass::CellClass(char *e, char *j)
{
    E = e;
    J = j;
}


#include　＜wx/listimpl.cpp＞
WX_DECLARE_LIST( CellClass, DicClass );
WX_DEFINE_LIST( DicClass )

int main()
{
    long	n;
    FILE	*f;
    char	buf[4096], e[256], j[4096], *e2, *j2;

    CellClass	*cell;
    DicClass	dic;

    //--- Reading Dictionary ---
    f = fopen("edic.txt","r");
    while ( -1 ) {
        if ( fgets(buf,4096,f) == NULL ) {
            break;
        } else {
            split(buf,e,j);
            e2 = (char *)malloc(strlen(e));
            strcpy(e2,e);
            j2 = (char *)malloc(strlen(j));
            strcpy(j2,j);
            cell = new CellClass(e2,j2);
            dic.Append(cell);
        }
    }
    fclose(f);

    //--- Size Check ---
    printf("size of list: %lu\n",dic.size());

    while ( -1 ) {
        printf("Idx: ");
        scanf("%lu",&n);
        if ( n == -1 ) {
            break;
        } else {
            cell = dic.Item(n)->GetData();
            printf("Eng: %s\n",cell->E);
            printf("Jpn: %s\n\n",cell->J);
        }
    }

    dic.Clear();
}

【解説】

　マクロの記述
　　　WX_DECLARE_LIST( CellClass, DicClass );
　　　WX_DEFINE_LIST( DicClass )
は，
　　　「CellClassのオブジェクトへのポインタをセルとする連結リストのクラスを
　　　　　DicClass として定義する」
ことを意味します．またこれらマクロの記述に先立って
　　　#include　＜wx/listimpl.cpp＞
を記述して必要な定義ファイルをインクルードしておく必要があります．

　main関数の中で，CellClassのインスタンスとして *cell， DicClassのインスタンスとして dic を生成しています．cellが示す記憶に辞書のデータをセットした後， Append()関数 を使って，そのアドレスが示す記憶の内容をセルとして dic に追加しています．

　リストのセルの数（リストの長さ）はsize()関数を使って調べることができます．

　インデックス（〜番目の数値）を指定してリストのセルにアクセスするには Item(n)->GetData() を実行します．

● wxListの特徴

　リストはセルの追加（挿入）と削除が迅速に行えるデータ構造ですが， 任意のインデックス位置を指定したセルへのアクセスが頻発する処理にはあまり向きません． 要素へのランダムアクセスを行う処理には，先に紹介した配列の方が向いています．

［ページトップへ］

■ ハッシュマップ　

　いわゆる「連想配列」とも呼ばれるデータ構造で，数値以外のデータをキー（key） にしてデータ（値）を読み書きするものです．「データベース的なもの」を作る際に重宝するデータ構造で， キーを指定することで大量のデータの中から迅速にデータを取り出すことができます． 今回のように辞書のデータを記憶に保持して，任意の単語に対する意味を取り出す処理には最適なデータ構造です．

　下のプログラム edic1.cpp は辞書データを読み込んで， 英単語をキー，日本語の意味を値とするハッシュマップ dic に登録します． その後，ユーザからの英単語の入力を受け，それに対する日本語の意味を表示します．

プログラム全体：edic1.cpp 
#include　　＜wx/wx.h＞
#include　　＜iostream＞

//////////////////////////////////////////////////////////
// Splitting English / Japanese				//
//////////////////////////////////////////////////////////

void split(char *buf, char *e, char *j)
{
    int	i, k, l;

    l = strlen(buf) - 1;
    for ( i = 0; i < l; i++ ) {
        if ( buf[i] == '\t' ) {
            e[i] = 0;
            break;
        } else {
            e[i] = buf[i];
        }
    }
    i++;

    for ( k = i; k < l; k++ ) {
        j[k-i] = buf[k];
    }
    j[k-i] = 0;
}


//////////////////////////////////////////////////////////
// Main Routine						//
//////////////////////////////////////////////////////////

WX_DECLARE_STRING_HASH_MAP( char*,   DicClass );

int main()
{
    FILE	*f;
    char	buf[4096], e[256], j[4096], *v;

    DicClass dic(DicClass(100000));

    //--- Reading Dictionary ---
    f = fopen("edic.txt","r");
    while ( -1 ) {
        if ( fgets(buf,4096,f) == NULL ) {
            break;
        } else {
            split(buf,e,j);
            v = (char *)malloc(strlen(j));
            strcpy(v,j);
            dic[wxString(e)] = v;
        }
    }
    fclose(f);

    //--- Inquiry ---
    while ( -1 ) {
        printf("Eng: ");
        scanf("%s",e);
        if ( strcmp(e,"quit()")==0 ) {
            break;
        } else if ( dic.find(wxString(e)) == dic.end() ) {
            printf("\t(no data)\n");
        } else {
            v = dic[wxString(e)];
            printf("Jpn: %s\n\n",v);
        }
    }
}

【解説】

　マクロの記述　WX_DECLARE_STRING_HASH_MAP( char*, DicClass );　は，
　　　「wxStringクラスのオブジェクトをキーとするハッシュマップのクラスを
　　　　　DicClass として定義する」
ことを意味します．

　main関数の中で，DicClassのインスタンスとして dic を生成しています．普通は
　　　DicClass dic;
とすれば良いのですが，格納するデータの量が大きい場合は，このプログラムのように
　　　DicClass dic(DicClass(100000)); として，必要とする記憶域の大きさの目安を与えておくと安全です． （悪くするとプログラム実行時に Segmentation fault を起こしたりします）

　ハッシュマップへのデータの読み書きは簡単で，
　　　dic[ キー ] = 値
とすることでキーに対する値を設定することができ，値を参照する際は単に
　　　dic[ キー ]
を参照するだけです．

　登録されているマップの数はsize()関数を使って調べることができます．

● イテレータ

　マップのデータを順番に参照するにはイテレータを使用します．例えば，
　　　DicClass::iterator it;
　　　for ( it = dic.begin(); it != dic.end(); it++ ) {
　　　　　　（it->first()　にキーが，it->second() に値が得られる）
　　　　　　（処理）
　　　}
のようにループを構成すると，マップのデータに1件づつアクセスすることができます．

［ページトップへ］

2014/09/12