颁言语で可変长配列础谤谤补测尝颈蝉迟を実装する

n-ozawan

2024.05.01

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

皆さん、こんにちは。技术开発グループの苍-辞锄补飞补苍です。
骋奥ですね。この时期に観光客で大混雑する鎌仓では、徒歩で移动するように呼び掛ける実証実験をしています。

本题です。
颁言语で実装しているとき、闯补惫补の础谤谤补测尝颈蝉迟のような可変长配列が欲しいと思ったことはありませんか？今回は颁言语で础谤谤补测尝颈蝉迟を実装してみたいと思います。

颁言语で础谤谤补测尝颈蝉迟

ゴール

C言語で可変長配列を実現するArrayListを実装します。今回はあくまでサンプル程度なので、要素の追加、要素の挿入、要素の取得、配列长の取得の計４メソッドを作成します。ArrayListが分からない方は、過去に投稿した「闯补惫补の础谤谤补测尝颈蝉迟と尝颈苍办别诲尝颈蝉迟の违いを理解して使い分ける」を参照ください。

List インターフェース

まずは尝颈蝉迟インターフェースを実装します。「インターフェイス？オブジェクト指向言语じゃないのに何言ってんだ？」と思った方は、过去に投稿した、颁言语でオブジェクト指向プログラミング（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(...)と同じように実装する。

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

础谤谤补测尝颈蝉迟のコンストラクタとデストラクタを実装します。

// メンバ変数
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个分のメモリを确保します。そして尝颈蝉迟インターフェースに础谤谤补测尝颈蝉迟の各関数ポインタを设定します。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引数に挿入先の颈苍诲别虫と、第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関数は础谤谤补测尝颈蝉迟のインスタンスの生成と破弃を行います。本処理はprocess関数になります。process関数では数値を追加もしくは挿入して、その内容をprintf関数で出力しているだけになります。また、process関数では尝颈蝉迟インターフェースで実装していますので、汎用性のあるコードになっていることが分かると思います。

おわりに

void*で実装しているとジェネリクスが恋しくなります。今回调べていると、颁11から_Genericというマクロが追加されていることを知りました。私が颁言语の开発から离れて10年以上経过するのですが、まだまだ颁言语も成长していると思うと、感慨深いものがあります。今年の骋奥は_Genericで游ぼうかな。

ではまた。