sourcecode

다차원 어레이의 올바른 할당

copyscript 2022. 8. 17. 23:53
반응형

다차원 어레이의 올바른 할당

이 질문의 목적은 C에서 다차원 어레이를 동적으로 할당하는 방법에 대한 참조를 제공하는 것입니다.이것은 일부 C 프로그래밍 서적에서조차 종종 오해되고 제대로 설명되지 않는 주제이다.그래서 숙련된 C 프로그래머들도 그것을 제대로 하기 위해 고군분투한다.

프로그래밍 선생님/책/튜토리얼로부터 다차원 배열을 동적으로 할당하는 올바른 방법은 포인터 투 포인터를 사용하는 것이라고 배웠습니다.

그러나 현재 SO의 몇몇 높은 평가 사용자는 이것이 잘못된 잘못된 관행이라고 말합니다.포인터 투 포인터는 어레이가 아니며 실제로 어레이를 할당하지 않으며 코드가 불필요하게 느리다고 합니다.

다차원 어레이를 할당하는 방법을 배웠습니다.

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

int** arr_alloc (size_t x, size_t y)
{
  int** pp = malloc(sizeof(*pp) * x);
  assert(pp != NULL);
  for(size_t i=0; i<x; i++)
  {
    pp[i] = malloc(sizeof(**pp) * y);
    assert(pp[i] != NULL);
  }

  return pp;
}

int** arr_fill (int** pp, size_t x, size_t y)
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      pp[i][j] = (int)j + 1;
    }
  }

  return pp;
}

void arr_print (int** pp, size_t x, size_t y)
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      printf("%d ", pp[i][j]);
    }
    printf("\n");
  }
}

void arr_free (int** pp, size_t x, size_t y)
{
  (void) y;

  for(size_t i=0; i<x; i++)
  {
    free(pp[i]);
    pp[i] = NULL;
  }
  free(pp);
  pp = NULL;
}


int main (void)
{
  size_t x = 2;
  size_t y = 3;
  int** pp;

  pp = arr_alloc(x, y);
  pp = arr_fill(pp, x, y);
  arr_print(pp, x, y);
  arr_free(pp, x, y);

  return 0;
}

산출량

1 2 3
1 2 3

이 코드는 잘 작동합니다!어떻게 틀릴 수 있죠?

질문에 답하기 위해서는 먼저 몇 가지 개념을 명확히 해야 합니다.어레이란 무엇이며 어떻게 사용하는가?질문의 코드는 무엇입니까(어레이가 아닌 경우)?

배열이란?

어레이의 정식 정의는 C 표준 ISO 9899:2011 6.2.5/20 타입에 기재되어 있습니다.

배열 유형은 요소 유형이라고 하는 특정 멤버 개체 유형을 사용하여 비어 있지 않은 연속적으로 할당된 개체 집합을 나타냅니다.

쉬운 영어로 배열은 인접한 메모리 셀에 연속적으로 할당된 동일한 유형의 항목의 집합입니다.

, 의 정수로 이 있습니다.int arr[3] = {1,2,3};하다

+-------+-------+-------+
|       |       |       |
|   1   |   2   |   3   |
|       |       |       |
+-------+-------+-------+

그럼 다차원 배열의 정식 정의는 어떨까요?사실, 이것은 위에서 언급한 것과 같은 정의입니다.재귀적으로 적용됩니다.

어레이를 2D 어레이를 할당합니다.int arr[2][3] = { {1,2,3}, {1,2,3} };하다

+-------+-------+-------+-------+-------+-------+
|       |       |       |       |       |       |
|   1   |   2   |   3   |   1   |   2   |   3   |
|       |       |       |       |       |       |
+-------+-------+-------+-------+-------+-------+

이 예에서는 어레이 어레이를 사용하고 있습니다.각각 3개의 정수로 이루어진 두 개의 항목이 있는 배열입니다.

어레이는 다른 어레이와 같은 유형입니다.

C의 배열은 보통 변수와 동일한 유형의 시스템을 따릅니다.위와 같이 어레이는 다른 유형의 어레이와 마찬가지로 사용할 수 있습니다.

n차원 배열에도 일반 1차원 배열과 동일한 종류의 포인터 산술을 적용할 수 있습니다.일반 1차원 배열의 경우 포인터 산술 적용은 간단해야 합니다.

int arr[3] = {1,2,3};
int* ptr = arr; // integer pointer to the first element.

for(size_t i=0; i<3; i++)
{
  printf("%d ", *ptr); // print contents.
  ptr++; // set pointer to point at the next element.
}

이것은 "배열 붕괴"를 통해 가능해졌다.arr표현식 내에서 사용되며 첫 번째 요소에 대한 포인터로 "전환"됩니다.

마찬가지로 어레이 포인터를 사용하여 어레이 배열을 반복할 수 있습니다.

int arr[2][3] = { {1,2,3}, {1,2,3} };
int (*ptr)[3] = arr; // int array pointer to the first element, which is an int[3] array.

for(size_t i=0; i<2; i++)
{
  printf("%d %d %d\n", (*ptr)[0], (*ptr)[1], (*ptr)[2]); // print contents
  ptr++; // set pointer to point at the next element
}

하다 ''arr그것은 종류였다.int [2][3]첫 번째 원소에 대한 포인터로 분해됩니다. 번째 는 첫 the the the the 。int [3]는 러한요음음음음음음음음음음음음음음음음 as as as as라고 됩니다.int(*)[3] 포인터 어레이 포인터

다차원 어레이를 사용하기 위해서는 어레이 포인터와 어레이 붕괴를 이해해야 합니다.

배열이 일반 변수와 동일하게 작동하는 경우가 더 많습니다.sizeof연산자는 일반 변수와 마찬가지로 (비 VLA) 어레이에서도 작동합니다.예: 32비트시스템

int x; printf("%zu", sizeof(x));4.
int arr[3] = {1,2,3}; printf("%zu", sizeof(arr));123*4=12)
int arr[2][3] = { {1,2,3}, {1,2,3} }; printf("%zu", sizeof(arr));242*3*4=24)

다른 유형과 마찬가지로 어레이는 라이브러리 함수 및 범용 API와 함께 사용할 수 있습니다.을 충족하기 에 예를 어레이를 할 수 .memcpy:

int arr_a[3] = {1,2,3};
int arr_b[3];
memcpy(arr_b, arr_a, sizeof(arr_a));

은 또한 다른 .memset,strcpy,bsearch ★★★★★★★★★★★★★★★★★」qsort연속적으로 할당된 어레이에서 작동하도록 설계되어 있습니다.배열이 할 수 다차원 배열로 할 수 .bsearch ★★★★★★★★★★★★★★★★★」qsort바이너리 검색의 실장이나 퀵 소트등의 번거로움이 없어져, 프로젝트 마다 바퀴를 다시 돌릴 필요가 없어집니다.

어레이와 다른 유형 간의 위의 모든 일관성은 특히 범용 프로그래밍을 수행할 때 활용할 수 있는 매우 좋은 기능입니다.

포인터 투 포인터라고 하는 것은, 어레이가 아닌 경우는 어떤 것입니까.

이제 질문의 코드로 돌아가겠습니다.이 질문에서는 포인터로 다른 구문을 사용했습니다.그것은 전혀 불가사의한 것이 아니다.이것은 타이핑 포인터이며, 그 이상도 이하도 아닙니다.배열이 아닙니다.2D 어레이가 아닙니다.엄밀히 말하면 어레이를 가리킬 때 사용할 수 없으며 2D 어레이를 가리킬 때도 사용할 수 없습니다.

그러나 포인터 투 포인터는 어레이 전체를 가리키는 것이 아니라 포인터 배열의 첫 번째 요소를 가리키는 데 사용할 수 있습니다.이것이 질문에서 어레이 포인터를 에뮬레이트하는 방법으로서 사용되는 방법입니다.질문에서는 두 포인터의 배열을 가리킬 때 사용됩니다.그리고 두 포인터 각각은 3개의 정수로 이루어진 배열을 가리킬 때 사용됩니다.

이것은 룩업 테이블이라고 불리며 ADT(Abstract Data Type)의 일종으로 플레인 어레이의 하위 수준 개념과는 다릅니다.주요 차이점은 룩업테이블의 할당 방법입니다.

+------------+
|            |
| 0x12340000 |
|            |
+------------+
      |
      |
      v
+------------+     +-------+-------+-------+
|            |     |       |       |       |
| 0x22223333 |---->|   1   |   2   |   3   |
|            |     |       |       |       |
+------------+     +-------+-------+-------+
|            | 
| 0xAAAABBBB |--+
|            |  | 
+------------+  |  
                |
                |  +-------+-------+-------+
                |  |       |       |       |
                +->|   1   |   2   |   3   |
                   |       |       |       |
                   +-------+-------+-------+

이 예에서는 32비트주소가 구성되어 있습니다.0x12340000박스에는 주소가 포함되어 .0x12340000포인터 배열의 첫 번째 항목으로 이동합니다.이 배열의 각 포인터는 차례로 정수 배열의 첫 번째 항목을 가리키는 주소를 포함합니다.

여기서부터 문제가 시작됩니다.

룩업 테이블 버전 문제

룩업 테이블이 히프 메모리 전체에 흩어져 있습니다.셀에는 되어 있지 .는 각 이 에의 콜이기 입니다.각 콜은 에 접속되어 있기 때문입니다.malloc()는 다른 메모리 영역과 인접할 필요는 없는 새로운 메모리 영역을 제공합니다.: 그그,,, 문: this this this this this this this this this this this this this this this this this this this this this?

  • 예상대로 포인터 산수를 사용할 수 없습니다.포인터 연산 형식을 사용하여 룩업 테이블의 항목을 인덱싱하고 액세스할 수 있지만 배열 포인터를 사용하여 인덱싱할 수는 없습니다.

  • 연산자 사이즈는 사용할 수 없습니다.포인터에 사용하면 포인터 크기를 알 수 있습니다.처음 가리키는 항목에 익숙해지면 포인터의 크기를 알 수 있습니다.둘 다 어레이의 크기가 아닙니다.

  • 유형열 종류)을한 표준 수 .memcpy,memset,strcpy,bsearch,qsort) 으로 할당하여 를 입력으로합니다.이러한 모든 함수는 데이터가 연속적으로 할당되어 있는 어레이를 입력으로 얻는 것으로 가정합니다.룩업 테이블을 파라미터로 호출하면 프로그램 크래시와 같은 정의되지 않은 동작 버그가 발생합니다.

  • 「 」의 콜malloc여러 세그먼트를 할당하면 힙 플래그멘테이션이 발생하고 결과적으로 RAM 메모리 사용률이 저하됩니다.

  • 메모리가 분산되어 있기 때문에 CPU는 룩업테이블을 반복할 때 캐시 메모리를 사용할 수 없습니다.데이터 캐시를 효율적으로 사용하려면 위에서 아래로 반복되는 연속된 메모리 청크가 필요합니다.즉, 룩업테이블은 설계상 실제 다차원 배열보다 액세스 시간이 상당히 느립니다.

  • 의 각 malloc()힙을 관리하는 라이브러리 코드는 사용 가능한 공간이 있는 위치를 계산해야 합니다.의 각 free()실행해야 하는 오버헤드코드가 있습니다.따라서, 이러한 기능에 대한 호출은 가능한 한 적게 하는 것이, 퍼포먼스를 위해서 바람직할 때가 많습니다.

룩업 테이블이 다 나쁜가요?

보시다시피 포인터 기반 룩업 테이블에는 많은 문제가 있습니다.하지만 모두 나쁜 것은 아니고 다른 도구와 같은 도구입니다.올바른 목적을 위해 사용되어야만 합니다.배열로 사용해야 하는 다차원 배열을 찾는 경우 룩업 테이블은 잘못된 도구임이 분명합니다.하지만 그것들은 다른 용도로 사용될 수 있다.

룩업 테이블은 모든 치수가 개별적으로 완전히 다른 크기를 가져야 할 때 적합합니다.이러한 컨테이너는 예를 들어 C 문자열 목록을 작성할 때 유용합니다.따라서 메모리를 절약하기 위해 상기의 실행 속도 성능 저하를 감수하는 것이 정당화될 수 있습니다.

또한 룩업 테이블은 전체 다차원 배열을 재할당하지 않고도 런타임에 테이블의 일부를 재할당할 수 있다는 장점이 있습니다.이 작업을 자주 수행해야 하는 경우에는 룩업 테이블이 실행 속도 면에서 다차원 어레이를 능가할 수도 있습니다.예를 들어 체인 해시 테이블을 구현할 때 유사한 룩업테이블을 사용할 수 있습니다.

그렇다면 다차원 어레이를 동적으로 할당하려면 어떻게 해야 할까요?

현대 C에서 가장 쉬운 형태는 가변장 어레이(VLA)를 사용하는 것입니다. int array[x][y];서 ''는x ★★★★★★★★★★★★★★★★★」y는 실행 시 이전 배열 선언에서 지정된 값입니다.되지 않습니다.즉, 자동 기간이 .저장기간은 자동으로 설정됩니다.따라서 VLA는 임시 어레이에서 편리하고 빠르게 사용할 수 있지만 질문의 룩업 테이블을 대체하지는 않습니다.

실제로 다차원 어레이를 동적으로 할당하고 스토리지 기간을 할당하려면malloc()/calloc()/realloc()아래에 예를 하나 들어보겠습니다.

현대 C에서는 VLA에 대한 어레이 포인터를 사용합니다.프로그램에 실제 VLA가 없는 경우에도 이러한 포인터를 사용할 수 있습니다.을 보통보다 type* ★★★void*이치노VLA에 대한 포인터를 사용하는 것 또한 당신은 기능은 배열을 사용하여 변수는 배열 차원을 전파하는 것과 형식 안전 한번에 변수를 만들고 허용한다.VLA포인터를 사용하면 어레이를 사용하는 함수에 어레이 치수를 파라미터로 전달할 수 있기 때문에 변수와 타입을 동시에 사용할 수 있습니다.

유감스럽게도 VLA에 대한 포인터가 있는 이점을 활용하기 위해 해당 포인터를 함수 결과로 반환할 수 없습니다.따라서 어레이에 대한 포인터를 호출자에게 반환해야 할 경우 포인터를 파라미터로 전달해야 합니다(Dynamic memory access는 내부 기능만 합니다).이것은 C에서의 훌륭한 프랙티스이지만, 코드를 읽기가 조금 어렵습니다.다음과 같이 됩니다.

void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
  *aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
  assert(*aptr != NULL);
}

어레이 포인터에 대한 포인터가 있는 이 구문은 다소 이상하고 위협적으로 보일 수 있지만, 차원을 추가해도 이보다 복잡하지는 않습니다.

void arr_alloc (size_t x, size_t y, size_t z, int(**aptr)[x][y][z])
{
  *aptr = malloc( sizeof(int[x][y][z]) ); // allocate a true 3D array
  assert(*aptr != NULL);
}

이제 이 코드를 룩업 테이블 버전에 하나 더 추가하기 위한 코드와 비교합니다.

/* Bad. Don't write code like this! */
int*** arr_alloc (size_t x, size_t y, size_t z)
{
  int*** ppp = malloc(sizeof(*ppp) * x);
  assert(ppp != NULL);
  for(size_t i=0; i<x; i++)
  {
    ppp[i] = malloc(sizeof(**ppp) * y);
    assert(ppp[i] != NULL);
    for(size_t j=0; j<y; j++)
    {
      ppp[i][j] = malloc(sizeof(***ppp) * z);
      assert(ppp[i][j] != NULL);
    }
  }

  return ppp;
}

이제 그것은 "3성 프로그램"의 읽기 힘든 엉망진창이다.그리고 4차원은 고려하지 말자...

실제 2D 어레이를 사용하는 버전의 전체 코드

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
  *aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
  assert(*aptr != NULL);
}

void arr_fill (size_t x, size_t y, int array[x][y])
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      array[i][j] = (int)j + 1;
    }
  }
}

void arr_print (size_t x, size_t y, int array[x][y])
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      printf("%d ", array[i][j]);
    }
    printf("\n");
  }
}

int main (void)
{
  size_t x = 2;
  size_t y = 3;
  int (*aptr)[x][y];

  arr_alloc(x, y, &aptr);
  arr_fill(x, y, *aptr);
  arr_print(x, y, *aptr);
  free(aptr); // free the whole 2D array

  return 0;
}

C에는 (기본 데이터 유형으로서의) 다차원 배열이 없습니다.그러나 어레이(또는 다른 Aggregate)와 포인터 어레이가 있을 수 있습니다.

가능한 접근법은 다음과 같은 추상적인 데이터 유형(유연한 어레이 멤버 사용, 즉 구현 요령 중 하나일 수 있으며 다른 접근 방식을 사용할 수 있음)으로 추론하는 것입니다.

추상적인 데이터 유형은 제안할 수 없습니다. 왜냐하면 그건 숙제 내용에 따라 달라지지만, 우리에겐 없습니다.추상적인 데이터 유형을 (종이로) 설계하고 나중에 구현해야 합니다.

ADT에 필요한 모든 조작을 (종이 또는 보드에) 리스트 하면, 간단하게 실장할 수 있습니다.

이 코드는 잘 작동합니다!어떻게 틀릴 수 있죠?

그 문장은 일관성이 없다(잘못된 명세서는 무엇입니까?)...

모든 경고 및 디버깅 정보를 사용하여 컴파일할 것을 권장합니다(예: gcc -Wall -Wextra -g경고를 받지 않을 때까지 코드를 개선하고 디버거를 사용합니다.gdb(프로그램에서 무슨 일이 일어나고 있는지 이해하기 위해) 및 기타 도구(볼라인드 등)를 사용합니다.

언급URL : https://stackoverflow.com/questions/42094465/correctly-allocating-multi-dimensional-arrays

반응형

'sourcecode' 카테고리의 다른 글

vuex 스토어의 악리를 통해 게시한 후 리다이렉트하는 올바른 방법  (0) 2022.08.17
Vue.js2 - Object.assign({}, this.var)을 차단하는 감시 메서드  (0) 2022.08.17
C 실행 파일 이름 결정  (0) 2022.08.17
구성 요소에서 내 스토어 개체에 액세스할 수 없음  (0) 2022.08.17
Vue. vuex 상태에 따라 창 닫기 방지  (0) 2022.08.17

'sourcecode'의 다른글

  • 현재글다차원 어레이의 올바른 할당

관련글

댓글

티스토리툴바