darake
Update:
ダブルポインタ(ポインタのポインタ)のメリットや使い道を紹介する
C言語では、ポインタを使うことで柔軟なデータ構造を表現できるが、今までダブルポインタ(ポインタのポインタ)についてイマイチ理解できていなかった。
色々調べていくと、ダブルポインタのメリットや使い道が分かってきたので、紹介していく。
ダブルポインタのメリットや使い道とは？
ダブルポインタのメリットとしては、様々なデータ型を格納できる動的配列を作れる、と言う点が挙げられる。
C++には、Vectorと呼ばれている便利なデータ構造が使える。このVectorはC言語の配列の強化版みたいなもので、好きなデータ型を自由に追加、削除ができるし、配列の大きさも自動で変更してくれる。(例えば、配列の0番目がint型、1番目が文字列型の様にもできる！）
一方で、Ｃ言語の配列は非常に機能が弱く、int array[5]と宣言するとint型しか要素が使えないし、6つ以上の要素を追加することができない。
int *array = (int *)malloc(sizeof(int) * 20);
array[0] = 32;
しかし、ダブルポインタを使えば、要素に様々な型のデータを入れることができるようになる。(ただし、ポインタに限る)
ダブルポインタを使った動的配列
では、ダブルポインタを使って動的配列を作るとどうなるかを見ていく。
まずは、動的配列のデータ構造は以下の通りになる。ポイントとしては、動的配列の中身を**bodyのようにダブルポインタを使うことと、動的配列が確保しているメモリの数を記憶しておく変数sizeを用意すること。
typedef struct _Vector VECTOR;
struct _Vector
{
int size; // 動的配列が確保しているメモリ数
int index; // 動的配列のindex
void **body; // 動的配列の中身
};
この動的配列を初期化するために、vec_make関数を用意する。
#define INIT_SIZE 10
VECTOR vec_make(int size)
{
void *body = malloc(sizeof(void *) * INIT_SIZE);
VECTOR vec = {
.size = size, .alloc_num = INIT_SIZE, .index = 0, body = body};
return vec;
}
重要な点は、void *body = malloc(sizeof(void *) * INIT_SIZE);のように、void型のポインタの配列を作って、その配列のアドレスをbodyに格納すると言うこと。
void型のポインタにすることで、様々なデータ型のポインタを格納することができるようになる
次に、動的配列に要素を追加するための関数vec_pushを用意する。
void vec_push(VECTOR *vec, void *p)
{
vec->body[vec->index++] = p;
}
引数のvoid *pには好きなデータ型のポインタを入れることができ、そのポインタを動的配列の要素に格納することができる。
本来は「vec->indexが動的配列の大きさよりも小さいか？」などの判定をすべきだが、サンプルコードと言う事で省略している。
また、動的配列の要素を取得するためのvec_getを用意。
void *vec_get(VECTOR *vec, int index)
{
return vec->body[index];
}
そして、main関数で以下のように実行する。
int main()
{
VECTOR vec = vec_make(5);
char *str = "I am tarou";
int i = 15;
vec_push(&vec, str);
vec_push(&vec, &i);
char *str1 = vec_get(&vec, 0);
char *ip = vec_get(&vec, 1);
printf("str is %s\n", str1);
printf("int is %d\n", *ip);
return 1;
}
上記の動的配列vecの0番目の要素にはchar *型が格納され、1番目の要素にはint *型が格納されるようになる。今回はchar *とint *型を配列に格納したが、構造体のポインタを格納するのが一般的だと思う。
リスト構造との違いは？
ダブルポインタを使った動的配列でなくとも、連結リストでデータを表現できることが多い。
typedef struct _List
{
int x;
struct _List *next;
} List;
しかし、連結リストの計算量はO(n)となっており、要素の数が多ければ検索の時間を大きくなっていく。一方、ダブルポインタを使った動的配列であれば計算量はO(1)なので、連結リストよりも高速であるメリットがある。
もちろん、連結リストも動的配列もそれぞれに良さがあるので、状況に応じて使い分けるのが良い。