지난 시간에 배웠던 동적 할당을 활용해 가변 배열을 만들어보자.
가변 배열이란 이전에 배웠던 크기가 고정되어 있는 일반 배열과 달리 크기에 변동이 생길 수 있는 배열이다.
따라서 아래처럼 지역변수를 사용할 수 없다.
int main()
{
int a = 100;
int iInput = 0;
scanf_s("%d", &a);
int arr[a] = {}; // 사용불가
return 0;
}
같은 맥락으로 구조체도 살펴보자. 구조체 안에는 사용자가 임의로 변수를 멤버로 넣을 수 있다.
하지만 역시 이 구조체 안에도 배열 개수를 선언할 때는 다음과 같이 변수를 사용한 동적 배열은 만들 수 없다.
int g_i = 100;
typedef struct _tagST
{
int iArr[g_i]; // 사용불가
}ST;
그렇다면 어떻게 해야 동적 할당이 가능한 가변 배열을 만들 수 있을까?
바로 힙 메모리 영역에 저장된 것을 사용하는 것이다.
이를 위해서 가변 배열이라는 어떤 형태를 선언하고 그걸 가변 배열의 동작을 하는 객체로 만드는 방법을 사용한다.
여기서 객체에 대해 생각해 보자.
객체란 int가 자료형이라면 int a가 바로 객체에 해당한다.
비유하자면 int라는 자료형(붕어빵틀)을 실제로 만들어낸 데이터(붕어빵)인 것이다.
이러한 내용을 바탕으로 가변 배열을 직접 만들어보기 위해 새로운 헤더 파일을 하나 생성해 본다.
<Arr.h>
typedef struct _tagArr
{
}tArr;
가변 배열이란 자료형으로서 역할을 하려면 어떤 멤버들을 가지고 있어야 할까?
앞서 언급한 것처럼 힙 메모리 영역에 저장되는 데이터를 멤버로 가져야 한다.
// <가변 배열의 구현>
typedef struct _tagArr
{
int* pArr; // 데이터가 시작되는 지점을 알고 있어야 한다
int iCount; // 다음 데이터가 어디부터 시작인지 알기 위해 현재까지
// 들어온 데이터가 몇 개인지 알아야 한다
int iMaxCount; // 데이터가 최대 몇 개까지 들어갈 수 있는지 한계치를 알아야 한다
}tArr;
구현한 배열을 main 함수에서 실제로 사용하기 위해 초기화를 해보자.
int main()
{
tArr s;
s.pInt = (int*) malloc(40)
s.iCount = 0;
s.iMaxCount = 10; // 인트형이 40바이트 들어있으므로 10개
return 0;
}
위의 초기화 내용은 자주 반복될 것이므로 초기화 함수를 만들어 사용하는 것이 효율적이다.
// <Arr.h>
typedef struct _tagArr
{
int* pInt; // 데이터가 시작되는 지점을 알고 있어야 한다
int iCount; // 다음 데이터가 어디부터 시작인지 알기 위해 현재까지
// 들어온 데이터가 몇 개인지 알아야 한다
int iMaxCount; // 데이터가 최대 몇 개까지 들어갈 수 있는지 한계치를 알아야 한다
}tArr;
void InitArr(tArr* _pArr); // 헤더에 직접 함수를 모두 구현하면 복사붙여넣기 과정에서
// 중복되므로 선언만 해준다.
헤더에 선언한 함수를 Arr.cpp에 구현한다.
<Arr.cpp>
#include "Arr.h"
#include <iostream>
void InitArr(tArr* _pArr)
{
// '->' 멤버접근
_pArr->pInt = (int*)malloc(sizeof(int) * 2); // 미리 8 바이트만큼의 공간을 할당
_pArr->iCount = 0;
_pArr->iMaxCount = 10;
}
<main.cpp>
#include <iostream>
#include "Arr.h"
int main()
{
tArr s = {}; // 메인 함수 종료시 배열 객체 메모리가 해제 됨.
// 이때 단순히 배열 객체만 해제되면 객체의 멤버가 가르키고 있던 실질적 데이터
// 저장 공간이었던 힙 메모리에는 해제를 해주지 않기 때문에 메모리 누수가 발생한다.
// 즉, 아래에서 InitArr()로 초기화를 진행하고 나면 나중에 사용 목적이 끝난 뒤
// 종료 직전에 힙 메모리 영역에 넣고 쓰고 있던 메모리를 해제해주어야 한다.
InitArr(&s);
return 0;
}
힙 메모리 영역에 할당된 것을 해제해 주기 위해 배열 메모리 해제 함수와 데이터를 넣어서 실질적으로 활용해 볼 데이터 추가 함수를 추가한다.
<Arr.h>
// 배열 초기화 함수
void InitArr(tArr* _pArr);
// 데이터 추가 함수
void PushBack(tArr* _pArr, int _iData);
// 공간 추가 확장 (추후 구현)
void Reallocate(tArr* _pArr);
// 배열 메모리 해제 함수
void ReleaseArr(tArr* _pArr);
<Arr.cpp>
void PushBack(tArr* _pArr, int _iData)
{
// 배열에 데이터를 추가하기 전에 먼저 현재 개수와 최대 개수가 같은지 체크해야한다.
if (_pArr->iMaxCount <= _pArr->iCount) // 힙 영역에 할당한 공간이 다 찬 경우
{
// 재할당
Reallocate(_pArr);
}
// 공간 문제가 없어 할당이 가능한 경우
// 데이터 추가 (현재 주소의 첫번째 칸부터 데이터를 추가한다)
// 가변 배열 객체 안에 힙 메모리 주소 변수와 카운트를 동시에 세고 있다.
// 그 다음에 들어갈 것은 가변 배열이 가진 주소 변수로 가서
// 인덱스 접근을 할 건데, 그때의 인덱스가 본인이 가진 카운터 값이다.
// 그 카운터 값을 가지고 주소에 접근해서 그 위치의 데이터를 수정하고 나면
// 카운트 값이 증가해야 개수가 1 증가하면서
// 또 다음 번에 그걸 그대로 맞물려 돌아간다.
// 따라서 후위 연산자를 사용해 입력까지 다 끝나고 나서 카운터 값이 증가하도록 한다.
_pArr->pInt[_pArr->iCount++] = _iData;
}
void ReleaseArr(tArr* _pArr)
{
free(_pArr->pInt); // 할당한 메모리를 해제함
_pArr->iCount = 0; //
_pArr->iMaxCount = 0;
}
메모리를 직접 할당하는 동적 할당 기능이 필요하기 때문에 가변 배열을 구현할 땐 유의할 사항이 많다.
실수로 크기를 원래 하려고 했던 것보다 크게 잡거나, 할당하지 않은 곳에 접근해서
메모리를 수정하거나 써 버리는 경우 심각한 문제가 발생할 수 있다.
힙 손상이라고도 하는 이러한 오류는 실행 중에는 발견되지 않다가 뒤늦게 발견될 수 있기 때문에
문제가 발생한 원인을 쉽게 알 수 없어 이슈 발생 시 해결하기가 쉽지 않다.
malloc 함수에서 다루는 동적할당이라는 동작 자체가 메모리를 할당 받고 주소를 전달받는 방식인데,
이때 내가 원하는 주소를 받을 수 있는 것은 아니고 요청한 사이즈 만큼 할당 받은 곳의 주소를 줄 뿐이다.
그렇다면 사용할 배열의 공간이 모자랄 때 뒤이어서 추가적으로 메모리를 확장한다는 게 가능할까?
처음에 동적 할당을 받을 때 충분히 넉넉한 공간을 잡아 줘야 한다.
즉, 두 칸을 쓸 수 있도록 할당했다면 그 공간이 다 찼을 때, 두 칸을 뒤이어 붙일 것이 아니라 한번에 네 칸을 넣을 만큼 새로 공간을 받아야 한다.
따라서 가변 배열의 데이터에 현재 할당한 데이터가 꽉 찼을 때는 공간을 늘려야한다.
이 공간을 늘리는 규칙에 대해서 알아보자.
1. 기존에 들어갈 사이즈보다 더 큰 사이즈의 공간을 할당해야한다.
// 1. 2배 더 큰 공간을 동적할당한다.
int* pNew = (int*)malloc(_pArr->iMaxCount * 2 * sizeof(int));따라서 들어갈 사이즈가 기존 최대 카운트 값에서 일정 배 한 만큼에서 자료형 타입의 사이즈만큼 공간을 할당한다.
그러면 새롭게 할당된 주소가 나오게 된다.
이 주소를 지역변수로 받아 놓아야 활용을 할 수 있다.
2. 기존 공간에 있던 데이터들을 새로 할당한 공간으로 복사시킨다.
기존에 있던 데이터들을 그대로 옮겨갈 수 있도록 새로 할당한 공간에 복사시킨다.
for (int i = 0; i < _pArr->iCount; ++i)
{
pNew[i] = _pArr->pInt[i];
}
3. 기존 공간은 메모리 해제
이제 모든 값을 새 배열에 복사했으므로 이전 배열의 값들은 필요가 없어졌다. 기존 공간의 메모리를 전부 해제한다.
free(_pArr->pInt);
4. 배열에 새로 할당된 공간을 가리키게 한다.
새롭게 할당한 데이터를 제대로 사용하려면 배열의 주소와 연결하여 실제로 그 공간을 가리키게 해야 한다.
_pArr->pInt = pNew;
5. MaxCount 변경점 적용
배열이 변경되었으니 올바른 작동을 위해 데이터가 최대 몇 개까지 들어갈 수 있는지 표시하는 MaxCount 값을 수정한다.
_pArr->iMaxCount *= 2;
아래는 전체 코드이다.
<main.cpp>
#include <iostream>
#include "Arr.h"
int main()
{
tArr s1 = {};
InitArr(&s1);
for (int i = 0; i < 10; i++)
{
PushBack(&s1, i);
}
for (int i = 0; i < s1.iCount; ++i) // 미리 보유하고 있는 개수만큼 반복문을 돌면서
// 데이터를 하나씩 출력한다.
{
printf("%d\n", s1.pInt[i]);
}
Reallocate(&s1);
ReleaseArr(&s1);
return 0;
}
<Arr.h>
#pragma once
typedef struct _tagArr
{
int* pInt; // 데이터가 시작되는 지점을 알고 있어야 한다
int iCount; // 다음 데이터가 어디부터 시작인지 알기 위해 현재까지
// 들어온 데이터가 몇 개인지 알아야 한다
int iMaxCount; // 데이터가 최대 몇 개까지 들어갈 수 있는지 한계치를 알아야 한다
}tArr;
// 배열 초기화 함수
void InitArr(tArr* _pArr);
// 데이터 추가 함수
void PushBack(tArr* _pArr, int _iData);
// 공간 추가 확장
void Reallocate(tArr* _pArr);
// 배열 메모리 해제 함수
void ReleaseArr(tArr* _pArr);
<Arr.cpp>
#include "Arr.h"
#include <iostream>
void InitArr(tArr* _pArr)
{
// '->' 멤버접근
_pArr->pInt = (int*)malloc(sizeof(int) * 2); // 미리 8 바이트만큼의 공간을 할당
_pArr->iCount = 0;
_pArr->iMaxCount = 10;
}
void PushBack(tArr* _pArr, int _iData)
{
// 배열에 데이터를 추가하기 전에 먼저 현재 개수와 최대 개수가 같은지 체크해야한다.
if (_pArr->iMaxCount <= _pArr->iCount) // 힙 영역에 할당한 공간이 다 찬 경우
{
// 재할당
Reallocate(_pArr);
}
// 공간 문제가 없어 할당이 가능한 경우
// 데이터 추가 (현재 주소의 첫번째 칸부터 데이터를 추가한다)
// 가변 배열 객체 안에 힙 메모리 주소 변수와 카운트를 동시에 세고 있다.
// 그 다음에 들어갈 것은 가변 배열이 가진 주소 변수로 가서
// 인덱스 접근을 할 건데, 그때의 인덱스가 본인이 가진 카운터 값이다.
// 그 카운터 값을 가지고 주소에 접근해서 그 위치의 데이터를 수정하고 나면
// 카운트 값이 증가해야 개수가 1 증가하면서
// 또 다음 번에 그걸 그대로 맞물려 돌아간다.
// 따라서 후위 연산자를 사용해 입력까지 다 끝나고 나서 카운터 값이 증가하도록 한다.
_pArr->pInt[_pArr->iCount++] = _iData;
}
// 공간 추가 확장
void Reallocate(tArr* _pArr)
{
// 1. 2배 더 큰 공간을 동적할당한다.
int* pNew = (int*)malloc(_pArr->iMaxCount * 2 * sizeof(int));
// 2. 기존 공간에 있던 데이터들은 새로 할당한 공간으로 복사시킨다.
for (int i = 0; i < _pArr->iCount; ++i)
{
pNew[i] = _pArr->pInt[i];
}
// 3. 기존 공간은 메모리 해제
free(_pArr->pInt);
// 4. 배열이 새로 할당된 공간을 가리키게 한다.
_pArr->pInt = pNew;
// 5.
_pArr->iMaxCount *= 2;
}
void ReleaseArr(tArr* _pArr)
{
free(_pArr->pInt); // 할당한 메모리를 해제함
_pArr->iCount = 0; //
_pArr->iMaxCount = 0;
}추가로 재할당과 같은 중요한 기능을 하는 함수가 메인 함수에서 함부로 호출되지 않게 하기 위해서 특정 기능을 헤더와 CPP 파일에 묶어서 자료형으로 구현을 하면 헤더에 추가하지 않고 CPP에서 구현함으로서 접근을 막을 수 있다.
- 가변 배열의 활용 : 버블 정렬 구현하기
<Arr.h>
void Sort(tArr* _pArr);
<Arr.cpp>
void Sort(tArr* _pArr)
{
// 데이터가 1개 이하면 정렬하지 않음
if (_pArr->iCount <= 1)
return;
while (true)
{
bool bFinish = true;
int iLoop = _pArr->iCount - 1;
// 오름차순 정렬
for (int i = 0; i < iLoop; ++i)
{
if (_pArr->pInt[i] > _pArr->pInt[i + 1])
{
int iTemp = _pArr->pInt[i];
_pArr->pInt[i] = _pArr->pInt[i + 1];
_pArr->pInt[i + 1] = iTemp;
bFinish = false;
}
}
if (bFinish)
break;
}
}
<main.cpp>
int main()
{
tArr s1 = {};
InitArr(&s1);
// 시드 값을 사용한 난수는 시드값이 달라지면 안의 출력 패턴도 변화한다.
// 단, 일일이 시드 값을 숫자로 변경하는 것이 비효율적이므로
// 여기서는 시간 값을 가져와 변화시켜주었다.
// 이렇게 하면 절대 숫자가 겹칠 일이 없다.
// 하지만 이것이 완벽한 난수 방법은 아니다.
// 3D 쉐이더에서는 이런 방식을 사용할 수 없다.
// 쉐이더에서는 동일 시간 때의 난수를 만들어야 하기 때문이다.
// 지금 이 순간 동시에 난수가 여러 개 존재할 수가 있다.
// 그런데 이런 방식으로 하면 같은 시간대에
// 다 동일한 난수가 나오기 때문에 사용이 불가능하다.
// 이처럼 어떤 상황에서는 난수가 시간 영향을 받지 않고 나와야하는 경우가 있으므로
// 난수 관련해서는 고민해야 할 부분이 많다.
srand(time(nullptr));
// 랜덤으로 보이지만 완벽한 랜덤은 아니다. (나오는 숫자가 매번 같음)
rand();
// 1~100까지의 수 중 랜덤한 수를 할당하려고 함
for (int i = 0; i < 10; i++)
{
// 반복문을 돌면서 얻은 랜덤한 숫자를 100으로 나눠 나머지 연산을 한 다음 플러스 1 하면
// 범위는 전체 숫자에 다같이 결괴에 1씩 더하므로 1부터 100사이의 값을 가지게 된다.
int iRand = rand() % 100 + 1;
PushBack(&s1, iRand);
}
// 일반 출력
printf("정렬 전\n");
for (int i = 0; i < s1.iCount; ++i) // 미리 보유하고 있는 개수만큼 반복문을 돌면서
// 데이터를 하나씩 출력한다.
{
printf("%d\n", s1.pInt[i]);
}
// Sort 함수를 이용해 정렬 한 뒤 출력
Sort(&s1);
printf("\n");
printf("정렬 후\n");
for (int i = 0; i < s1.iCount; ++i)
{
printf("%d\n", s1.pInt[i]);
}
return 0;
}