C言語で動的配列（vector）を実装する

c++には動的配列としてvectorがあります。これをcで実現することを考えてみます。<br>

#### データ構造
データをint型として実装してみる。データ格納構造は配列（array）だが、動的に配列の大きさを変更するために、配列の大きさ（size）が必要である。そこで、配列の要素数と配列の先頭アドレス（int型へのポインタ）を持つ構造体とする。<br>
![データ構造.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4054118/6e5a1c1d-ef84-44e6-8ce9-51869202bb72.jpeg)<br>
```
struct Vector {
  int size;
  int *array;
};
``` 

#### vector変数の宣言
構造体Vectorの変数として宣言し、初期化する。<br>
```
  struct Vector v;              /* declare struct Vector variable */
  vector_init(&v, 0);           /* initialize, set size = 0 */
```
初期化は、以下の関数で行う。ここでは、配列の初期大きさをnとして、sizeの設定と、n個分の配列要素のメモリ領域を確保してそのメモリ領域の先頭アドレスをポインタarrayに設定する。<br>
```
void vector_init(struct Vector *pvec, int n) {
  pvec->size = n;
  if (n == 0) {
    pvec->array = NULL;                 /* no element */
  } else {
    pvec->array = malloc(sizeof(int) * n);
  }
  return;
}
```

#### pushback:要素の追加
配列の最後尾にデータを追加する。データを追加するので、arrayのアドレスに割り当てているメモリ領域を1要素分増やす。arrayが指し示すアドレスのメモリ領域を増やして、再割り当てする。再割り当てするメモリ領域の大きさは、sizeに要素数が入っているので分かる。当然size変数は+1しておく。<br>
![pushback.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4054118/dd8f3502-46e6-4a0f-b889-da3e9d1745a9.jpeg)<br>
```
void vector_pushback(struct Vector *pvec, int x) {
  pvec->size++;                         /* array size increment */
  pvec->array = realloc(pvec->array, sizeof(int) * pvec->size);
  pvec->array[pvec->size - 1] = x;      /* set at end of array */
  return;
}
```

#### find:要素の探索
指定した値の要素の位置を返す。指定した値の要素が存在しない場合は、配列の最後の要素の次の位置（要素の位置は0から始まるので、要素数がNの場合はN）を返す。<br>
```
int vector_find(struct Vector *pvec, int x) {
  int i = 0;
  while (i < pvec->size && pvec->array[i] != x) {
    i++;
  }
  return i;
}
```

#### erase:要素の消去
指定する値の要素を配列から削除する。削除した要素以降の要素は前詰めする。要素数が-1されるので、sizeを更新し、配列のメモリ領域を1減らして再割り当てし、その先頭アドレスをarrayにセットする。<br>
![erase.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4054118/882b5cb8-0563-4158-a425-4fbe594f36f9.jpeg)<br>
```
void vector_erase(struct Vector *pvec, int x) {
  int n = vector_find(pvec, x);
  if (n < pvec->size) {
    for (int i = n; i < pvec->size - 1; i++) {  /* after erase element */
      pvec->array[i] = pvec->array[i + 1];      /* left-justified */
    }
    pvec->size--;                               /* size decrement */
    pvec->array = realloc(pvec->array, sizeof(int) * pvec->size);
  }
  return;
}
```

#### vector_put:要素の値の変更
配列の中の位置をiで指定（位置は0スタート）し、その位置の要素の値をxにする。配列の中の位置iの要素pvec->array[i]にxを代入している。配列の中の位置を指定する引数が配列の範囲を超えている場合は、何もしない。<br>
```
void vector_put(struct Vector *pvec, int i, int x) {
  if (i < pvec->size) {
    pvec->array[i] = x;
  }
  return;
}
```

#### vector_at:要素の値の取得
配列の中の位置をiで指定（位置は0スタート）し、その位置の要素の値を返す。配列の中の位置を指定する引数が配列の範囲を超えている場合は、その位置＝アドレスに格納されている値を返す。配列の範囲を超えているかどうかの判断はできるが、関数の戻り値は整数なので、戻り値で「範囲外指定」の区別ができない。戻り値が配列の範囲内であることを、プログラマが確認することにする。<br>
```
int vector_at(struct Vector *pvec, int i) {
  return pvec->array[i];
}
```

#### 使い方
構造体Vector変数の宣言と初期化、値の追加、削除、取得をする例である。<br>
```
  struct Vector v;
  vector_init(&v, 0);           /* initialize vector */
  ...
  int x = 0;
  vector_pushback(&v, x);       /* push back */
  ...
  x = vector_at(&v, 0);         /* get item from vector */
  x++;
  vector_put(&v, 0, x);         /* set value to item in vector */
  ...
  vector_pushback(&v, 0);
  ...

  /\* print vector \*/
  for (int i = 0; i < v->size; i++)
    printf("%d ", vector_at(&v, i));
  printf("\n");
```

#### 構造体を使わない（int型配列の場合）
データ構造としては、配列の要素数を何らかの方法で持っていればいい。配列がint型の配列の場合、配列のどこかに配列の要素数を持つことにすれば、構造体にせず配列で表現できる。<br>
![データ構造2.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4054118/26e3c657-2563-4a1d-b04b-2bdc7432de27.jpeg)<br>

ただし、配列の大きさを動的に可変にするために、変数は配列ではなく、配列の先頭アドレスとし、変数が示すアドレスに配列を作成する。<br>
```
  int *v = vector_init(0);
```
ここで、<br>
```
int* vector_init(int n) {
  int *vec =  malloc(sizeof(int)*(n+1));/* create vector with 1 element */
  vec[0] = n;                           /* top element = size */
  return vec;
}
```
である。配列の先頭要素vec[0]に要素数をセットしている。<br>

追加、削除の場合は、配列全体のサイズを動的に変化させてその先頭アドレスでポインタ変数を更新すればいい。値の取得、代入は配列としても行うことができる（ただし、添え字が+1となる）。<br>
```
void vector_pushback(int *vec, int x) {
  int size = vec[0] + 1;                /* array size increment */
  int *p = realloc(vec, sizeof(int) * (size + 1));
  vec = p;
  vec[0] = size;                        /* array size update */
  vec[size] = x;                        /* set at end of array */
  return;
}

int vector_find(int *vec, int x) {
  for (int i = 0; i < vec[0]; i++) {    /* top element = size */
    if (vec[i + 1] == x) {              /* content start from index 1 */
      return i;
    }
  }
  return vec[0];
}

void vector_erase(int *vec, int x) {
  int n = vector_find(vec, x);
  if (n < vec[0]) {
    for (int i = n; i < vec[0]; i++) {  /* after erase element */
      vec[i + 1] = vec[i + 2];          /* left-justified */
    }
    vec[0]--;                           /* size decrement */
    int *p = realloc(vec, sizeof(int) * vec[0]);
    vec = p;
  }
  return;
}

void vector_put(int *vec, int i, int x) {
  if (id < vec[0]) {
    vec[i + 1] = x;
  }
  return;
}

int vector_at(int *vec, int i) {
  return vec[i + 1];
}
```