C array yang tumbuh secara dinamis

Saya memiliki program yang membaca daftar "mentah" entitas dalam game, dan saya bermaksud membuat array yang menyimpan nomor indeks (int) dari jumlah entitas yang tidak ditentukan, untuk memproses berbagai hal. Saya ingin menghindari penggunaan terlalu banyak memori atau CPU untuk menjaga indeks seperti itu ...

Solusi cepat dan kotor yang saya gunakan sejauh ini adalah mendeklarasikan, dalam fungsi pemrosesan utama (fokus lokal) array dengan ukuran entitas game maksimum, dan integer lain untuk melacak berapa banyak yang telah ditambahkan ke daftar. Ini tidak memuaskan, karena setiap daftar memiliki 3000+ array, yang tidak terlalu banyak, tetapi terasa seperti sia-sia, karena saya mungkin akan menggunakan solusi untuk 6-7 daftar untuk berbagai fungsi.

Saya belum menemukan solusi spesifik C (bukan C ++ atau C #) untuk mencapai hal ini. Saya dapat menggunakan pointer, tetapi saya agak takut menggunakannya (kecuali hanya itu cara yang mungkin).

Array tidak meninggalkan ruang lingkup fungsi lokal (mereka akan diteruskan ke fungsi, kemudian dibuang), jika hal-hal berubah.

Jika pointer adalah satu-satunya solusi, bagaimana saya bisa melacak mereka untuk menghindari kebocoran?

Saya bisa menggunakan pointer, tetapi saya agak takut menggunakannya.

Jika Anda membutuhkan array dinamis, Anda tidak bisa lepas dari pointer. Mengapa kamu takut? Mereka tidak akan menggigit (asalkan Anda berhati-hati, itu). Tidak ada larik dinamis bawaan di C, Anda hanya perlu menulis sendiri. Di C ++, Anda bisa menggunakan std::vectorkelas bawaan. C # dan hampir semua bahasa tingkat tinggi lainnya juga memiliki beberapa kelas serupa yang mengelola array dinamis untuk Anda.

Jika Anda berencana untuk menulis sendiri, berikut ini adalah sesuatu untuk Anda mulai: sebagian besar implementasi array dinamis bekerja dengan memulai dengan array beberapa ukuran standar (kecil), lalu setiap kali Anda kehabisan ruang saat menambahkan elemen baru, gandakan ukuran array. Seperti yang Anda lihat pada contoh di bawah ini, sama sekali tidak sulit: (Saya telah menghilangkan pemeriksaan keamanan untuk singkatnya)

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

void initArray(Array *a, size_t initialSize) {
  a->array = 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 = 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;
}

Menggunakannya sama mudahnya:

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);

Ada beberapa opsi yang bisa saya pikirkan.

1. Daftar Tertaut. Anda dapat menggunakan daftar yang ditautkan untuk membuat array yang tumbuh secara dinamis. Tetapi Anda tidak akan bisa melakukannya array[100]tanpa harus berjalan 1-99terlebih dahulu. Dan mungkin tidak berguna bagi Anda untuk menggunakannya.
2. Array besar. Cukup buat sebuah array dengan lebih dari cukup ruang untuk semuanya
3. Mengubah ukuran array. Buat kembali array begitu Anda tahu ukuran dan / atau buat array baru setiap kali Anda kehabisan ruang dengan margin dan salin semua data ke array baru.
4. Kombinasi Array Daftar Tertaut. Cukup gunakan larik dengan ukuran tetap dan setelah Anda kehabisan ruang, buat larik baru dan tautkan ke sana (alangkah baiknya untuk melacak larik dan taut ke larik berikutnya di dalam sebuah struct).

Sulit mengatakan opsi apa yang terbaik untuk situasi Anda. Cukup membuat array besar tentu saja salah satu solusi termudah dan seharusnya tidak memberi Anda banyak masalah kecuali itu benar-benar besar.

Seperti segala sesuatu yang tampak lebih menakutkan pada awalnya daripada kemudian, cara terbaik untuk mengatasi rasa takut awal adalah dengan membenamkan diri Anda ke dalam ketidaknyamanan yang tidak diketahui ! Pada saat-saat seperti itulah yang paling banyak kita pelajari.

Sayangnya, ada batasannya. Saat Anda masih belajar untuk menggunakan suatu fungsi, Anda tidak seharusnya mengambil peran sebagai guru, misalnya. Saya sering membaca jawaban dari mereka yang tampaknya tidak tahu cara menggunakan realloc(yaitu jawaban yang saat ini diterima! ) Memberi tahu orang lain bagaimana menggunakannya secara salah, kadang-kadang dengan kedok bahwa mereka telah menghilangkan penanganan kesalahan , meskipun ini adalah perangkap umum yang perlu disebutkan. Inilah jawaban yang menjelaskan cara menggunakan reallocdengan benar . Perhatikan bahwa jawabannya menyimpan nilai balik ke variabel yang berbeda untuk melakukan pengecekan kesalahan.

Setiap kali Anda memanggil fungsi, dan setiap kali Anda menggunakan array, Anda menggunakan pointer. Konversi ini terjadi secara implisit, yang jika sesuatu harus lebih menakutkan, karena hal-hal yang tidak kita lihat yang paling sering menyebabkan masalah. Misalnya, kebocoran memori ...

Operator array adalah operator pointer. array[x]benar-benar jalan pintas untuk *(array + x), yang dapat dipecah menjadi: *dan (array + x). Kemungkinan besar itulah *yang membingungkan Anda. Kami lebih lanjut dapat menghilangkan penambahan dari masalah dengan mengasumsikan xmenjadi 0, dengan demikian, array[0]menjadi *arraykarena menambahkan 0tidak akan mengubah nilai ...

... dan dengan demikian kita dapat melihat bahwa *arrayitu setara dengan array[0]. Anda dapat menggunakan satu di mana Anda ingin menggunakan yang lain, dan sebaliknya. Operator array adalah operator pointer.

malloc, reallocdan teman tidak menemukan konsep pointer yang telah Anda gunakan selama ini; mereka hanya menggunakan ini untuk mengimplementasikan beberapa fitur lain, yang merupakan bentuk berbeda dari durasi penyimpanan, paling cocok ketika Anda menginginkan perubahan ukuran yang drastis dan dinamis .

Sangat memalukan bahwa jawaban yang saat ini diterima juga bertentangan dengan saran-saran lain yang sangat beralasan tentang StackOverflow , dan pada saat yang sama, kehilangan kesempatan untuk memperkenalkan fitur yang tidak banyak diketahui yang menyinari dengan tepat usecase ini: array fleksibel anggota! Itu sebenarnya jawaban yang cukup rusak ... :(

Ketika Anda mendefinisikan Anda struct, mendeklarasikan array Anda di akhir struktur, tanpa batas atas. Sebagai contoh:

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

Ini akan memungkinkan Anda untuk menyatukan array Anda intke dalam alokasi yang sama dengan Anda count, dan mengikat mereka seperti ini bisa sangat berguna !

sizeof (struct int_list)akan bertindak seolah-olah valuememiliki ukuran 0, jadi itu akan memberi tahu Anda ukuran struktur dengan daftar kosong . Anda masih perlu menambahkan ukuran yang diteruskan ke reallocuntuk menentukan ukuran daftar Anda.

Tip berguna lainnya adalah untuk mengingat yang realloc(NULL, x)setara dengan malloc(x), dan kita dapat menggunakan ini untuk menyederhanakan kode kita. Sebagai contoh:

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;

Alasan saya memilih untuk menggunakan struct int_list **sebagai argumen pertama mungkin tidak langsung tampak jelas, tetapi jika Anda berpikir tentang argumen kedua, setiap perubahan yang dibuat valuedari dalam push_backtidak akan terlihat oleh fungsi yang kami panggil, kan? Hal yang sama berlaku untuk argumen pertama, dan kita harus dapat memodifikasi kita array, tidak hanya di sini tetapi mungkin juga dalam fungsi lain / s kita berikan kepada ...

arraymulai menunjuk apa-apa; ini adalah daftar kosong. Menginisialisasi itu sama dengan menambahkannya. Sebagai contoh:

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

PS Ingatfree(array); ketika Anda selesai dengan itu!

Membangun desain Matteo Furlans , ketika ia mengatakan " implementasi array paling dinamis bekerja dengan memulai dengan array beberapa ukuran standar (kecil), lalu setiap kali Anda kehabisan ruang saat menambahkan elemen baru, gandakan ukuran array ". Perbedaan dalam " pekerjaan dalam proses " di bawah ini adalah bahwa ia tidak berlipat ganda dalam ukuran, itu bertujuan hanya menggunakan apa yang diperlukan. Saya juga menghilangkan pemeriksaan keamanan untuk kesederhanaan ... Juga membangun ide brimboriums , saya telah mencoba menambahkan fungsi hapus ke kode ...

File storage.h terlihat seperti ini ...

#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 */

File storage.c terlihat seperti ini ...

#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 terlihat seperti ini ...

#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);
}

Nantikan kritik konstruktif untuk diikuti ...

Ketika Anda mengatakannya

membuat array yang memegang nomor indeks (int) dari jumlah entitas yang tidak ditentukan

Anda pada dasarnya mengatakan Anda menggunakan "pointer", tetapi yang merupakan pointer lokal array-lebar, bukan pointer memory-wide. Karena Anda secara konseptual sudah menggunakan "pointer" (yaitu nomor id yang merujuk ke elemen dalam array), mengapa Anda tidak menggunakan pointer biasa (mis. Angka id yang merujuk ke elemen dalam array terbesar: seluruh memori ).

Alih-alih objek Anda menyimpan nomor id sumber daya, Anda dapat membuatnya menyimpan pointer. Pada dasarnya hal yang sama, tetapi jauh lebih efisien karena kita menghindari mengubah "array + index" menjadi "pointer".

Pointer tidak menakutkan jika Anda menganggapnya sebagai indeks array untuk seluruh memori (yang sebenarnya)

Untuk membuat berbagai item tanpa batas dari jenis apa pun:

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);
}

dan cara menggunakannya:

// 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;
}

Vektor / array ini dapat menampung semua jenis barang dan ukurannya benar-benar dinamis.

Yah, saya kira jika Anda perlu menghapus elemen, Anda akan membuat salinan array yang membenci elemen yang akan dikecualikan.

// 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);
//

Asumsikan itu getElement2BRemove(), copy2TempVector( void* ...)dan fillFromTempVector(...)merupakan metode bantu untuk menangani vektor temp.