c動的に成長する配列

https://stackoverflow.com/questions/3536153

30-09-2019
|

質問

ゲーム内のエンティティの「生」リストを読み取るプログラムがあり、さまざまなものを処理するために、不確定なエンティティのインデックス番号（INT）を保持する配列を作成するつもりです。そのようなインデックスを維持するために、メモリやCPUをあまりにも多く使用しないでください...

私がこれまでに使用している迅速で汚いソリューションは、メイン処理機能（ローカルフォーカス）で、最大ゲームエンティティのサイズのアレイと、リストに追加された数を追跡する別の整数を宣言することです。すべてのリストには3000以上のアレイが保持されているため、これは満足のいくものではありませんが、それほど多くはありませんが、さまざまな機能に6〜7のリストにソリューションを使用できるため、無駄のように感じます。

これを達成するためのC（C ++またはC＃ではない）特定のソリューションは見つかりませんでした。ポインターを使用できますが、使用することを少し恐れています（それが唯一の可能性のある方法でない限り）。

アレイは、物事を変える場合に備えて、ローカル関数スコープ（関数に渡され、破棄される）を残しません。

ポインターが唯一のソリューションである場合、漏れを避けるためにそれらを追跡するにはどうすればよいですか？

解決

ポインターを使用することはできますが、それらを使用することを少し恐れています。

動的配列が必要な場合は、ポインターを逃れることはできません。なぜあなたは恐れているのですか？彼らは噛みません（あなたが注意する限り、つまり）。 Cには組み込みの動的配列はありません。自分で書くだけです。 C ++では、内蔵を使用できます std::vector クラス。 C＃および他のすべての高レベルの言語には、動的配列を管理する同様のクラスもあります。

独自に書く予定がある場合は、ここにあなたが始めるための何かがあります：ほとんどのダイナミックアレイの実装は、いくつかの（小さな）デフォルトサイズの配列から始めることで動作します。配列のサイズ。以下の例でわかるように、それはまったく難しくありません：（私は簡潔にするために安全チェックを省略しました）

typedef struct {
  int *array;
  size_t used;
  size_t size;
} Array;

void initArray(Array *a, size_t initialSize) {
  a->array = (int *)malloc(initialSize * sizeof(int));
  a->used = 0;
  a->size = initialSize;
}

void insertArray(Array *a, int element) {
  // a->used is the number of used entries, because a->array[a->used++] updates a->used only *after* the array has been accessed.
  // Therefore a->used can go up to a->size 
  if (a->used == a->size) {
    a->size *= 2;
    a->array = (int *)realloc(a->array, a->size * sizeof(int));
  }
  a->array[a->used++] = element;
}

void freeArray(Array *a) {
  free(a->array);
  a->array = NULL;
  a->used = a->size = 0;
}

それを使用することも同じくらい簡単です：

Array a;
int i;

initArray(&a, 5);  // initially 5 elements
for (i = 0; i < 100; i++)
  insertArray(&a, i);  // automatically resizes as necessary
printf("%d\n", a.array[9]);  // print 10th element
printf("%d\n", a.used);  // print number of elements
freeArray(&a);

他のヒント

私が考えることができるいくつかのオプションがあります。

リンクリスト。リンクされたリストを使用して、動的に成長しているアレイのようなものを作成できます。しかし、あなたはできることはありません array[100] 通り抜ける必要なく 1-99 最初。そして、どちらも使用するのに便利ではないかもしれません。
大きな配列。すべてのために十分なスペースを持つ配列を作成するだけです
アレイのサイズ変更。サイズがわかったら、アレイを再作成したり、マージンでスペースを使い果たすたびに新しい配列を作成し、すべてのデータを新しい配列にコピーします。
リンクリストアレイの組み合わせ。固定サイズのアレイを使用して、スペースを使い果たしたら、新しい配列とそれへのリンクを作成します（アレイと構造体の次の配列へのリンクを追跡するのが賢明です）。

あなたの状況でどのオプションが最適かを言うのは難しいです。単に大きな配列を作成することは、もちろん最も簡単なソリューションの1つであり、本当に大きくない限り多くの問題を与えるべきではありません。

最初は怖いと思われるすべてのものと同様に、最初の恐怖を乗り越えるための最良の方法は 未知のものの不快感に没頭してください！結局のところ、それは私たちが最も学んだもののようなものです。

残念ながら、制限があります。まだ機能を使用することを学んでいますが、たとえば教師の役割を想定してはなりません。私はよく使用する方法を知らないように見える人からの答えをよく読みます realloc （すなわち 現在受け入れられている答え！）他の人にそれを誤って使用する方法を伝える、時には彼らが持っていると装って 省略エラー処理, 、これは言及する必要がある一般的な落とし穴ですが。使用方法を説明する回答を次に示します realloc 正しく. 答えは返品値をに保存していることに注意してください違うエラーチェックを実行するための変数。

関数を呼び出すたびに、そして配列を使用するたびにポインターを使用しています。コンバージョンは暗黙的に発生しています。これは、ほとんどの問題を引き起こすことが多いことがわからないことです。たとえば、メモリリーク...

配列演算子はポインター演算子です。 array[x] 本当に近道です *(array + x), 、それを分けることができます： * と (array + x). 。それはおそらくそうです * あなたを混乱させるものです。想定することにより、問題からの追加をさらに排除できます x することが 0, 、したがって、 array[0] なります *array 追加するからです 0 価値は変えません...

...そして、私たちはそれを見ることができます *array に相当します array[0]. 。もう一方を使用する場所で使用できます。その逆も同様です。配列演算子はポインター演算子です。

malloc, realloc そして、友達はしません発明あなたがずっと使ってきたポインターの概念。彼らは単に 使用する これは、ストレージ期間の異なる形式である他の機能を実装するために、あなたが望むときに最も適しています サイズの劇的で動的な変化.

現在受け入れられている答えが残念ですまたの穀物に反します Stackoverflowに関する他の非常によく根拠のあるアドバイス, 、同時に、まさにこのUSECASE：Flexible Arrayメンバーのために輝くあまり知られていない機能を導入する機会を逃します！それは実際にです かなり壊れています 答え... ：（

あなたがあなたを定義するとき struct, 、配列を宣言します 最後に 上限なしの構造の。例えば：

struct int_list {
    size_t size;
    int value[];
};

これにより、配列を統合できます int あなたと同じ割り当てに count, 、そして、彼らをこのように縛ることができます とても便利な!

sizeof (struct int_list) あたかも動作します value サイズは0なので、構造のサイズがわかります 空のリスト付き. 。渡されたサイズに追加する必要があります realloc リストのサイズを指定します。

もう1つの便利なヒントは、それを覚えておくことです realloc(NULL, x) に相当します malloc(x), 、そしてこれを使用してコードを簡素化できます。例えば：

int push_back(struct int_list **fubar, int value) {
    size_t x = *fubar ? fubar[0]->size : 0
         , y = x + 1;

    if ((x & y) == 0) {
        void *temp = realloc(*fubar, sizeof **fubar
                                   + (x + y) * sizeof fubar[0]->value[0]);
        if (!temp) { return 1; }
        *fubar = temp; // or, if you like, `fubar[0] = temp;`
    }

    fubar[0]->value[x] = value;
    fubar[0]->size = y;
    return 0;
}

struct int_list *array = NULL;

私が使用することを選んだ理由 struct int_list ** 最初の議論はすぐには明白ではないように見えるかもしれませんが、2番目の議論について考えると、 value 内部から push_back 私たちが呼んでいる機能には見えませんか？同じことが最初の議論にも当てはまり、私たちは私たちを変更できる必要があります array, 、だけでなくここしかし おそらく他の関数でも私たちはそれを渡します...

array 何も指さないように始めます。空のリストです。 初期化 それはそれに追加するのと同じです。例えば：

struct int_list *array = NULL;
if (!push_back(&array, 42)) {
    // success!
}

詩 覚えておいてください free(array); あなたがそれで終わったら！

あなたが言っているとき

不確定なエンティティのインデックス番号（int）を保持している配列を作成します

基本的には、「ポインター」を使用していると言っていますが、メモリ全体のポインターの代わりにアレイ全体のローカルポインターです。概念的には既に「ポインター」（つまり、配列内の要素を指すID番号）を使用しているため、通常のポインター（つまり、メモリ全体の要素を指すIE ID番号：）。

オブジェクトがリソースID番号を保存する代わりに、代わりにポインターを保存することができます。基本的に同じことですが、「配列 +インデックス」を「ポインター」に変えることを避けるため、はるかに効率的です。

ポインターは、メモリ全体の配列インデックスと考えると、怖くありません（実際にはそうです）

建物 マッテオファラン 彼が言ったとき、デザイン」ほとんどの動的な配列の実装は、いくつかの（小）デフォルトサイズの配列から始めることで機能します。新しい要素を追加するときにスペースを使い果たすたびに、配列のサイズを2倍にします「。の違い」進行中の作業「以下は、サイズが2倍にならないということです。必要なもののみを使用することを目指しています。また、シンプルさのために安全チェックも省略しました... ブリムボリウム アイデア、私はコードに削除関数を追加しようとしました...

Storage.hファイルは次のようになります...

#ifndef STORAGE_H
#define STORAGE_H

#ifdef __cplusplus
extern "C" {
#endif

    typedef struct 
    {
        int *array;
        size_t size;
    } Array;

    void Array_Init(Array *array);
    void Array_Add(Array *array, int item);
    void Array_Delete(Array *array, int index);
    void Array_Free(Array *array);

#ifdef __cplusplus
}
#endif

#endif /* STORAGE_H */

Storage.cファイルは次のようになります...

#include <stdio.h>
#include <stdlib.h>
#include "storage.h"

/* Initialise an empty array */
void Array_Init(Array *array) 
{
    int *int_pointer;

    int_pointer = (int *)malloc(sizeof(int));

    if (int_pointer == NULL)
    {       
        printf("Unable to allocate memory, exiting.\n");
        free(int_pointer);
        exit(0);
    }
    else
    {
        array->array = int_pointer; 
        array->size = 0;
    }
}

/* Dynamically add to end of an array */
void Array_Add(Array *array, int item) 
{
    int *int_pointer;

    array->size += 1;

    int_pointer = (int *)realloc(array->array, array->size * sizeof(int));

    if (int_pointer == NULL)
    {       
        printf("Unable to reallocate memory, exiting.\n");
        free(int_pointer);
        exit(0);
    }
    else
    {
        array->array = int_pointer;
        array->array[array->size-1] = item;
    }
}

/* Delete from a dynamic array */
void Array_Delete(Array *array, int index) 
{
    int i;
    Array temp;
    int *int_pointer;

    Array_Init(&temp);

    for(i=index; i<array->size; i++)
    {
        array->array[i] = array->array[i + 1];
    }

    array->size -= 1;

    for (i = 0; i < array->size; i++)
    {
        Array_Add(&temp, array->array[i]);
    }

    int_pointer = (int *)realloc(temp.array, temp.size * sizeof(int));

    if (int_pointer == NULL)
    {       
        printf("Unable to reallocate memory, exiting.\n");
        free(int_pointer);
        exit(0);
    }
    else
    {
        array->array = int_pointer; 
    } 
}

/* Free an array */
void Array_Free(Array *array) 
{
  free(array->array);
  array->array = NULL;
  array->size = 0;  
}

main.cはこのように見えます...

#include <stdio.h>
#include <stdlib.h>
#include "storage.h"

int main(int argc, char** argv) 
{
    Array pointers;
    int i;

    Array_Init(&pointers);

    for (i = 0; i < 60; i++)
    {
        Array_Add(&pointers, i);        
    }

    Array_Delete(&pointers, 3);

    Array_Delete(&pointers, 6);

    Array_Delete(&pointers, 30);

    for (i = 0; i < pointers.size; i++)
    {        
        printf("Value: %d Size:%d \n", pointers.array[i], pointers.size);
    }

    Array_Free(&pointers);

    return (EXIT_SUCCESS);
}

楽しみにしています 建設的な批判 従うために...

あらゆるタイプの無制限のアイテムの配列を作成するには：

typedef struct STRUCT_SS_VECTOR {
    size_t size;
    void** items;
} ss_vector;


ss_vector* ss_init_vector(size_t item_size) {
    ss_vector* vector;
    vector = malloc(sizeof(ss_vector));
    vector->size = 0;
    vector->items = calloc(0, item_size);

    return vector;
}

void ss_vector_append(ss_vector* vec, void* item) {
    vec->size++;
    vec->items = realloc(vec->items, vec->size * sizeof(item));
    vec->items[vec->size - 1] = item;
};

void ss_vector_free(ss_vector* vec) {
    for (int i = 0; i < vec->size; i++)
        free(vec->items[i]);

    free(vec->items);
    free(vec);
}

そしてそれを使用する方法：

// defining some sort of struct, can be anything really
typedef struct APPLE_STRUCT {
    int id;
} apple;

apple* init_apple(int id) {
    apple* a;
    a = malloc(sizeof(apple));
    a-> id = id;
    return a;
};


int main(int argc, char* argv[]) {
    ss_vector* vector = ss_init_vector(sizeof(apple));

    // inserting some items
    for (int i = 0; i < 10; i++)
        ss_vector_append(vector, init_apple(i));


    // dont forget to free it
    ss_vector_free(vector);

    return 0;
}

このベクトル/配列は、あらゆるタイプのアイテムを保持でき、サイズが完全に動的です。

まあ、要素を削除する必要がある場合は、除外される要素を軽spする配列のコピーを作成するでしょう。

// inserting some items
void* element_2_remove = getElement2BRemove();

for (int i = 0; i < vector->size; i++){
       if(vector[i]!=element_2_remove) copy2TempVector(vector[i]);
       }

free(vector->items);
free(vector);
fillFromTempVector(vector);
//

と仮定する getElement2BRemove(), copy2TempVector( void* ...) と fillFromTempVector(...) 温度ベクトルを処理する補助方法です。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow