ArrayList 구현

먼저 이름 지정에 대한 단어 :

선택한 이름 유형, _arraylist는 라이브러리 인터페이스 유형의 잘못된 이름입니다. _로 시작하는 이름은 사용자 코드에서 사용하기가 좋지 않습니다. 라이브러리 내부에서 일반적으로 사용됩니다. 더 나은 이름은 ArrayList 또는 array_list입니다.

사실 사용 예에서 ArrayList. 이것은 여기에 포함되지 않은 헤더에 다음과 같은 내용이 있다는 것을 의미합니까?

typedef _arraylist ArrayList; 

헤더에 불투명 한 유형을 정의했다면, 위와 같이 좋은 습관이 될 것입니다. 그러나 코드에서 _arraylist에 대한 참조를 사용해서는 안됩니다. 혼동을 피하기 위해 항상 typedef “d 이름을 사용하세요.

함수 이름 접두사는 유형의 이름을 정확히 따라야하므로 ArrayList의 경우 모든 함수는 ArrayList_ 접두사가 붙었습니다. 예 :

ArrayList * ArrayList_create(); 

또한 이름 (예 : arraylist_getsize()). 단어를 구분하기 위해 밑줄을 추가하면 훨씬 더 읽기 쉬워집니다. 예 : ArrayList_get_size() .

메모리 문제 :

arraylist_create() :

struct _arraylist *arraylist_create() { struct _arraylist *list = malloc(sizeof(struct _arraylist)); assert(list != NULL); list->size = 0; list->data = calloc(2, sizeof(void *)); assert(list->data != NULL); list->data[0] = NULL; return list; } 

여기서 특이한 첫 번째 것은 어설 션입니다. 어설 션은 메모리 할당 실패를 처리하는 적절한 방법이 아닙니다. 또한 , 그들은 일반적으로 릴리스 빌드에서 비활성화되므로 릴리스에서 메모리가 부족하면 프로그램이 조용히 충돌합니다. 이 경우 NULL를 반환하고 (stderr에도 기록 할 수 있음) 호출자가 확인한대로이 오류를 처리하도록해야합니다. 적합합니다.

두 번째 문제는 calloc()입니다. 2 개의 void 포인터를 할당하고 있지만 size는 0으로 설정됩니다. 나는 이것의 요점을 정말로 이해하지 못한다. 당신의 구조는 배열의 배열과 목록이 더 비슷하기 때문에, 당신이해야 할 일은 포인터 배열을 미리 정의 된 기본 크기로 할당 한 다음 필요에 따라 개별 배열을 할당하는 것입니다. 요청시 포인터 배열입니다. arraylist_create()는 어떻게 생겼는지 :

ArrayList * ArrayList_create() { ArrayList *list = malloc(sizeof *list); if (list == NULL) { return NULL; } list->size = 0; list->data = calloc(INITIAL_BASE_ARRAY_SIZE, sizeof(void *)); if (list->data == NULL) { free(list); // Don"t leek memory here! return NULL; } return list; } 

또 다른 큰 메모리 문제는 상수입니다. arraylist_add() 및 arraylist_remove()에 의해 재 할당됩니다.

제거는 시퀀스를 축소하지 않아야합니다. 어레이는 나중에 다시 증가합니다. 필요한 경우 사용자가 스토리지를 축소 할 수있는 명시적인 방법을 추가 할 수 있습니다 (a la std::vector::shrink_to_fit()).

요청 된 것보다 더 큰 크기로 스토리지를 미리 할당하면 어레이가 상각 된 고정 시간에 실행되도록 만들 수 있습니다 (STL vector에서 다시 영감을 얻음).

sizeof 실수 :

예상 한 결과를 반환하지 않습니다.

size_t arraylist_getsizeof(struct _arraylist *list) { /* Returns the size of the internal array in memory */ return sizeof(*list->data); } 

sizeof 연산자는 항상 적용되는 유형의 크기를 반환합니다. 포인터가 가리키는 배열의 크기는 컴파일 타임 작업이기 때문에 유추 할 수 없습니다. arraylist_getsizeof()는 항상 동일한 값, 즉 void 포인터 크기를 반환하며 아키텍처에 따라 4 또는 8이됩니다.

어설 션을 사용하여 불변성을 확인합니다. :

assert 모든 함수의 div id = “1979ffde07”>

성능에 대해 이야기하기

목록을 매우 자주 사용해야하는 경우 어떻게해야합니까?

arraylist_add 함수를 자세히 살펴 보겠습니다. 백만 바이트 (1MB)의 목록이 필요한 경우 data struct member 100 만 번.

목록에서 가장 낮은 부분입니다!

제안

청크로 메모리 할당 , 예를 들어 C ++ std::vector는 std::vector의 현재 크기에 따라 추가 된 청크의 증가하는 크기를 사용합니다.

이것은 증가 할 것입니다. 새로운 요소를 추가 할 목적으로 몇 번 실행하십시오.

코드에 대해있는 그대로

아름답지만 간단한 프로그램 흐름을 구현해보세요.

값 유형 (int) ArrayList를 생성하여 대신 덩어리로 메모리를 할당합니다. 전체 배열을 재 할당하고 후드 아래에 목록 동작을 추가하십시오. 청크 목록을 의미합니다. 여전히 관리해야합니다.

다음은 재 할당하는 대신 각 노드에 대량의 데이터를 사용하는 예제가있는 솔루션입니다. 노드. 목적 중 하나에 다른 덩어리 크기가 가장 적합 할 수 있습니다. 쓰기, 긴 배열 읽기; r \ w 짧은 배열; 요소 제거; 등

#include <stdio.h> #include <stdlib.h> typedef struct ArrayList ArrayList; typedef ArrayList* ArrayListPtr; struct ArrayList { size_t capacity; size_t size; int *data; ArrayListPtr parent; ArrayListPtr child; }; const size_t ARRAY_LIST_CHUNCK_SIZE = 64; ArrayListPtr array_list_create_with_parent_and_chunck_size(ArrayListPtr parent, size_t chunck_size) { ArrayListPtr result = (ArrayListPtr)calloc(sizeof(ArrayList), 1); result->parent = parent; result->capacity = chunck_size; result->data = (int*)malloc(sizeof(int) * chunck_size); return result; } ArrayListPtr array_list_create_with_parent(ArrayListPtr parent) { return array_list_create_with_parent_and_chunck_size( parent, ARRAY_LIST_CHUNCK_SIZE ); } ArrayListPtr array_list_create() { return array_list_create_with_parent_and_chunck_size( NULL, ARRAY_LIST_CHUNCK_SIZE ); } void array_list_push_back(ArrayListPtr list, int value) { if (list->size >= list->capacity) { if (!list->child) { list->child = array_list_create_with_parent(list); } array_list_push_back(list->child, value); } else { list->data[list->size++] = value; } } int* array_list_get_value_by_index(ArrayListPtr list, size_t index) { if (index >= list->capacity || index >= list->size) { if (list->child) { return array_list_get_value_by_index(list->child, index - list->size); } else { return NULL; } } return list->data + index; } int main(int argc, char *argv[]) { ArrayListPtr list = array_list_create(); for (int i = 0; i < 100*1000; ++i) { array_list_push_back(list, i); } size_t test[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,31,32,33,63,64,65,999,1000}; for (int i = 0; i < sizeof(test) / sizeof(size_t); ++i) { int* result = array_list_get_value_by_index(list, test[i]); if (result) { printf("list[%ld] = %d\n", test[i], *result); } else { printf("Can"t get value by index %ld\n", test[i]); } } } 

댓글

• 귀하의 관심을 존중합니다. 그러나 이것은 C ++가 아니라 C입니다. C ++라면 그냥 벡터를 사용해서 ..
• @AmrAyman, 확인해보세요
• ‘ 인상적입니다! 하지만 연결된 목록이 아닌 arraylist를 갖고 싶습니다. 여기에 연결된 목록 구현이 일반 구조체 구현보다 더 발전했지만 glampert가 문제를 해결했습니다.
• 성능 향상에 대해. ‘별로 없습니다. 제 구현은 일반적으로 배열에 의존하기 때문에 힙에 의존합니다. 사용자는 재귀에 엄청나게 의존하며 ‘ 노드에 의존하기 때문에 ‘ 자연 스럽습니다. 또한 목록을 해제하는 것은 상대적으로 많이 느립니다. ‘ 재귀 (성능이 매우 낮음)를 사용하거나 상당히 복잡하기 때문입니다. while loop ..

다른 사람이 언급하지 않은 문제는 테스트가 작동하지 않는다는 것입니다. 작동하는 것처럼 보이지만 실제로는 작동하지 않습니다. 목록에 값을 추가 할 때 변수 i :

arraylist_add(list, &i); 

그리고 arraylist_add는 전달 된 값을 저장합니다 (해야하는대로).

void arraylist_add(struct arraylist *list, void *elem) { .... new_data[list->size] = elem; 

그러면 i = 0을 반복하면됩니다. .99 목록에있는 모든 것은 i의 주소입니다. 데이터를 다시 읽을 때 루프 변수 i를 다시 사용하고 값을 0..99에서 수정하면 인쇄 된 값이 올바르게 표시됩니다. 그러나 실제로 루프에 의해 수정되는 루프 변수의 값을보고 있습니다.

저를 믿지 않는다면 고정 된 배열 항목 (예 : 50)을 인쇄하십시오.

printf("i: %d\n", *(int *)arraylist_get(list, 50)); 

인쇄됩니다 100 (또는 현재 i의 값).

대신 실제 값을 저장해야합니다.

arraylist_add(list, (void*) i); 

값을 입력했을 때의 유형으로 캐스트해야합니다.

printf("i: %d\n", (int)arraylist_get(list, t)); 

다른 사람들이 언급했듯이 코드에는 다른 많은 문제가 있습니다. . 모든 수정을 수행하기 위해 arraylist_setdata를 사용하는 기본 설계는 잘못되었습니다. 변경 될 때마다 재 할당하는 것은 좋지 않습니다. realloc는 비용이 많이 듭니다. void* 인 척하여 물건을 저장하는 목록의 기본 아이디어는 나에게 혼란스럽고 나쁜 아이디어처럼 보입니다.

댓글

• 글쎄요, 눈치 채지 못할 수도 있지만 ‘ 제가 테스트하고 싶은 것은 정확히 입니다. 그 포인터는 저장되고 검색됩니다. 함수 래퍼를 통해 올바르게 ..
• void *로 저장하는 것은 ‘보기만큼 나쁘지 않습니다.생각해보세요. void *는 단순히 메모리 주소를 저장합니다.이 주소는 저장된 값의 유형에 신경 쓰지 않습니다. ‘ 간단히 말해서, 배열은 메모리 주소 만 저장해야하며, ‘는 C가 단일 배열에서 다양한 유형을 처리하는 유일한 방법입니다 ..
• realloc에 대해 동의하지만 ‘ 동적