ص صفيف تنمو ديناميكيا

Question

لديّ برنامج يقرأ قائمة "خام" من الكيانات داخل اللعبة ، وأعتزم جعل صفيف يحمل رقم فهرس (INT) لعدد غير محدد من الكيانات ، لمعالجة أشياء مختلفة. أود تجنب استخدام الكثير من الذاكرة أو وحدة المعالجة المركزية للحفاظ على هذه الفهارس ...

الحل السريع والقذر الذي أستخدمه حتى الآن هو الإعلان ، في وظيفة المعالجة الرئيسية (التركيز المحلي) الصفيف مع حجم كيانات اللعبة القصوى ، وآخر صحيح لتتبع عدد القائمة التي تمت إضافتها إلى القائمة. هذا ليس مرضيًا ، حيث أن كل قائمة تمتلك 3000+ صفيف ، وهي ليست كثيرًا ، ولكنها تبدو وكأنها مضيعة ، لأنني سأستخدم الحل ل 6-7 قوائم للوظائف المختلفة.

لم أجد أي حلول محددة C (وليس C ++ أو C#) لتحقيق ذلك. يمكنني استخدام المؤشرات ، لكنني خائف بعض الشيء من استخدامها (ما لم تكن الطريقة الوحيدة الممكنة).

لا تترك المصفوفات نطاق الوظيفة المحلية (يجب نقلها إلى وظيفة ، ثم يتم التخلص منها) ، في حالة تغيير الأشياء.

إذا كانت المؤشرات هي الحل الوحيد ، فكيف يمكنني تتبعها لتجنب التسريبات؟

Answer 1

يمكنني استخدام المؤشرات ، لكنني خائف بعض الشيء من استخدامها.

إذا كنت بحاجة إلى مجموعة ديناميكية ، فلن تتمكن من الهروب من المؤشرات. لماذا تخاف رغم ذلك؟ لن يعضوا (طالما كنت حذرا ، وهذا هو). لا يوجد صفيف ديناميكي مدمج في 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);

Answer 2

هناك بعض الخيارات التي يمكنني التفكير فيها.

1. قائمة مرتبطة. يمكنك استخدام قائمة مرتبطة لجعل مجموعة تنمو ديناميكيًا مثل الشيء. لكنك لن تكون قادرًا على القيام به array[100] دون الحاجة إلى المشي 1-99 أول. وقد لا يكون ذلك مفيدًا لك لاستخدامه أيضًا.
2. مجموعة كبيرة. ما عليك سوى إنشاء مجموعة بأكثر من مساحة كافية لكل شيء
3. صفيف تغيير حجم. أعد إنشاء الصفيف بمجرد معرفة حجم و/أو إنشاء صفيف جديد في كل مرة تنفد فيها من الفضاء مع بعض الهامش ونسخ جميع البيانات إلى الصفيف الجديد.
4. مجموعة صفيف قائمة مرتبطة. ما عليك سوى استخدام صفيف بحجم ثابت ، وبمجرد نفاد المساحة ، قم بإنشاء صفيف جديد وربط بذلك (سيكون من الحكمة تتبع الصفيف ورابط الصفيف التالي في البنية).

من الصعب تحديد الخيار الذي سيكون أفضل في وضعك. ببساطة إنشاء مجموعة كبيرة هو Of Courres أحد أسهل الحلول ولا ينبغي أن يعطيك الكثير من المشاكل ما لم تكن كبيرة حقًا.

Answer 3

كما هو الحال مع كل ما يبدو أكثر رعبا في البداية مما كان عليه لاحقًا ، فإن أفضل طريقة للتغلب على الخوف الأولي هي انغمس في إزعاج المجهول! في بعض الأحيان ، نتعلم أكثر ، بعد كل شيء.

لسوء الحظ ، هناك قيود. على الرغم من أنك لا تزال تتعلم استخدام وظيفة ، فلا ينبغي عليك تولي دور المعلم ، على سبيل المثال. كثيرا ما أقرأ إجابات من أولئك الذين لا يعرفون على ما يبدو كيفية استخدامه realloc (بمعنى آخر الجواب المقبول حاليا!) إخبار الآخرين بكيفية استخدامه بشكل غير صحيح ، وأحيانًا تحت ستارهم حذفت معالجة الأخطاء, ، على الرغم من أن هذا هو مأزق شائع يحتاج إلى ذكر. إليك إجابة تشرح كيفية استخدامها realloc بشكل صحيح. لاحظ أن الإجابة تقوم بتخزين قيمة الإرجاع في مختلف متغير من أجل إجراء فحص الخطأ.

في كل مرة تتصل فيها بوظيفة ، وفي كل مرة تستخدم فيها صفيفًا ، فأنت تستخدم مؤشرًا. تحدث التحويلات ضمنياً ، والتي إذا كان أي شيء يجب أن يكون أكثر رعبا ، لأن الأشياء التي لا نرى والتي غالباً ما تسبب معظم المشكلات. على سبيل المثال ، تسرب الذاكرة ...

مشغلي الصفيف هم مشغلي المؤشرات. array[x] هو حقا اختصار ل *(array + x), ، والتي يمكن تقسيمها إلى: * و (array + x). من المرجح أن * هو ما يربكك. يمكننا مزيد من القضاء على الإضافة من المشكلة بافتراض x أن تكون 0, ، هكذا، array[0] يصبح *array لأن إضافة 0 لن يغير القيمة ...

... وبالتالي يمكننا أن نرى ذلك *array يعادل array[0]. يمكنك استخدام واحدة حيث تريد استخدام الآخر ، والعكس صحيح. مشغلي الصفيف هم مشغلي المؤشرات.

malloc, realloc والأصدقاء لا اختراع مفهوم المؤشر الذي كنت تستخدمه طوال الوقت ؛ هم فقط استعمال هذا لتنفيذ بعض الميزات الأخرى ، وهو شكل مختلف من مدة التخزين ، الأكثر ملاءمة عندما ترغب تغييرات حادة وديناميكية في الحجم.

إنه لأمر مخز أن الإجابة المقبولة حاليًا ايضا يتعارض مع حبة بعض النصائح الأخرى التي تم تأسيسها بشكل جيد على Stackoverflow, ، وفي الوقت نفسه ، يفوت فرصة لتقديم ميزة غير معروفة تضيء لهذا الاستخدام بالضبط: أعضاء مجموعة مرنة! هذا في الواقع مكسورة جدا إجابه... :(

عندما تحدد الخاص بك struct, ، أعلن صفيفك .في نهايةالمطاف من الهيكل ، دون أي حدود علوية. فمثلا:

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

سيتيح لك هذا توحيد صفيفك من int في نفس التخصيص مثل count, ، وجعلهم ملزمين مثل هذا يمكن أن يكون مفيد جدا!

sizeof (struct int_list) سوف يتصرف كما لو value بحجم 0 ، لذلك سوف يخبرك بحجم الهيكل مع قائمة فارغة. لا تزال بحاجة إلى إضافة إلى الحجم المنقولة realloc لتحديد حجم قائمتك.

نصيحة أخرى مفيدة هي أن تتذكر ذلك 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 ** نظرًا لأن الحجة الأولى قد لا تبدو واضحة على الفور ، ولكن إذا فكرت في الوسيطة الثانية ، فإن أي تغييرات تم إجراؤها على value من داخل push_back لن تكون مرئية للوظيفة التي ندعو منها ، أليس كذلك؟ الشيء نفسه ينطبق على الوسيطة الأولى ، ونحن بحاجة إلى أن نكون قادرين على تعديلنا array, ، ليس مجرد هنا لكن ربما أيضًا في أي وظيفة أخرى/نقوم بتمريرها إليها...

array يبدأ في الإشارة إلى لا شيء ؛ إنها قائمة فارغة. التهيئة هو نفسه إضافته. فمثلا:

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

ملاحظة تذكر أن free(array); عندما تنتهي من ذلك!

Answer 4

عندما تقول

اصنع صفيفًا يحمل رقم فهرس (INT) لعدد غير محدد من الكيانات

أنت تقول بشكل أساسي أنك تستخدم "مؤشرات" ، ولكنها مؤشر محلي على مستوى الصفيف بدلاً من مؤشر على مستوى الذاكرة. نظرًا لأنك تستخدم بالفعل "مؤشرات" (أي أرقام المعرفات التي تشير إلى عنصر في صفيف) ، فلماذا لا تستخدم مؤشرات منتظمة فقط (أي أرقام معرفات تشير إلى عنصر في أكبر صفيف: الذاكرة بأكملها ).

بدلاً من كائناتك تخزين أرقام معرف الموارد ، يمكنك جعلها تخزن مؤشرًا بدلاً من ذلك. في الأساس نفس الشيء ، ولكن أكثر كفاءة لأننا نتجنب تحويل "Array + Index" إلى "مؤشر".

المؤشرات ليست مخيفة إذا كنت تعتقد أنها فهرس صفيف للذاكرة بأكملها (وهو ما هم عليه بالفعل)

Answer 5

بناء على ماتيو فورلان التصميم عندما قال "تعمل معظم تطبيقات الصفيف الديناميكية من خلال البدء بمجموعة من الحجم الافتراضي (الصغير) ، ثم كلما نفدت من الفضاء عند إضافة عنصر جديد ، ضعف حجم الصفيف". الفرق في"أعمال جارية"فيما يلي أنه لا يتضاعف في الحجم ، فهو يهدف إلى استخدام ما هو مطلوب فقط. لقد حذفت أيضًا فحص السلامة للبساطة ... أيضًا بناء على بريمبريوم فكرة ، لقد حاولت إضافة وظيفة حذف إلى الرمز ...

ملف 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);
}

نتطلع إلى النقد البناء للمتابعة...

Answer 6

لإنشاء مجموعة من العناصر غير المحدودة من أي نوع من النوع:

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

يمكن لهذا المتجه/الصفيف أن يحتفظ بأي نوع من العناصر وهو ديناميكي تمامًا في الحجم.

Answer 7

حسنًا ، أعتقد أنه إذا كنت بحاجة إلى إزالة عنصر ، فسوف تقوم بتقديم نسخة من الصفيف الذي يحتقر العنصر المراد استبعاده.

// 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(...) هي طرق مساعدة للتعامل مع ناقل درجة الحرارة.