반응형
동적으로 확장되는 어레이
게임 내 엔티티의 「raw」리스트를 읽어내는 프로그램이 있어, 여러가지 처리를 위해서 엔티티의 인덱스 번호(int)를 가지는 어레이를 만들 생각입니다.이러한 인덱스를 유지하기 위해 메모리나 CPU를 너무 많이 사용하는 것은 피하고 싶습니다.
지금까지 사용한 빠르고 더러운 해결책은 메인 처리 기능(로컬 포커스)에서 최대 게임 엔티티의 크기를 가진 어레이를 선언하고 목록에 추가된 수를 추적하는 것입니다.모든 리스트가 3000대 이상의 어레이를 탑재하고 있기 때문에 만족할 수 없지만, 다양한 기능에 대해 6~7개의 리스트의 솔루션을 사용할 수 있기 때문에 낭비라고 생각합니다.
이를 실현하기 위한 C(C++ 또는 C#이 아닌) 고유의 솔루션은 발견되지 않았습니다.포인터는 사용할 수 있지만, 사용하는 것이 조금 두렵습니다(그 방법밖에 없는 경우).
어레이는 로컬 기능 범위에서 벗어나지 않습니다(기능에 전달된 후 폐기됩니다).
포인터가 유일한 해결책인 경우 누출을 방지하기 위해 포인터를 추적하려면 어떻게 해야 합니까?
포인터는 사용할 수 있지만 사용하는 것이 조금 두렵습니다.
동적 배열이 필요한 경우 포인터를 이스케이프할 수 없습니다.근데 왜 두려운 거야?그들은 물지 않을 것이다.C에는 내장 다이내믹 어레이가 없기 때문에 직접 작성하기만 하면 됩니다.C++ 에서는, 짜넣기 클래스를 사용할 수 있습니다.C# 및 기타 모든 고급 언어에는 동적 어레이를 관리하는 유사한 클래스도 있습니다.
독자적인 기입을 계획하고 있는 경우는, 우선, 대부분의 다이나믹 어레이 실장은, 디폴트 사이즈가 작은 어레이로부터 개시해, 새로운 요소를 추가할 때에 용량이 부족할 때마다, 어레이의 사이즈가 2배가 됩니다.아래 예에서 볼 수 있듯이, 전혀 어렵지 않습니다. (간단히 하기 위해 안전 점검을 생략했습니다.)
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;
}
사용법은 다음과 같습니다.
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);
하나의 간단한 해결책은 다음과 같습니다.POSIX 솔루션을 사용할 수 있는 경우, 이것은 매우 유용합니다.페이지 전체를 매핑하고 오버플로우를 방지하세요.realloc어쨌든 그런 값에는 실패할 것입니다.최신 OS는 사용할 때까지 모든 것을 커밋하지 않으며, 필요에 따라 파일을 잘라낼 수 있습니다.
'하다'라는도 있어요.realloc처음보다 더 무섭게 보이는 모든 것과 마찬가지로, 처음의 두려움을 극복하는 가장 좋은 방법은 미지의 불편함에 빠져드는 것이다!결국 우리가 가장 많이 배울 때죠.
아쉽게도 한계가 있습니다.예를 들어, 기능 사용법을 배우는 동안에는 교사 역할을 맡아서는 안 된다.는 자주 것 .realloc(즉, 현재 승인된 답변!) 다른 사람에게 오류 처리를 생략한 것처럼 위장하여 잘못 사용하는 방법을 알려줍니다. 단, 이는 언급이 필요한 일반적인 함정입니다.여기 올바른 사용법을 설명하는 답이 있습니다.오류 체크를 수행하기 위해 반환 값을 다른 변수에 저장하는 것이 답이라는 점에 유의하십시오.
함수를 호출할 때마다 그리고 배열을 사용할 때마다 포인터를 사용합니다.이러한 전환은 암묵적으로 일어나고 있습니다. 만약 더 무서운 것이 있다면, 가장 큰 문제를 일으키는 것은 종종 우리가 볼 수 없는 것이기 때문입니다.예를 들어 메모리 누수...
배열 연산자는 포인터 연산자입니다. array[x] 말은 지름길이에요.*(array + x)이는 다음과 같이 나눌 수 있습니다.* ★★★★★★★★★★★★★★★★★」(array + x)'아예'가, '아예: '아예'가,*는 더 것이라고 가정하면 될 수 있습니다.x0 , 즉,array[0] becomes가 되다*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;
가가제 the the the를 struct int_list **해 보이지 않을 수 두 인수에 해 보면, 이 있을 , 변경사항이 있을 수 있습니다.value에서)push_back금금거 기능 ?능? 능???이고, 할 수 .또한 이 인수에 대해 수정이 필요합니다.array여기뿐만 아니라 다른 기능에서도 전달될 수 있습니다.
array아무것도 가리키지 않고 시작합니다.빈 리스트입니다.초기화는 추가와 동일합니다.예를 들어 다음과 같습니다.
struct int_list *array = NULL;
if (!push_back(&array, 42)) {
// success!
}
추신. 다 쓰면 잊지 마세요!
제가 생각할 수 있는 몇 가지 방법이 있습니다.
- 수 있습니다.링크된 목록을 사용하여 동적으로 증가하는 어레이를 만들 수 있습니다. 은 할 수 이다.
array[100]1-99먼저. 그리고 여러분들도 사용하기에는 그다지 편리하지 않을 수도 있습니다. - 대규모 어레이모든 것을 수용할 수 있는 충분한 공간을 가진 어레이를 만드는 것만으로 충분
- 어레이 크기 조정 중.크기가 확인되면 어레이를 재생성하거나 여유 공간이 부족할 때마다 새 어레이를 만들고 모든 데이터를 새 어레이에 복사합니다.
- Linked List Array 조합.크기가 고정된 어레이를 사용하고 공간이 부족하면 새 어레이를 생성하여 해당 어레이에 링크합니다(어레이를 추적하고 구조체의 다음 어레이에 대한 링크를 유지하는 것이 좋습니다.
당신의 상황에서는 어떤 옵션이 최선이라고 말하기 어렵습니다.대규모 어레이를 작성하는 것은 물론 가장 쉬운 해결책 중 하나이며, 실제로 대규모 어레이가 아니면 큰 문제가 발생하지 않습니다.
Matteo Furlans 설계를 기반으로 한 그는 "대부분의 동적 어레이 구현은 기본 크기가 작은 어레이부터 시작하여 새로운 요소를 추가할 때 공간이 부족할 때마다 어레이의 크기가 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);
}
건설적인 비평이 이어지길 기대하세요...
당신이 말할 때
불확실한 수의 엔티티 인덱스 번호(int)를 가진 배열을 만드는
기본적으로는 메모리 전체 포인터가 아닌 어레이 전체 로컬 포인터를 사용한다는 것입니다.개념적으로 이미 포인터(즉, 배열 내의 요소를 참조하는 ID 번호)를 사용하고 있으므로 일반 포인터(즉, 가장 큰 배열의 요소를 참조하는 ID 번호: 전체 메모리)를 사용하는 것이 좋습니다.
개체는 리소스 ID 번호를 저장하는 대신 포인터를 저장하도록 할 수 있습니다.기본적으로는 동일하지만 "array + index"를 "pointinter"로 변환하지 않기 때문에 훨씬 효율적입니다.
포인터는 메모리 전체의 어레이 인덱스로 생각하면 무섭지 않습니다(실제입니다).
모든 유형의 무제한 항목 배열을 작성하려면:
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;
}
이 벡터/어레이는 모든 유형의 항목을 포함할 수 있으며 크기가 완전히 동적입니다.
요소를 삭제해야 할 경우 제외할 요소를 무시하고 배열 복사본을 만들 수 있습니다.
// 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(...)는 온도 벡터를 처리하기 위한 보조 방법입니다.
이 게시물은 순서가 잘못된 것 같습니다!이 글은 3개 게시물 중 1위입니다.미안하다.
Lie Ryan의 코드를 사용하려고 할 때 저장된 정보를 검색하는 데 문제가 있었습니다.벡터의 요소는 비트를 "치팅"하여 각 요소의 주소에 대한 포인터를 저장하고(물론 동적 배열 개념의 목적을 위반함) 검사하는 등 연속적으로 저장되지 않습니다.
약간의 손질을 통해:
ss_vector* vector; // pull this out to be a global vector
// Then add the following to attempt to recover stored values.
int return_id_value(int i,apple* aa) // given ptr to component,return data item
{ printf("showing apple[%i].id = %i and other_id=%i\n",i,aa->id,aa->other_id);
return(aa->id);
}
int Test(void) // Used to be "main" in the example
{ apple* aa[10]; // stored array element addresses
vector = ss_init_vector(sizeof(apple));
// inserting some items
for (int i = 0; i < 10; i++)
{ aa[i]=init_apple(i);
printf("apple id=%i and other_id=%i\n",aa[i]->id,aa[i]->other_id);
ss_vector_append(vector, aa[i]);
}
// report the number of components
printf("nmbr of components in vector = %i\n",(int)vector->size);
printf(".*.*array access.*.component[5] = %i\n",return_id_value(5,aa[5]));
printf("components of size %i\n",(int)sizeof(apple));
printf("\n....pointer initial access...component[0] = %i\n",return_id_value(0,(apple *)&vector[0]));
//.............etc..., followed by
for (int i = 0; i < 10; i++)
{ printf("apple[%i].id = %i at address %i, delta=%i\n",i, return_id_value(i,aa[i]) ,(int)aa[i],(int)(aa[i]-aa[i+1]));
}
// don't forget to free it
ss_vector_free(vector);
return 0;
}
주소를 알고 있으면 각 어레이 요소에 문제 없이 액세스할 수 있기 때문에 "다음" 요소를 추가하여 링크 목록으로 사용할 수 있습니다.하지만 더 나은 선택지는 분명히 있다.조언 부탁드립니다.
이 게시물은 순서가 잘못된 것 같습니다!3개의 게시물 중 3위입니다.미안하다.
저는 라이 라이언의 암호로 몇 가지 더 자유롭게 행동했습니다.링크된 목록은 검색 오버헤드로 인해 개별 요소에 액세스하는 데 시간이 많이 걸렸습니다. 즉, 올바른 요소를 찾을 때까지 목록을 따라 이동하는 것입니다.이 문제를 해결하려면 첨자 0을 포함하는 주소 벡터를 메모리 주소와 짝을 이룬 주소까지 유지해야 합니다.이것은, 주소 벡터가 동시에 할당되기 때문에, 메모리내에서 연속해 동작합니다.링크 리스트가 불필요해졌기 때문에, 관련 코드와 구조를 삭제했습니다.
이 접근방식은 일반 스태틱 어레이만큼 효율적이지는 않지만 적어도 적절한 아이템을 검색할 필요는 없습니다.이제 첨자를 사용하여 요소에 액세스할 수 있습니다.이를 활성화하기 위해 요소가 제거되고 "실제" 첨자가 포인터 벡터의 첨자에 반영되지 않는 경우를 처리하기 위해 코드를 추가해야 했습니다.이는 사용자에게 중요하거나 중요하지 않을 수 있습니다.저는 IS가 중요하기 때문에 구독자 번호 재지정도 옵션으로 했습니다.번호 변경을 사용하지 않을 경우 프로그램 흐름은 더미 "누락" 요소로 이동하며 오류 코드를 반환하고 사용자는 이를 무시하거나 필요에 따라 수행할 수 있습니다.
여기서부터 사용자에게 '요소' 부분을 필요에 맞게 코드화하여 올바르게 동작하도록 조언합니다.추가된 요소가 어레이일 경우 서브루틴을 신중하게 코드화하여 액세스합니다.스태틱 어레이에서는 필요 없었던 어레이 구조가 얼마나 추가되었는지 확인합니다.맛있게 드세요!
#include <glib.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
// Code from https://stackoverflow.com/questions/3536153/c-dynamically-growing-array
// For pointer-to-pointer info see:
// https://stackoverflow.com/questions/897366/how-do-pointer-to-pointers-work-in-c-and-when-might-you-use-them
typedef struct STRUCT_SS_VECTOR
{ size_t size; // # of vector elements
void** items; // makes up one vector element's component contents
int subscript; // this element's subscript nmbr, 0 thru whatever
// struct STRUCT_SS_VECTOR* this_element; // linked list via this ptr
// struct STRUCT_SS_VECTOR* next_element; // and next ptr
} ss_vector;
ss_vector* vector; // ptr to vector of components
ss_vector* missing_element(int subscript) // intercepts missing elements
{ printf("missing element at subscript %i\n",subscript);
return NULL;
}
typedef struct TRACKER_VECTOR
{ int subscript;
ss_vector* vector_ptr;
} tracker_vector; // up to 20 or so, max suggested
tracker_vector* tracker;
int max_tracker=0; // max allowable # of elements in "tracker_vector"
int tracker_count=0; // current # of elements in "tracker_vector"
int tracker_increment=5; // # of elements to add at each expansion
void bump_tracker_vector(int new_tracker_count)
{ //init or lengthen tracker vector
if(max_tracker==0) // not yet initialized
{ tracker=calloc(tracker_increment, sizeof(tracker_vector));
max_tracker=tracker_increment;
printf("initialized %i-element tracker vector of size %lu at %lu\n",max_tracker,sizeof(tracker_vector),(size_t)tracker);
tracker_count++;
return;
}
else if (max_tracker<=tracker_count) // append to existing tracker vector by writing a new one, copying old one
{ tracker_vector* temp_tracker=calloc(max_tracker+tracker_increment,sizeof(tracker_vector));
for(int i=0;(i<max_tracker);i++){ temp_tracker[i]=tracker[i];} // copy old tracker to new
max_tracker=max_tracker+tracker_increment;
free(tracker);
tracker=temp_tracker;
printf(" re-initialized %i-element tracker vector of size %lu at %lu\n",max_tracker,sizeof(tracker_vector),(size_t)tracker);
tracker_count++;
return;
} // else if
// fall through for most "bumps"
tracker_count++;
return;
} // bump_tracker_vector()
ss_vector* ss_init_vector(size_t item_size) // item_size is size of one array member
{ ss_vector* vector= malloc(sizeof(ss_vector));
vector->size = 0; // initialize count of vector component elements
vector->items = calloc(1, item_size); // allocate & zero out memory for one linked list element
vector->subscript=0;
bump_tracker_vector(0); // init/store the tracker vector
tracker[0].subscript=0;
tracker[0].vector_ptr=vector;
return vector; //->this_element;
} // ss_init_vector()
ss_vector* ss_vector_append( int i) // ptr to this element, element nmbr
{ ss_vector* local_vec_element=0;
local_vec_element= calloc(1,sizeof(ss_vector)); // memory for one component
local_vec_element->subscript=i; //vec_element->size;
local_vec_element->size=i; // increment # of vector components
bump_tracker_vector(i); // increment/store tracker vector
tracker[i].subscript=i;
tracker[i].vector_ptr=local_vec_element; //->this_element;
return local_vec_element;
} // ss_vector_append()
void bubble_sort(void)
{ // bubble sort
struct TRACKER_VECTOR local_tracker;
int i=0;
while(i<tracker_count-1)
{ if(tracker[i].subscript>tracker[i+1].subscript)
{ local_tracker.subscript=tracker[i].subscript; // swap tracker elements
local_tracker.vector_ptr=tracker[i].vector_ptr;
tracker[i].subscript=tracker[i+1].subscript;
tracker[i].vector_ptr=tracker[i+1].vector_ptr;
tracker[i+1].subscript=local_tracker.subscript;
tracker[i+1].vector_ptr=local_tracker.vector_ptr;
if(i>0) i--; // step back and go again
}
else
{ if(i<tracker_count-1) i++;
}
} // while()
} // void bubble_sort()
void move_toward_zero(int target_subscript) // toward zero
{ struct TRACKER_VECTOR local_tracker;
// Target to be moved must range from 1 to max_tracker
if((target_subscript<1)||(target_subscript>tracker_count)) return; // outside range
// swap target_subscript ptr and target_subscript-1 ptr
local_tracker.vector_ptr=tracker[target_subscript].vector_ptr;
tracker[target_subscript].vector_ptr=tracker[target_subscript-1].vector_ptr;
tracker[target_subscript-1].vector_ptr=local_tracker.vector_ptr;
}
void renumber_all_subscripts(gboolean arbitrary)
{ // assumes tracker_count has been fixed and tracker[tracker_count+1]has been zeroed out
if(arbitrary) // arbitrary renumber, ignoring "true" subscripts
{ for(int i=0;i<tracker_count;i++)
{ tracker[i].subscript=i;}
}
else // use "true" subscripts, holes and all
{ for(int i=0;i<tracker_count;i++)
{ if ((size_t)tracker[i].vector_ptr!=0) // renumbering "true" subscript tracker & vector_element
{ tracker[i].subscript=tracker[i].vector_ptr->subscript;}
else // renumbering "true" subscript tracker & NULL vector_element
{ tracker[i].subscript=-1;}
} // for()
bubble_sort();
} // if(arbitrary) ELSE
} // renumber_all_subscripts()
void collapse_tracker_higher_elements(int target_subscript)
{ // Fix tracker vector by collapsing higher subscripts toward 0.
// Assumes last tracker element entry is discarded.
int j;
for(j=target_subscript;(j<tracker_count-1);j++)
{ tracker[j].subscript=tracker[j+1].subscript;
tracker[j].vector_ptr=tracker[j+1].vector_ptr;
}
// Discard last tracker element and adjust count
tracker_count--;
tracker[tracker_count].subscript=0;
tracker[tracker_count].vector_ptr=(size_t)0;
} // void collapse_tracker_higher_elements()
void ss_vector_free_one_element(int target_subscript, gboolean Keep_subscripts)
{ // Free requested element contents.
// Adjust subscripts if desired; otherwise, mark NULL.
// ----special case: vector[0]
if(target_subscript==0) // knock out zeroth element no matter what
{ free(tracker[0].vector_ptr);}
// ----if not zeroth, start looking at other elements
else if(tracker_count<target_subscript-1)
{ printf("vector element not found\n");return;}
// Requested subscript okay. Freeit.
else
{ free(tracker[target_subscript].vector_ptr);} // free element ptr
// done with removal.
if(Keep_subscripts) // adjust subscripts if required.
{ tracker[target_subscript].vector_ptr=missing_element(target_subscript);} // point to "0" vector
else // NOT keeping subscripts intact, i.e. collapsing/renumbering all subscripts toward zero
{ collapse_tracker_higher_elements(target_subscript);
renumber_all_subscripts(TRUE); // gboolean arbitrary means as-is, FALSE means by "true" subscripts
} // if (target_subscript==0) else
// show the new list
// for(int i=0;i<tracker_count;i++){printf(" remaining element[%i] at %lu\n",tracker[i].subscript,(size_t)tracker[i].vector_ptr);}
} // void ss_vector_free_one_element()
void ss_vector_free_all_elements(void)
{ // Start at "tracker[0]". Walk the entire list, free each element's contents,
// then free that element, then move to the next one.
// Then free the "tracker" vector.
for(int i=tracker_count;i>=0;i--)
{ // Modify your code to free vector element "items" here
if(tracker[i].subscript>=0) free(tracker[i].vector_ptr);
}
free(tracker);
tracker_count=0;
} // void ss_vector_free_all_elements()
// defining some sort of struct, can be anything really
typedef struct APPLE_STRUCT
{ int id; // one of the data in the component
int other_id; // etc
struct APPLE_STRUCT* next_element;
} apple; // description of component
apple* init_apple(int id) // make a single component
{ apple* a; // ptr to component
a = malloc(sizeof(apple)); // memory for one component
a->id = id; // populate with data
a->other_id=id+10;
a->next_element=NULL;
// don't mess with aa->last_rec here
return a; // return pointer to component
}
int return_id_value(int i,apple* aa) // given ptr to component, return single data item
{ printf("was inserted as apple[%i].id = %i ",i,aa->id);
return(aa->id);
}
ss_vector* return_address_given_subscript(int i)
{ return tracker[i].vector_ptr;}
int Test(void) // was "main" in the example
{ int i;
ss_vector* local_vector;
local_vector=ss_init_vector(sizeof(apple)); // element "0"
for (i = 1; i < 10; i++) // inserting items "1" thru whatever
{local_vector=ss_vector_append(i);} // finished ss_vector_append()
// list all tracker vector entries
for(i=0;(i<tracker_count);i++) {printf("tracker element [%i] has address %lu\n",tracker[i].subscript, (size_t)tracker[i].vector_ptr);}
// ---test search function
printf("\n NEXT, test search for address given subscript\n");
local_vector=return_address_given_subscript(5);
printf("finished return_address_given_subscript(5) with vector at %lu\n",(size_t)local_vector);
local_vector=return_address_given_subscript(0);
printf("finished return_address_given_subscript(0) with vector at %lu\n",(size_t)local_vector);
local_vector=return_address_given_subscript(9);
printf("finished return_address_given_subscript(9) with vector at %lu\n",(size_t)local_vector);
// ---test single-element removal
printf("\nNEXT, test single element removal\n");
ss_vector_free_one_element(5,TRUE); // keep subscripts; install dummy error element
printf("finished ss_vector_free_one_element(5)\n");
ss_vector_free_one_element(3,FALSE);
printf("finished ss_vector_free_one_element(3)\n");
ss_vector_free_one_element(0,FALSE);
// ---test moving elements
printf("\n Test moving a few elements up\n");
move_toward_zero(5);
move_toward_zero(4);
move_toward_zero(3);
// show the new list
printf("New list:\n");
for(int i=0;i<tracker_count;i++){printf(" %i:element[%i] at %lu\n",i,tracker[i].subscript,(size_t)tracker[i].vector_ptr);}
// ---plant some bogus subscripts for the next subscript test
tracker[3].vector_ptr->subscript=7;
tracker[3].subscript=5;
tracker[7].vector_ptr->subscript=17;
tracker[3].subscript=55;
printf("\n RENUMBER to use \"actual\" subscripts\n");
renumber_all_subscripts(FALSE);
printf("Sorted list:\n");
for(int i=0;i<tracker_count;i++)
{ if ((size_t)tracker[i].vector_ptr!=0)
{ printf(" %i:element[%i] or [%i]at %lu\n",i,tracker[i].subscript,tracker[i].vector_ptr->subscript,(size_t)tracker[i].vector_ptr);
}
else
{ printf(" %i:element[%i] at 0\n",i,tracker[i].subscript);
}
}
printf("\nBubble sort to get TRUE order back\n");
bubble_sort();
printf("Sorted list:\n");
for(int i=0;i<tracker_count;i++)
{ if ((size_t)tracker[i].vector_ptr!=0)
{printf(" %i:element[%i] or [%i]at %lu\n",i,tracker[i].subscript,tracker[i].vector_ptr->subscript,(size_t)tracker[i].vector_ptr);}
else {printf(" %i:element[%i] at 0\n",i,tracker[i].subscript);}
}
// END TEST SECTION
// don't forget to free everything
ss_vector_free_all_elements();
return 0;
}
int main(int argc, char *argv[])
{ char cmd[5],main_buffer[50]; // Intentionally big for "other" I/O purposes
cmd[0]=32; // blank = ASCII 32
// while(cmd!="R"&&cmd!="W" &&cmd!="E" &&cmd!=" ")
while(cmd[0]!=82&&cmd[0]!=87&&cmd[0]!=69)//&&cmd[0]!=32)
{ memset(cmd, '\0', sizeof(cmd));
memset(main_buffer, '\0', sizeof(main_buffer));
// default back to the cmd loop
cmd[0]=32; // blank = ASCII 32
printf("REad, TEst, WRITe, EDIt, or EXIt? ");
fscanf(stdin, "%s", main_buffer);
strncpy(cmd,main_buffer,4);
for(int i=0;i<4;i++)cmd[i]=toupper(cmd[i]);
cmd[4]='\0';
printf("%s received\n ",cmd);
// process top level commands
if(cmd[0]==82) {printf("READ accepted\n");} //Read
else if(cmd[0]==87) {printf("WRITe accepted\n");} // Write
else if(cmd[0]==84)
{ printf("TESt accepted\n");// TESt
Test();
}
else if(cmd[0]==69) // "E"
{ if(cmd[1]==68) {printf("EDITing\n");} // eDit
else if(cmd[1]==88) {printf("EXITing\n");exit(0);} // eXit
else printf(" unknown E command %c%c\n",cmd[0],cmd[1]);
}
else printf(" unknown command\n");
cmd[0]=32; // blank = ASCII 32
} // while()
// default back to the cmd loop
} // main()
이 게시물의 순서가 잘못되었을 수 있습니다!이것은 3개의 게시물 중 2위입니다.미안하다.
저는 Lie Ryan의 코드로 "몇 가지 자유"를 취했고, 링크 리스트를 통해 그의 벡터의 개별 요소에 접근할 수 있도록 링크 리스트를 구현했습니다.이렇게 하면 접근이 가능하지만 검색 오버헤드로 인해 개별 요소에 액세스하는 데 시간이 많이 소요됩니다. 즉, 올바른 요소를 찾을 때까지 목록을 따라 내려가야 합니다.첨자 0을 포함한 주소 벡터를 메모리 주소와 짝을 이룬 주소까지 유지하면 이 문제를 해결할 수 있습니다.이 방법은 일반 어레이만큼 효율적이지는 않지만, 적어도 적절한 아이템을 검색하기 위해 "목록 보기"를 할 필요는 없습니다.
// Based on code from https://stackoverflow.com/questions/3536153/c-dynamically-growing-array
typedef struct STRUCT_SS_VECTOR
{ size_t size; // # of vector elements
void** items; // makes up one vector element's component contents
int subscript; // this element's subscript nmbr, 0 thru whatever
struct STRUCT_SS_VECTOR* this_element; // linked list via this ptr
struct STRUCT_SS_VECTOR* next_element; // and next ptr
} ss_vector;
ss_vector* vector; // ptr to vector of components
ss_vector* ss_init_vector(size_t item_size) // item_size is size of one array member
{ vector= malloc(sizeof(ss_vector));
vector->this_element = vector;
vector->size = 0; // initialize count of vector component elements
vector->items = calloc(1, item_size); // allocate & zero out memory for one linked list element
vector->subscript=0;
vector->next_element=NULL;
// If there's an array of element addresses/subscripts, install it now.
return vector->this_element;
}
ss_vector* ss_vector_append(ss_vector* vec_element, int i)
// ^--ptr to this element ^--element nmbr
{ ss_vector* local_vec_element=0;
// If there is already a next element, recurse to end-of-linked-list
if(vec_element->next_element!=(size_t)0)
{ local_vec_element= ss_vector_append(vec_element->next_element,i); // recurse to end of list
return local_vec_element;
}
// vec_element is NULL, so make a new element and add at end of list
local_vec_element= calloc(1,sizeof(ss_vector)); // memory for one component
local_vec_element->this_element=local_vec_element; // save the address
local_vec_element->next_element=0;
vec_element->next_element=local_vec_element->this_element;
local_vec_element->subscript=i; //vec_element->size;
local_vec_element->size=i; // increment # of vector components
// If there's an array of element addresses/subscripts, update it now.
return local_vec_element;
}
void ss_vector_free_one_element(int i,gboolean Update_subscripts)
{ // Walk the entire linked list to the specified element, patch up
// the element ptrs before/next, then free its contents, then free it.
// Walk the rest of the list, updating subscripts, if requested.
// If there's an array of element addresses/subscripts, shift it along the way.
ss_vector* vec_element;
struct STRUCT_SS_VECTOR* this_one;
struct STRUCT_SS_VECTOR* next_one;
vec_element=vector;
while((vec_element->this_element->subscript!=i)&&(vec_element->next_element!=(size_t) 0)) // skip
{ this_one=vec_element->this_element; // trailing ptr
next_one=vec_element->next_element; // will become current ptr
vec_element=next_one;
}
// now at either target element or end-of-list
if(vec_element->this_element->subscript!=i)
{ printf("vector element not found\n");return;}
// free this one
this_one->next_element=next_one->next_element;// previous element points to element after current one
printf("freeing element[%i] at %lu",next_one->subscript,(size_t)next_one);
printf(" between %lu and %lu\n",(size_t)this_one,(size_t)next_one->next_element);
vec_element=next_one->next_element;
free(next_one); // free the current element
// renumber if requested
if(Update_subscripts)
{ i=0;
vec_element=vector;
while(vec_element!=(size_t) 0)
{ vec_element->subscript=i;
i++;
vec_element=vec_element->next_element;
}
}
// If there's an array of element addresses/subscripts, update it now.
/* // Check: temporarily show the new list
vec_element=vector;
while(vec_element!=(size_t) 0)
{ printf(" remaining element[%i] at %lu\n",vec_element->subscript,(size_t)vec_element->this_element);
vec_element=vec_element->next_element;
} */
return;
} // void ss_vector_free_one_element()
void ss_vector_insert_one_element(ss_vector* vec_element,int place)
{ // Walk the entire linked list to specified element "place", patch up
// the element ptrs before/next, then calloc an element and store its contents at "place".
// Increment all the following subscripts.
// If there's an array of element addresses/subscripts, make a bigger one,
// copy the old one, then shift appropriate members.
// ***Not yet implemented***
} // void ss_vector_insert_one_element()
void ss_vector_free_all_elements(void)
{ // Start at "vector".Walk the entire linked list, free each element's contents,
// free that element, then move to the next one.
// If there's an array of element addresses/subscripts, free it.
ss_vector* vec_element;
struct STRUCT_SS_VECTOR* next_one;
vec_element=vector;
while(vec_element->next_element!=(size_t) 0)
{ next_one=vec_element->next_element;
// free(vec_element->items) // don't forget to free these
free(vec_element->this_element);
vec_element=next_one;
next_one=vec_element->this_element;
}
// get rid of the last one.
// free(vec_element->items)
free(vec_element);
vector=NULL;
// If there's an array of element addresses/subscripts, free it now.
printf("\nall vector elements & contents freed\n");
} // void ss_vector_free_all_elements()
// defining some sort of struct, can be anything really
typedef struct APPLE_STRUCT
{ int id; // one of the data in the component
int other_id; // etc
struct APPLE_STRUCT* next_element;
} apple; // description of component
apple* init_apple(int id) // make a single component
{ apple* a; // ptr to component
a = malloc(sizeof(apple)); // memory for one component
a->id = id; // populate with data
a->other_id=id+10;
a->next_element=NULL;
// don't mess with aa->last_rec here
return a; // return pointer to component
};
int return_id_value(int i,apple* aa) // given ptr to component, return single data item
{ printf("was inserted as apple[%i].id = %i ",i,aa->id);
return(aa->id);
}
ss_vector* return_address_given_subscript(ss_vector* vec_element,int i)
// always make the first call to this subroutine with global vbl "vector"
{ ss_vector* local_vec_element=0;
// If there is a next element, recurse toward end-of-linked-list
if(vec_element->next_element!=(size_t)0)
{ if((vec_element->this_element->subscript==i))
{ return vec_element->this_element;}
local_vec_element= return_address_given_subscript(vec_element->next_element,i); // recurse to end of list
return local_vec_element;
}
else
{ if((vec_element->this_element->subscript==i)) // last element
{ return vec_element->this_element;}
// otherwise, none match
printf("reached end of list without match\n");
return (size_t) 0;
}
} // return_address_given_subscript()
int Test(void) // was "main" in the original example
{ ss_vector* local_vector;
local_vector=ss_init_vector(sizeof(apple)); // element "0"
for (int i = 1; i < 10; i++) // inserting items "1" thru whatever
{ local_vector=ss_vector_append(vector,i);}
// test search function
printf("\n NEXT, test search for address given subscript\n");
local_vector=return_address_given_subscript(vector,5);
printf("finished return_address_given_subscript(5) with vector at %lu\n",(size_t)local_vector);
local_vector=return_address_given_subscript(vector,0);
printf("finished return_address_given_subscript(0) with vector at %lu\n",(size_t)local_vector);
local_vector=return_address_given_subscript(vector,9);
printf("finished return_address_given_subscript(9) with vector at %lu\n",(size_t)local_vector);
// test single-element removal
printf("\nNEXT, test single element removal\n");
ss_vector_free_one_element(5,FALSE); // without renumbering subscripts
ss_vector_free_one_element(3,TRUE);// WITH renumbering subscripts
// ---end of program---
// don't forget to free everything
ss_vector_free_all_elements();
return 0;
}
언급URL : https://stackoverflow.com/questions/3536153/c-dynamically-growing-array
반응형
'source' 카테고리의 다른 글
| MariaDB/MySQL에서 잠금 없이 삭제?(InnoDB) (0) | 2022.10.15 |
|---|---|
| String으로의 캐스팅과 String.valueOf의 차이 (0) | 2022.10.15 |
| 키가 mariadb로 너무 깁니다만, 같은 인코딩의 스크립트가 mysql로 동작합니다. (0) | 2022.10.15 |
| mysql 워크벤치 EER 열기 오류 (0) | 2022.10.15 |
| Larabel에서 이 작업을 수행하는 방법, 서브쿼리: (0) | 2022.10.15 |