[C/C++][자료구조] 동적배열

[C/C++][자료구조] 동적배열

이전 포스팅에서 배열도 메모리를 조작하면 중간에 삽입, 삭제가 가능하다는 것을 예제코드를 중심으로 배웠다. 이번 포스팅에서는 크기가 가변적인 배열을 만드는 방법에 대해 다루도록 하겠다.

배열에 새로운 요소가 삽입된다 하더라도 배열의 크기가 자동으로 늘어나는 것은 아니다. 이처럼 배열은 미리 선언한 크기 이상의 요소를 추가할 수는 없다. 이에 대한 근본적인 문제를 해결하기 위해서는 필요에 따라 크기가 늘었다 줄었다하는 배열 즉, 동적배열을 만들어야 한다는 것이다.

동적배열을 만드는 기본 원리는 최초 적당한 길이로 초기 할당하되 삽입되는 정보가 할당된 메모리양을 초과할 때 배열의 크기를 더 늘리는 것이다. 핵심 기술은 기존의 할당된 메모리를 재할당하는 realloc 함수라고 할 수 있다.

다음 아래 예제코드를 통해 동적배열을 파헤쳐 보자

#include ...
 
#define ELETYPE int
ELETYPE *ar;
unsigned size;
unsigned n;
unsigned growby;
 
void InitArray(unsigned asize, unsigned agrowby)
{
     size=asize;
     growby=agrowby;
     n=0;
     ar=(ELETYPE *)malloc(size*sizeof(ELETYPE));
}
 
void Insert(int idx, ELETYPE value)
{
     unsigned need;
 
     need=n+1;
     if (need > size) {
          size=need+growby;
          ar=(ELETYPE *)realloc(ar,size*sizeof(ELETYPE));
     }
     memmove(ar+idx+1,ar+idx,(n-idx)*sizeof(ELETYPE));
     ar[idx]=value;
     n++;
}
 
void Delete(int idx)
{
     memmove(ar+idx,ar+idx+1,(n-idx-1)*sizeof(ELETYPE));
     n--;
}
 
void Append(ELETYPE value)
{
     Insert(n,value);
}
 
void UnInitArray()
{
     free(ar);
}
 
void DumpArray(char *sMark)
{
     unsigned i;
     printf("%16s => 크기=%02d,개수=%02d : ",sMark,size,n);
     for (i=0;i<n;i++) printf("%2d ",ar[i]);
     printf("\n");
}
 
void main()
{
     int i;
 
     InitArray(10,5);DumpArray("최초");
     for (i=1;i<=8;i++) Append(i);DumpArray("8개 추가");
     Insert(3,10);DumpArray("10 삽입");
     Insert(3,11);DumpArray("11 삽입");
     Insert(3,12);DumpArray("12 삽입");
     Delete(7);DumpArray("요소 7 삭제");
 
     UnInitArray();
}

효율적인 배열 관리를 위해 이전 "배열 요소의 삽입, 삭제" 포스팅에서 구현한 예제코드 보다 몇 가지 함수가 더 추가되었다. 

DumpArray 함수는 결과 테스트를 위한 함수일 뿐이고 나머지는 동적 배열을 관리하는 함수이다.

일단 예제코드가 잘 동작하는지 테스트해 보자. 아래는 결과 값과 그에 대한 간단한 설명이다. 

• 최초          => 크기=10,개수=00 :

• 8개 추가     => 크기=10,개수=08 :  1  2  3  4  5  6  7  8
• 10 삽입      => 크기=10,개수=09 :  1  2  3 10  4  5  6  7  8
• 11 삽입      => 크기=10,개수=10 :  1  2  3 11 10  4  5  6  7  8
• 12 삽입      => 크기=16,개수=11 :  1  2  3 12 11 10  4  5  6  7  8
• 요소 7 삭제  => 크기=16,개수=10 :  1  2  3 12 11 10  4  6  7  8

최초 배열은 크기 10으로 초기화 작업이 실행되고 이후 루프를 돌며 8개의 값을 저장했다. 이 상태에서 10, 11, 12를 차례로 삽입했는데 10, 11까지는 남은 두 요소에 저장하면 되지만 12가 삽입될 때는 초기 할당된 10 크기로 부족하므로 Insert 함수 내부에서 크기를 재할당하여 배열의 크기가 16으로 늘어난다. 더 많은 요소를 삽입하면 배열은 자동으로 필요량을 판단하여 늘어날 것이다.

여기까지 이해가 됬으면 예제코드를 통해 보다 배열의 상세 원리에 대해 차근 차근 분석해 보도록 하겠다.

배열의 실체

• 위 예제코드에서 배열의 실체는 ar 포인터이다.

• int ar[1000]; 이런 식으로 배열을 선언하면 크기와 위치가 컴파일할 때 확정되어 버리므로 가변적인 크기를 다룰 수 없다. 그래서 저장하고자 하는 타입의 포인터를 동적으로 할당해야 한다.

• ELETPYE 매크로는 배열 요소의 타입인데 필요에 따라 변경할 수 있도록 매크로 상수로 정의했다.

• * 예제코드에서는 가장 단순한 타입인 정수(int)를 배열 요소로 사용했지만 임의의 모든 타입에 대해서도 동적배열을 만들 수 있다.

배열 관리 변수

• 동적배열은 컴파일할 때 그 크기가 미리 정해지지 않으며 실행중에 언제든지 크기를 변경할 수 있어야 한다. 그래서 현재 얼마만큼 할당되어 있는지 할당 크기를 별도의 변수에 저장해 두어야 하는데 size 변수가 배열의 할당 크기를 기억한다. 또한 배열에 실제 저장된 요소의 개수도 항상 유지해야 하는데 n 변수가 이 정보를 저장한다.

• 배열 관리 함수들은 배열에 요소를 삽입할 때 이 두 변수(size, n)값을 비교해 보고 재할당할 시점을 파악한다.

• growby 변수는 재할당할 때의 여유분을 지정하는데 이 변수의 역할에 대해서는 잠시 후 아래 '재할당' 부분에서 따로 알아보도록 하겠다.

배열 초기화

• 배열의 실체인 ar이 포인터 변수이므로 ar에 메모리가 할당되기 전까지 배열은 실제로 존재하지 않는다.

• 포인터가 실질적인 배열이 되기 위해서는 일단 메모리를 초기 할당해야 한다.

• InitArray 함수는 배열 관리 변수의 초기값을 설정하고 이 초기값대로 메모리를 할당하여 ar 포인터에 그 번지를 대입한다. 이 함수는 배열을 사용하는 주체가 호출하는데 위 예제코드의 경우 main 함수의 선두에서 호출하고 있다.

• 예제코드를 보면 main에서 InitArray(10,5) 로 호출했으므로 배열의 초기 할당치는 10이 되고 여유분은 5로 설정된다. 또한, 배열이 초기화되는 상황이므로 요소의 개수 num은 0으로 초기화될 것이다. size와 num은 모두 바이트 단위가 아니라 배열 요소의 개수 단위이므로 필요한 메모리양을 구하기 위해서는 sizeof(ELETYPE)을 곱해야 한다. 초기화가 완료되면 정수형 변수 10개를 저장할 수 있는 메모리가 할당되고 이 메모리의 선두를 ar 포인터가 가리키게 된다. 그리고 size는 할당 크기 10을 기억하며 아직 배열에 값이 저장되지 않았으므로 num은 0이다. 

• 예제코드의 main을 보면 1~8까지 8개의 정수를 추가했으므로 아직 2개의 여유가 남아 있는 상태이다. 물론 이 남은 칸에는 쓰레기값이 들어 있을 것이다.

• 배열을 다 사용한 후에는 UnInitArray 함수를 호출하여 사용하던 메모리를 해제하는데 free 함수로 ar에 동적할당한 메모리만 회수하면 된다. 예제코드의 main 함수의 끝에서 UnInitArray를 호출하고 있다.

재할당

• 1~8까지의 정수를 추가한 후 10, 11, 12 요소 3의 위치에 순서대로 삽입하는데 10, 11까지 삽입되면 ar은 꽉 찬 상태가 된다. 이 상태에서 12를 더 삽입하려면 기억 공간이 부족하므로 배열의 크기를 늘려 재할당해야 한다. 배열의 크기가 늘어나는 경우는 Insert 함수에서 요소를 추가할 때 뿐이므로 이 함수의 선두에서만 배열 크기를 점검하면 된다.

• 재할당할 조건은 아주 상식적이다. Insert 함수가 호출되었을 때 필요한 배열 크기는 현재 요소 개수인 num에 추가될 하나를 더해 num+1이며 이 값을 need 변수에 대입했다. 원한다면 여러 개를 한꺼번에 삽입하는 것도 물론 가능하다. need가 할당된 크기인 size보다 더 클 때 이 때가 바로 배열의 크기를 늘릴 때이다.

• 현재 크기가 부족하다는 판단이 내려졌으므로 새로운 크기를 계산하되 일단 need 이상 되어야 하고 여기에 약간의 여유분 growby를 더했다. size는 16이 되며 이 크기대로 realloc 함수를 호출하여 ar 배열을 재할당한다. realloc 함수는 ar 배열을 크기로 재할당하며 필요할 경우 번지를 옮겨 기존 메모리의 값을 복사해 주기까지 하므로 이 함수만 호출하면 ar은 내용을 유지한 채로 지정한 크기만큼 늘어나게 된다. 만약 need가 size보다 더 작다면, 즉 아직 여유분이 남아 있다면 재할당없이 기존의 방법대로 삽입한다.

여유분

• 배열을 재할당할 때는 어느 정도의 여유분을 주는 것이 효율상 유리하다. 삽입은 보통 연속적으로 일어나므로 메모리가 부족해서 크기를 늘려야 한다면 조만간 메모리가 다시 부족해질 확률이 아주 높다.

• need만큼 필요해졌을 때 need만큼만 재할당하면 일단은 삽입 가능하지만 잠시 후 다시 재할당해야 할 것이다.

• realloc 함수는 편리하기는 하지만 번지가 바뀔 경우 굉장히 느리며 특히 배열의 크기가 클수록 속도상의 불이익이 심하기 때문에 가급적이면 호출 회수를 줄여야 한다. 그래서 이왕 재할당을 할 때 여유분을 주어 다음 번 부족한 상황을 최대한 늦추는 것이 좋다.

• 동적배열은 이런 목적으로 growby라는 여유분 변수를 정의하고 재할당할 때 need에 이 값을 더한 크기로 배열을 늘린다. 필요에 따라 적당한 양을 주는 것이 좋으며 초기 InitArray 함수를 호출할 때 개발자가 결정할 수 있도록 코드를 작성하는 것이 좋다.

그 외 함수의 변화(문자열을 저장하는 정적배열→정수형을 저장하는 동적배열)

• 우선 가장 먼저 InitArray 함수에서 배열의 크기를 재할당 할 때 늘려줄 여유분에 대한 변수 값을 설정해주었다.

• Insert 함수에는 배열 크기 점검과 재할당문이 추가되었고 memmove 함수의 이동 길이가 조금 달라졌다. 배열에 기억되는 값이 문자열이 아닐 경우에는 null 종료 문자를 이동 길이에 포함시킬 필요가 없으므로 sizeof(ELETYPE)을 곱해야 한다.

• 문자열이나 포인터는 끝 표식에 사용할 수 있는 특이값(null)이 있지만 정수형이나 실수형에는 이런 목적으로 사용할 수 있는 특이값이 따로 없다. 그래서 배열에 저장된 요소의 실제 개수를 저장하는 num이라는 별도의 변수가 필요하다.

• Delete 함수도 Insert 함수와 마찬가지로 이동 길이를 계산하는 식이 달라졌다.

* 참고 - 소프트웨어 공학연구소 C/C++ 강좌 (http://soen.kr/)