동적배열

출처 http://www.winapi.co.kr/clec/cpp2/19-1-2.htm
동적 배열

앞에서 작성한 예제에서 보았다시피 배열도 메모리를 조작하면 중간에 삽입, 삭제가 가능하여 크기가 가변적인 정보를 다룰 수 있다. 그러나 새로운 요소가 삽입된다 하더라도 배열의 크기가 자동으로 늘어나는 것은 아니므로 미리 선언한 크기 이상의 요소를 추가할 수는 없다. 앞 예제의 ar 배열은 크기 16으로 선언되었으므로 최대 15개의 문자만을 저장할 수 있을 뿐이다. 설사 배열을 동적으로 할당한다 하더라도 할당할 때 필요한 크기를 지정해야 하므로 배열의 크기는 언제나 유한하다.

C언어는 중급 언어라는 특성상 배열의 범위를 전혀 점검하지 않기 때문에 배열을 넉넉한 크기로 선언하는 것만으로는 충분하지 않다. 근본적인 문제는 배열이 작은 것이 아니라 필요한 크기를 미리 예측할 수 없다는 데 있으므로 신축성 있는 관리가 필요하다. 크기가 가변적인 정보는 이론적으로 무한대까지 늘어날 수 있어야 하며 이런 정보들을 관리하기 위해서는 배열도 정보의 양에 따라 실행중에 확장 가능해야 한다. 물론 컴퓨터의 메모리가 유한하기 때문에 실질적인 무한 배열은 불가능하지만 메모리가 허락하는 한까지(=실질적인 무한대)는 정보를 저장할 수 있어야 안전하다.

실행중에 필요한만큼 크기를 늘렸다 줄였다 할 수 있는 배열을 동적 배열이라고 한다. C언어 차원에서 동적 배열에 대한 지원은 전혀 없으므로 이런 배열은 직접 만들어 쓰는 수밖에 없다. 참고로 C++로 만든 라이브러리(MFC, STL 등)에는 동적 배열 클래스가 제공되는데 이런 클래스의 내부도 여기서 만드는 예제와 거의 동일한 원리를 사용한다. 그래서 이 장의 예제를 이해하면 이후 고수준 라이브러리의 내부도 쉽게 이해할 수 있다.

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

 

예 제 : DynArray

#include <Turboc.h>

 

#define ELETYPE int

ELETYPE *ar;

unsigned size;

unsigned num;

unsigned growby;

 

void InitArray(unsigned asize, unsigned agrowby)

{

     size=asize;

     growby=agrowby;

     num=0;

     ar=(ELETYPE *)malloc(size*sizeof(ELETYPE));

}

 

void Insert(int idx, ELETYPE value)

{

     unsigned need;

 

     need=num+1;

     if (need > size) {

          size=need+growby;

          ar=(ELETYPE *)realloc(ar,size*sizeof(ELETYPE));

     }

     memmove(ar+idx+1,ar+idx,(num-idx)*sizeof(ELETYPE));

     ar[idx]=value;

     num++;

}

 

void Delete(int idx)

{

     memmove(ar+idx,ar+idx+1,(num-idx-1)*sizeof(ELETYPE));

     num--;

}

 

void Append(ELETYPE value)

{

     Insert(num,value);

}

 

void UnInitArray()

{

     free(ar);

}

 

void DumpArray(char *sMark)

{

     unsigned i;

     printf("%16s => 크기=%02d,개수=%02d : ",sMark,size,num);

     for (i=0;i<num;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개로 부족하므로 이 때 재할당되어 배열은 크기 16으로 늘어난다. 더 많은 요소를 삽입하면 배열은 자동으로 필요량을 판단하여 늘어날 것이다. 어째서 이렇게 되는지 차근 차근 분석해 보자.

배열의 실체

이 예제에서 배열의 실체는 ar 포인터이다. int ar[1000]; 이런 식으로 배열을 선언하면 크기와 위치가 컴파일할 때 확정되어 버리므로 가변적인 크기를 다룰 수 없다. 그래서 저장하고자 하는 타입의 포인터를 선언하고 이 포인터를 동적으로 할당해야 한다. ELETYPE 매크로는 배열 요소의 타입인데 필요에 따라 변경할 수 있도록 매크로 상수로 정의했다. 이 예제는 가장 단순한 타입인 정수(int)를 배열 요소로 사용했지만 임의의 모든 타입에 대해서도 동적 배열을 만들 수 있다.

배열 관리 변수

동적 배열은 컴파일할 때 그 크기가 미리 정해지지 않으며 실행중에 언제든지 크기를 변경할 수 있어야 한다. 그래서 현재 얼마만큼 할당되어 있는지 할당 크기를 별도의 변수에 저장해 두어야 하는데 size 변수가 배열의 할당 크기를 기억한다. 또한 배열에 실제 저장된 요소의 개수도 항상 유지해야 하는데 num 변수가 이 정보를 저장한다. 배열 관리 함수들은 배열에 요소를 삽입할 때 이 두 변수값을 비교해 보고 재할당할 시점을 파악할 것이다. growby 변수는 재할당할 때의 여유분을 지정하는데 이 변수의 역할에 대해서는 잠시 후 따로 알아보도록 하자.

배열 초기화

배열의 실체인 ar이 포인터 변수이므로 ar에 메모리가 할당되기 전까지 배열은 실제로 존재하지 않는다. 포인터가 실질적인 배열이 되기 위해서는 일단 메모리를 초기 할당해야 한다. InitArray 함수는 배열 관리 변수의 초기값을 설정하고 이 초기값대로 메모리를 할당하여 ar 포인터에 그 번지를 대입한다. 이 함수는 배열을 사용하는 주체가 호출하는데 이 예제의 경우 main 함수의 선두에서 호출하고 있다.

main에서 InitArray(10,5) 로 호출했으므로 배열의 초기 할당치는 10이 되고 여유분은 5로 설정된다. InitArray 함수는 전달받은 인수로 관련 변수를 초기화하고 ar에 size 개수만큼의 요소를 저장할 수 있는 메모리를 할당한다. 배열이 초기화되는 상황이므로 요소의 개수 num은 0으로 초기화될 것이다. size와 num은 모두 바이트 단위가 아니라 배열 요소의 개수 단위이므로 필요한 메모리양을 구하기 위해서는 sizeof(ELETYPE)을 곱해야 한다.

초기화가 완료되면 정수형 변수 10개를 저장할 수 있는 메모리가 할당되고 이 메모리의 선두를 ar 포인터가 가리키게 된다. 그리고 size는 할당 크기 10을 기억하며 아직 배열에 값이 저장되지 않았으므로 num은 0이다. 이 상태에서 ar은 크기 10의 정수형 배열과 같아지며 10개의 정수값을 기억할 수 있다. main에서는 1~8까지 8개의 정수를 추가했으며 이 때의 ar 배열을 그림으로 그려 보면 다음과 같다.

총 10개의 요소를 기억할 수 있으며 8개를 저장했으므로 아직 두 개의 여유가 남아 있는 상황이다. 물론 이 남은 칸에는 쓰레기값이 들어 있을 것이다. 배열을 다 사용한 후에는 UnInitArray 함수를 호출하여 사용하던 메모리를 해제하는데 free 함수로 ar에 동적할당한 메모리만 회수하면 된다. main 함수의 끝에서 UnInitArray를 호출하고 있다.

재할당

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

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

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

여유분

배열을 재할당할 때는 어느 정도의 여유분을 주는 것이 효율상 유리하다. 삽입은 보통 연속적으로 일어나므로 메모리가 부족해서 크기를 늘려야 한다면 조만간 메모리가 다시 부족해질 확률이 아주 높다. need만큼 필요해졌을 때 need만큼만 재할당하면 일단은 삽입 가능하지만 잠시 후 다시 재할당해야 할 것이다. realloc 함수는 편리하기는 하지만 번지가 바뀔 경우 굉장히 느리며 특히 배열의 크기가 클수록 속도상의 불이익이 심하기 때문에 가급적이면 호출 회수를 줄여야 한다. 그래서 이왕 재할당을 할 때 여유분을 주어 다음 번 부족한 상황을 최대한 늦추는 것이 좋다.

동적 배열은 이런 목적으로 growby라는 변수를 정의하고 재할당할 때 need에 이 값을 더한 크기로 배열을 늘린다. 여유분은 어디까지나 여유를 두기 위한 값이므로 이 값이 0이더라도 동적 배열은 제대로 동작하겠지만 성능이 떨어진다. 그렇다고 해서 여유분을 지나치게 크게 주면 남는 메모리가 많아져 공간 효율이 떨어진다. 필요에 따라 적당한 양을 주는 것이 좋으며 그래서 InitArray 함수를 호출할 때 개발자가 결정할 수 있도록 해 두었다.

예제에서는 재할당이 빨리 일어나도록 하기 위해 초기값, 여유분을 10, 5로 주었지만 실제 프로젝트에서는 배열의 삽입, 삭제 빈도에 따라 초기값과 여유분을 적당한 크기로 선택해야 한다. 100, 50 정도면 대체로 쓸만한 성능을 보일 것이며 자료의 양이 많고 삽입도 빈번하다면 1000, 500 정도로 충분한 값을 주어 성능의 향상을 꾀할 수 있다. 즉 InitArray의 인수들은 배열의 성능 파라미터이다.

그 외 함수의 변화

그 외 나머지 함수들은 어떤 변화가 생겼는지 동적 할당을 하지 않는 앞의 예제와 비교해 보자. Insert 함수에는 배열 크기 점검과 재할당문이 추가되었고 배열 요소를 삽입하는 코드는 앞의 예제와 거의 비슷하다. 다만 memmove 함수의 이동 길이가 조금 달라졌다. 배열에 기억되는 값이 문자열이 아니므로 널 종료 문자를 이동 길이에 포함시킬 필요가 없으며 문자형에 대한 배열이 아닌 임의 타입에 대한 배열이므로 sizeof(ELETYPE)을 곱해야 한다.

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

Delete 함수도 마찬가지로 이동 길이를 계산하는 식만 달라졌으며 논리는 동일하다. 만약 배열 요소가 다량 삭제되어 지나치게 남는 메모리가 많다면 배열 크기를 줄이는 것도 가능하다. 이 경우 Delete에 현재 할당 크기와 요소 개수를 비교하여 일정 기준 이하일 때, 예를 들어 num이 size의 절반도 안될 때 size를 줄이는 코드를 작성하면 된다. 그러나 늘어난 배열을 굳이 줄여야 하는 경우는 극히 드물기 때문에 이 코드는 작성하지 않았으며 현실적으로 별로 효용성이 없다. Append 함수는 앞의 예제와 완전히 동일하다.

 

이상으로 실행중에 크기를 변경할 수 있는 동적 배열을 만들어 보고 간단하게 분석해 보았다. 이 예제는 완벽하게 동작하지만 예제로서의 간결성을 중요시하다 보니 몇 가지 마음에 들지 않는 면이 있다. 우선 배열 관리를 위해 전역변수가 필요하고 이 변수들을 관리하는 별도의 함수까지 있어 재활용하기가 번거로운 편이다. 그래서 여러 개의 동적 배열을 동시에 사용할 수 없다. InitArray도 수동으로 호출해야 하고 다 사용한 후 UnInitArray를 호출하여 배열을 해제하는 것도 잊어서는 안된다.

편리하고 안전한 사용을 위해 좀 더 형식성을 갖출 필요가 있는데 이럴 때 사용하는 것이 바로 C++의 클래스이다. 배열 관리 변수와 관련 함수들을 클래스로 묶어 놓으면 객체를 선언하는 것만으로 동적 배열을 쉽게 생성하고 사용할 수 있으며 자신이 필요없어졌을 때 메모리를 자동으로 정리하도록 할 수 있다. CArray ar; ar.Insert(), ar.Delete() 식으로 편리하게 사용할 수 있다. 또한 배열의 대상 타입을 ELETYPE이라는 매크로로 바꿀 수는 있지만 동시에 여러 타입에 대한 동적 배열을 만들 수는 없다. 이 문제는 C++의 템플릿으로 해결할 수 있다.

3부에서는 클래스로 동적 배열 타입을 만들어 볼 것이고 이 클래스를 템플릿으로 만들어 일반적인 타입에 대해 범용적으로 사용할 수 있도록 실습할 것이다. 또한 활용성을 높이기 위해 검색, 복수 삽입, 배열끼리의 병합 등 좀 더 많은 기능들을 추가해 보도록 하자. 여기서는 C 수준에서 동적 배열을 작성하는 방법에 대해서만 정리하고 넘어가기로 한다.