C言語で可変長配列ArrayListを実装する

n-ozawan

2024.05.01

プログラム C/C++ 実用性0

皆さん、こんにちは。技術開発グループのn-ozawanです。
GWですね。この時期に観光客で大混雑する鎌倉では、徒歩で移動するように呼び掛ける実証実験をしています。

本題です。
C言語で実装しているとき、JavaのArrayListのような可変長配列が欲しいと思ったことはありませんか？今回はC言語でArrayListを実装してみたいと思います。

C言語でArrayList

ゴール

C言語で可変長配列を実現するArrayListを実装します。今回はあくまでサンプル程度なので、要素の追加、要素の挿入、要素の取得、配列長の取得の計４メソッドを作成します。ArrayListが分からない方は、過去に投稿した「JavaのArrayListとLinkedListの違いを理解して使い分ける」を参照ください。

List インターフェース

まずはListインターフェースを実装します。「インターフェイス？オブジェクト指向言語じゃないのに何言ってんだ？」と思った方は、過去に投稿した、C言語でオブジェクト指向プログラミング（1回目、2回目）を参照ください。

// メンバ変数
typedef struct _List {
  void (*List_add)(struct _List* list, void* element);
  void (*List_insert)(struct _List* list, int index, void* element);
  const void* (*List_get)(const struct _List* list, int index);
  int (*List_size)(const struct _List* list);
} List;

// メソッド
void List_add(List* list, void* element) {
  if (list->List_add) {
    list->List_add(list, element);
  } else {
    printf("not implemented.\n");
  }
}

// 以下略。
// List_insert(...), List_get(...), List_size(...) も、List_add(...)と同じように実装する。

コンストラクタとデストラクタ

ArrayListのコンストラクタとデストラクタを実装します。

// メンバ変数
typedef struct {
  List parent;        // 継承
  void* array;        // 配列の実体
  int sizeOfElement;  // 要素1個分のサイズ
  int length;         // 配列に格納した要素数
  int maxLength;      // メモリ確保した配列の数
} ArrayList;

// コンストラクタ
ArrayList* ArrayList_new(int sizeOfElement) {
  ArrayList* list = (ArrayList*)malloc(sizeof(ArrayList));

  // 初期配列の作成
  list->length = 0;
  list->maxLength = 10;
  list->sizeOfElement = sizeOfElement;
  list->array = (void*)malloc(sizeOfElement * list->maxLength);

  // オーバーライド
  list->parent.List_add = ArrayList_add;
  list->parent.List_insert = ArrayList_insert;
  list->parent.List_get = ArrayList_get;
  list->parent.List_size = ArrayList_size;
  return list;
}

// デストラクタ
void ArrayList_delete(ArrayList* arraylist) {
  if (arraylist->array) free(arraylist->array);
  free(arraylist);
}

arrayに配列の実体を保持しています。初回は要素数10個分のメモリを確保します。そしてListインターフェースにArrayListの各関数ポインタを設定します。arrayの型をvoid*にしている理由は、構造体の配列も出来るようにするためです。

要素の取得

要素を取得する処理を実装します。

const void* ArrayList_get(const List* list, int index) {
  ArrayList* arraylist = (ArrayList*)list;
  return arraylist->array + (index * arraylist->sizeOfElement);
}

配列の実体arrayの先頭から、指定されたindexまでのアドレス値を返却するだけです。

要素の追加

要素を追加する処理を実装します。

int ArrayList_ensureCapacity(ArrayList* arraylist, int minCapacity) {
  void* newarray = realloc(arraylist->array, arraylist->sizeOfElement * minCapacity);
  if (newarray == 0) {
    printf("out of memory.");
    return -1;
  }
  arraylist->maxLength = minCapacity;
  arraylist->array = newarray;
  return 0;
}

void ArrayList_add(List* list, void* element) {
  ArrayList* arraylist = (ArrayList*)list;
  if (arraylist->length == arraylist->maxLength) {
    int result = ArrayList_ensureCapacity(arraylist, arraylist->maxLength * 1.4);
    if (result != 0) return;
  }
  memcpy(arraylist->array + (arraylist->length * arraylist->sizeOfElement), element, arraylist->sizeOfElement);
  arraylist->length += 1;
}

ArrayList_add関数の第2引数に追加したい要素を指定します。もし確保した全ての配列要素を使用している場合は、ArrayList_ensureCapacity関数で配列を拡張します。メモリの再確保にはrealloc関数を使用しています。配列の拡張に成功したら、memcpy関数で末尾に要素を書き込みます。

要素の挿入

要素を挿入する処理を実装します。

void ArrayList_insert(List* list, int index, void* element) {
  ArrayList* arraylist = (ArrayList*)list;
  if (arraylist->length == arraylist->maxLength) {
    int result = ArrayList_ensureCapacity(arraylist, arraylist->maxLength * 1.4);
    if (result != 0) return;
  }
  memcpy(arraylist->array + ((index + 1) * arraylist->sizeOfElement), 
         arraylist->array + (index * arraylist->sizeOfElement),
         (arraylist->length - index) * arraylist->sizeOfElement);
  memcpy(arraylist->array + (index * arraylist->sizeOfElement), element, arraylist->sizeOfElement);
  arraylist->length += 1;
}

ArrayList_insert関数の第2引数に挿入先のindexと、第3引数に挿入したい要素を指定します。ArrayList_insert関数でも必要であればArrayList_ensureCapacity関数で配列を拡張します。配列の拡張に成功したら、挿入したい要素より後ろの要素を、１つずらすようにコピーしてから、データを挿入します。

配列長の取得

配列長を取得する処理を実装します。

int ArrayList_size(const List* list) {
  ArrayList* arraylist = (ArrayList*)list;
  return arraylist->length;
}

内部で保持しているlenghtを返却しているだけです。

使い方

実装したコードを使ってみましょう。

void process(List* list) {
  // 配列の末尾に追加
  for (int i = 0; i < 20; i++) {
    List_add(list, &i);
  }

  // 配列の途中に挿入
  int value = 99;
  List_insert(list, 10, &value);

  // 結果を出力
  for (int i = 0; i < List_size(list); i++) {
    int* value = (int*)List_get(list, i);
    printf("%d ", *value);
  }
  printf("\n");
}

int main() {
  ArrayList* arraylist = ArrayList_new(sizeof(int));

  process((List*)arraylist);
  // Output: 0 1 2 3 4 5 6 7 8 9 99 10 11 12 13 14 15 16 17 18 19 

  ArrayList_delete(arraylist);
  return 0;
}

main関数はArrayListのインスタンスの生成と破棄を行います。本処理はprocess関数になります。process関数では数値を追加もしくは挿入して、その内容をprintf関数で出力しているだけになります。また、process関数ではListインターフェースで実装していますので、汎用性のあるコードになっていることが分かると思います。

おわりに

void*で実装しているとジェネリクスが恋しくなります。今回調べていると、C11から_Genericというマクロが追加されていることを知りました。私がC言語の開発から離れて10年以上経過するのですが、まだまだC言語も成長していると思うと、感慨深いものがあります。今年のGWは_Genericで遊ぼうかな。

ではまた。