ArrayListの実装

まず、名前の付け方について一言：

選択した名前タイプ_arraylistは、ライブラリインターフェイスタイプの不適切な名前です。 _で始まる名前は、ユーザーコードでの操作が快適ではありません。これらは通常、ライブラリ内部で使用されます。より適切な名前は、ArrayListまたはarray_listです。

実際、使用例では、ArrayList。これは、ここに含まれていないヘッダーに次のようなものがあることを意味しますか？

typedef _arraylist ArrayList; 

ヘッダーに不透明（OPAQUE）型を定義した場合、上記のように、それは良い習慣です。ただし、コードで_arraylistへの参照を使用しないでください。混乱を避けるために、常にtypedef “d名を使用してください。

関数名のプレフィックスも型の名前に正確に従う必要があるため、ArrayListの場合はすべての関数を接頭辞ArrayList_例：

ArrayList * ArrayList_create(); 

また、の名前（arraylist_getsize()など）。単語を区切るために下線を追加すると、読みやすくなります。例：ArrayList_get_size() 。

メモリの問題：

arraylist_create()：

struct _arraylist *arraylist_create() { struct _arraylist *list = malloc(sizeof(struct _arraylist)); assert(list != NULL); list->size = 0; list->data = calloc(2, sizeof(void *)); assert(list->data != NULL); list->data[0] = NULL; return list; } 

ここで最初に珍しいのはアサーションです。アサーションは、メモリ割り当ての失敗を処理する適切な方法ではありません。 、これらは通常、リリースビルドでは無効になっているため、リリース時にメモリが不足した場合、プログラムはサイレントにクラッシュします。この場合、おそらくNULLを返し（おそらくstderrにもログを記録します）、発信者にこのエラーを処理させる必要があります。適合。

ここでの2番目の問題は、calloc()です。 2つのvoidポインターを割り当てていますが、sizeはゼロに設定されています。私は実際にはこれのポイントを理解していません。あなたの構造はリストよりも配列の配列に似ているので、あなたがすべきことは、事前定義されたデフォルトサイズでポインタの配列を割り当て、次に必要に応じて個々の配列を割り当てることです。オンデマンドのポインタの配列。arraylist_create()の外観：

ArrayList * ArrayList_create() { ArrayList *list = malloc(sizeof *list); if (list == NULL) { return NULL; } list->size = 0; list->data = calloc(INITIAL_BASE_ARRAY_SIZE, sizeof(void *)); if (list->data == NULL) { free(list); // Don"t leek memory here! return NULL; } return list; } 

もう1つの大きなメモリの問題は、定数です。 arraylist_add()とarraylist_remove()によって行われた再割り当て。

削除してもシーケンスは縮小されません。アレイは将来再び大きくなります。必要に応じて、ユーザーがストレージを縮小できるようにする明示的な方法を追加できます（std::vector::shrink_to_fit()）。

に追加する要求されたサイズよりも大きいサイズのストレージを事前に割り当てた場合、アレイを償却済みの一定時間で実行することができます（ここでも、STL vectorに触発されています）。

sizeof間違い：

これでは期待どおりの結果が返されません：

size_t arraylist_getsizeof(struct _arraylist *list) { /* Returns the size of the internal array in memory */ return sizeof(*list->data); } 

sizeof演算子は、常に適用される型のサイズを返します。コンパイル時の操作であるため、ポインタが指す配列のサイズを推測することはできません。 arraylist_getsizeof()は常に同じ値を返します。voidポインタのサイズは、アーキテクチャに応じて4または8になります。

アサーションを使用して不変条件をチェックします：

assertはassertすべての関数のdivid = “1979ffde07”>

パフォーマンスについて話しましょう

リストを頻繁に使用する必要がある場合はどうしますか？

関数arraylist_addを詳しく見てみましょう。100万バイト（1MB）のリストが必要な場合は、data構造体メンバーを100万回。

リストの最下位部分です！

提案

メモリをチャンクで割り当てますたとえば、C ++ std::vectorは、std::vectorの現在のサイズに応じて追加されたチャンクのサイズを増やします。

これは増加します新しい要素を追加する目的で数回実行します。

コードについてそのまま説明します

エレガントでシンプルなプログラムフローを実装してみます。

値タイプ（int）ArrayListを作成します。これにより、代わりにチャンクによってメモリが割り当てられます。完全な配列を再割り当てし、内部でリストの動作を追加します。チャンクのリストを意味しますが、それでも管理する必要があります。

これは、再割り当てする代わりに各ノードにデータのチャンクを使用する例を使用したソリューションです。ノード。目的の1つには、異なるチャンクサイズが最適な場合があります。長い配列の書き込み、読み取り。 r \ w短い配列;要素の削除;など

#include <stdio.h> #include <stdlib.h> typedef struct ArrayList ArrayList; typedef ArrayList* ArrayListPtr; struct ArrayList { size_t capacity; size_t size; int *data; ArrayListPtr parent; ArrayListPtr child; }; const size_t ARRAY_LIST_CHUNCK_SIZE = 64; ArrayListPtr array_list_create_with_parent_and_chunck_size(ArrayListPtr parent, size_t chunck_size) { ArrayListPtr result = (ArrayListPtr)calloc(sizeof(ArrayList), 1); result->parent = parent; result->capacity = chunck_size; result->data = (int*)malloc(sizeof(int) * chunck_size); return result; } ArrayListPtr array_list_create_with_parent(ArrayListPtr parent) { return array_list_create_with_parent_and_chunck_size( parent, ARRAY_LIST_CHUNCK_SIZE ); } ArrayListPtr array_list_create() { return array_list_create_with_parent_and_chunck_size( NULL, ARRAY_LIST_CHUNCK_SIZE ); } void array_list_push_back(ArrayListPtr list, int value) { if (list->size >= list->capacity) { if (!list->child) { list->child = array_list_create_with_parent(list); } array_list_push_back(list->child, value); } else { list->data[list->size++] = value; } } int* array_list_get_value_by_index(ArrayListPtr list, size_t index) { if (index >= list->capacity || index >= list->size) { if (list->child) { return array_list_get_value_by_index(list->child, index - list->size); } else { return NULL; } } return list->data + index; } int main(int argc, char *argv[]) { ArrayListPtr list = array_list_create(); for (int i = 0; i < 100*1000; ++i) { array_list_push_back(list, i); } size_t test[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,31,32,33,63,64,65,999,1000}; for (int i = 0; i < sizeof(test) / sizeof(size_t); ++i) { int* result = array_list_get_value_by_index(list, test[i]); if (result) { printf("list[%ld] = %d\n", test[i], *result); } else { printf("Can"t get value by index %ld\n", test[i]); } } } 

コメント

• 私はあなたの興味を尊重します。ただし、これはCであり、C ++ではありません。 C ++の場合は、ベクトルを使用してそれを実行します。
• @AmrAyman、確認してください
• それは’印象的です！しかし、リンクリストではなく配列リストが必要です。ここでのリンクリストの実装は通常の構造体の実装よりも進んでいますが、glampertは問題を解決しました。
• パフォーマンスの向上について。 ‘それほど多くはありません。私の実装はヒープに依存しています。通常、配列に依存しているためです。あなたは再帰に大きく依存していますが、’ノードに依存しているので、’は当然です。また、リストを解放すると、’再帰（パフォーマンスが非常に低い）を使用するか、かなり複雑になるため、比較的遅くなります。 whileループ..

他の人が言及していない問題は、テストが機能しないことです。動作しているように見えますが、実際には動作しません。リストに値を追加すると、変数iのアドレスが渡されます：

arraylist_add(list, &i); 

およびarraylist_addは、渡された値を（必要に応じて）保存するだけです。

void arraylist_add(struct arraylist *list, void *elem) { .... new_data[list->size] = elem; 

つまり、i = 0をループしたら。 .99リストにあるのはiのアドレスだけです100回。データを読み戻すときは、ループ変数iを再度使用し、その値を0..99から変更すると、出力される値は正しく表示されます。しかし、実際には、ループ変数の値がループによって変更されているのがわかります。

信じられない場合は、次のように50などの固定配列エントリを出力します。

printf("i: %d\n", *(int *)arraylist_get(list, 50)); 

出力されます100（または現在のiの値）

代わりに、実際の値を格納する必要があります：

arraylist_add(list, (void*) i); 

そして印刷する値を入力時の型にキャストする必要があります：

printf("i: %d\n", (int)arraylist_get(list, t)); 

他の人が指摘しているように、コードには他にも多くの問題があります。 。arraylist_setdataを使用してすべての変更を行う基本的な設計は間違っています。変更のたびに再割り当てするのは悪いことです。reallocはコストがかかります。そしてvoid*のふりをしてリストを格納するという基本的な考え方は、私には混乱を招き、悪い考えのようです。

コメント

• 気づかないかもしれませんが、’は正確にテストしたかったものです。ポインタは保存および取得されます。関数ラッパーを介して正しく..
• void *として保存することは’見た目ほど悪くはありません。考えてみてください。void *は単にメモリアドレスを格納するだけで、’に格納されている値のタイプは気にしません。要するに、配列はメモリアドレスのみを格納することになっており、’は、Cが単一の配列でさまざまな型を処理する唯一の方法です..
• reallocについては同意しますが、’ ダイナミックを作成するためのより良い方法を見つけることができませんでした。 b>配列。とにかく、私はそのための特別な関数、shrink_to_fit関数をラップするというglampert ‘のアドバイスに従いました..
• 可変サイズのスカラーデータをvoid*に保存して保存しようとしていると想像しました（さまざまな人がそれを行うためのコードを送信しています）。本当にポインタを保存したい場合は、異なるポインタを既知の順序で保存し、同じ順序で保存するのではなく、同じ順序に戻すことを確認することをお勧めします。ポインタを100回。ポインタを格納する際の問題は、ポイントされたオブジェクトが、配列内にそのアドレスが存在する間、永続的でなければならないことです。 void *にもかかわらず、もちろん1つの配列内で型を混在させることはできません。
• 同じことを行う別の方法で、配列は構造の終わりの直後に続きます。その方法には独自の問題があるので、私が言及したことを忘れてください。