C 동적으로 성장하는 배열

C 동적으로 성장하는 배열

---

게임 내 엔터티의 "원시"목록을 읽는 프로그램이 있으며 다양한 것을 처리하기 위해 알 수없는 엔터티의 인덱스 번호 (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);

---

내가 생각할 수있는 몇 가지 옵션이 있습니다.

1. 연결된 목록. 연결된 목록을 사용하여 동적으로 성장하는 배열을 만들 수 있습니다. 그러나 먼저 array[100]걸을 필요 없이는 할 수 없습니다 1-99. 그리고 당신이 사용하는 것이 그렇게 편리하지 않을 수도 있습니다.
2. 큰 배열. 모든 것을위한 충분한 공간을 가진 어레이를 생성하기 만하면됩니다
3. 배열 크기 조정 크기를 알고 나면 배열을 다시 만들고 여유 공간이 부족할 때마다 새 배열을 만들고 모든 데이터를 새 배열에 복사하십시오.
4. 연결된 목록 배열 조합. 고정 크기의 배열을 사용하기 만하면 공간이 부족 해지면 새 배열을 생성하고 그 배열에 연결합니다 (구조에서 배열과 다음 배열에 대한 링크를 추적하는 것이 좋습니다).

상황에 가장 적합한 옵션을 말하기는 어렵습니다. 단순히 큰 배열을 만드는 것은 물론 가장 쉬운 솔루션 중 하나이며 실제로 크지 않으면 큰 문제를 일으키지 않아야합니다.

---

처음보다 더 무서워 보이는 모든 것과 마찬가지로, 초기 두려움을 극복하는 가장 좋은 방법은 자신을 미지의 불쾌에 빠뜨리는 것입니다 ! 결국 우리가 가장 많이 배우는 것과 같은 시간입니다.

불행히도 한계가 있습니다. 여전히 기능 사용을 배우는 동안 예를 들어 교사의 역할을 맡아서는 안됩니다. 나는 종종 사용법을 모르는 사람들 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뿐만 아니라, 여기에 있지만 다른 기능도 가능하게 / 우리는 그것을 통과 s의 ...

array아무것도 가리 키지 않고 시작합니다. 빈 목록입니다. 초기화 하는 것은 추가하는 것과 같습니다. 예를 들면 다음과 같습니다.

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

추신 당신이 그것으로 끝났을 때를 기억하십시오free(array); !

---

당신이 말할 때

불확실한 수의 엔티티의 색인 번호 (int)를 보유하는 배열을 만듭니다.

기본적으로 "포인터"를 사용하고 있지만 메모리 전체 포인터 대신 배열 전체 로컬 포인터입니다. 개념적으로 이미 "포인터"(예 : 배열의 요소를 나타내는 id 번호)를 사용하고 있기 때문에 정규 포인터 (즉, 가장 큰 배열의 요소를 나타내는 id 번호 : 전체 메모리) 만 사용하지 않는 이유는 무엇입니까? ).

자원 ID 번호를 저장하는 객체 대신 포인터를 저장하도록 만들 수 있습니다. 기본적으로는 똑같지 만 "배열 + 색인"을 "포인터"로 바꾸지 않기 때문에 훨씬 효율적입니다.

포인터를 전체 메모리의 배열 인덱스로 생각하면 무서운 것은 아닙니다 (실제로있는 것입니다)

---

Matteo Furlans 디자인을 바탕으로 그는 " 대부분의 작은 기본 크기의 배열로 시작하여 대부분의 동적 배열 구현이 작동하며, 새로운 요소를 추가 할 때 공간이 부족할 때마다 배열의 크기를 두 배로 늘 립니다"라고 말했습니다. 아래 " 진행중인 작업 "의 차이점은 크기가 두 배가 아니라 필요한 것만 사용한다는 것입니다. 나는 또한 단순성에 대한 안전 점검을 생략했습니다 ... 또한 brimboriums 아이디어를 기반으로 코드에 삭제 기능을 추가하려고 시도했습니다 ...

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

건설적인 비판 을 기대하고 ...

---

To create an array of unlimited items of any sort of type:

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

and how to use it:

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

This vector/array can hold any type of item and it is completely dynamic in size.

---

Well, I guess if you need to remove an element you will make a copy of the array despising the element to be excluded.

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

Assume that getElement2BRemove(), copy2TempVector( void* ...) and fillFromTempVector(...) are auxiliary methods to handle the temp vector.

참고URL : https://stackoverflow.com/questions/3536153/c-dynamically-growing-array