[C++] 가변 배열 구현

꿈별·2023년 5월 9일
cpp
0

C++

목록 보기
16/27

✔가변 배열

  • 배열 크기를 선언할 때에는 변수를 사용할 수 없다.
  • 함수의 지역 변수들은 함수 호출 시에 스택 메모리가 할당된다.
    그런데 배열의 크기를 변수로 설정하면 코드가 실행되기 전까지 변수의 값을 확신할 수 없기 때문에 컴파일러가 메모리 크기를 파악하여 할당할 수가 없다.

-> 가변 배열은 지역 변수로 만들 수 없다.
👉 가변 배열은 힙 메모리 영역을 이용해 만들 수 있다.

  • 구조체 는 될까?
    : 사용자가 만든 자료형이라는 특징을 제외하고는 일반적인 자료형이랑 똑같기 때문에, 규칙이 그대로 적용되어서 배열 크기 선언에 변수를 사용할 수 없다.

  • 객체(Instance)
    : 구조체의 실질적인 데이터를 말한다.
    (자료형이라는 틀로 찍어낸 결과물이 객체)

int a;

-> a : 객체


malloc을 활용한 가변 배열 구현

  • 가변 배열 역할을 할 자료형을 선언하고, 객체를 생성하면 가변 배열을 만들 수 있다.
    • ❗But 각 객체에 직접 데이터를 넣으면 가변 배열로 사용할 수 없다.
      -> 지정된 배열 크기 이상의 데이터를 저장할 수 없음.
    • 따라서 객체가 사용할 힙 메모리 주소를 받아와서 그 공간에 데이터를 저장해야 한다.

창고 주인 <-> 창고
배열 객체 <-> 힙 메모리
: 창고 주인은 물건(데이터)을 받아 창고에 저장한다.


예시

  • 크기가 100인 배열 arr은 크기 100 이상의 데이터를 저장할 수 없다.
    : 이렇게 제한적으로 사용해야 한다면 굳이 자료형을 선언해서 배열을 만들 이유가 없다.
typedef struct _tagArr
{
	int arr[100];
}tArr;

tArr s;
for (int i = 0; i < 100; ++i)
{
	s.arr[0] = i;
}

👉 동적 할당이 가능한 힙 메모리를 사용해야 함.

구현

  • 3가지의 멤버를 가져야 한다.
    1. 메모리 시작 주소
    2. 데이터 *개수
    3. 데이터 최대치
typedef struct _tagArr
{
	int* pInt;		//메모리 주소
    int iCount;		//데이터 개수
    int iMaxCount;  //최대치
}

1) 메모리 시작 주소

  • 힙 메모리의 시작 주소를 전달받는다.

2) 데이터 개수

  • 데이터를 저장할 위치를 어떻게 알 수 있을까?
    (이미 저장되어 있는 데이터에 따라 새로 저장할 위치가 달라진다.)
    -> 지금까지 들어온 데이터 수를 기록해놔야 알 수 있다.

3) 데이터 최대치

  • 메모리가 최대치보다 초과될 경우 늘려줘야 한다.
    • 그러려면 현재 메모리 공간에 든 데이터 개수를 아는 상태에서, 메모리를 늘려줘야 한다는 것을 인식해야 함.
      -> iCount 와 iMaxCount 가 같아질 때가 그 타이밍.

객체 생성할 때마다 일일이 초기화하기가 번거롭다.

tArr s;
s.pInt = (int*)malloc(40);
s.iCount = 0;
s.iMaxCount = 10;

-> 초기화 함수를 만들자.


1) 배열 초기화 함수

  • 반환받을 필요가 없으므로 void형
  • InitArr(s); 처럼 객체를 그대로 넘긴다고 초기화 되지 않음.
    -> 객체가 main 함수의 지역 안에 있으면 함수가 객체로 접근할 수 없다.
    따라서 객체의 주소를 넘겨줘야 한다.
  • 8byte 메모리 생성하여 int형 데이터 2개를 넣을 것이므로 sizeof 활용
    -> 컴파일러에겐 똑같이 8byte로 인식되겠지만, 사용자가 의도를 파악하기가 쉽다.

선언

void InitArr(tArr* _pArr);

정의

void InitArr(tArr* _pArr)
{
	_pArr->pInt = (int*)malloc(sizeof(int) * 2);
	_pArr->iCount = 0;
	_pArr->iMaxCount = 2;
}

2) 배열 메모리 해제 함수

  • 가변배열 객체는 지역변수이므로 함수가 종료될 때 자동 해제된다.
    -> But 객체의 실질적인 데이터를 저장하는 힙 메모리는 그대로 남아 있음.
    -> 메모리 누수 발생
    👉 함수 종료 전에 메모리 해제 요청하기

선언

void ReleaseArr(tArr* _pArr);

정의

void ReleaseArr(tArr* _pArr)
{
	free(_pArr->pInt);
	_pArr->iCount = 0;
	_pArr->iMaxCount = 0;
}

-> free(_pArr->pInt); 이후, 가리키던 힙 공간이 해제되어서 객체가 텅 비었다. 따라서 데이터 한계치, 최대치 모두 0이 됨

3) 데이터 추가 함수

  • 순서 )
    1. 먼저, 메모리 늘려줘야 하는 상태인지 체크하기
      (한계치(현재 데이터 개수)와 최대치가 같은지 체크)
    2. 0번에서 할당했던 힙 메모리 공간이 다 찼다면, 재할당하기
    3. 메모리가 여유있는 상태가 되었을 때,
      가변배열의 인덱스로 접근해 데이터를 추가한다. 이 때 인덱스는 데이터 한계치이며, 데이터를 추가해준 뒤 한계치를 1 증가시킨다.

선언

void PushBack(tArr* _pArr, int _iData);

정의

void PushBack(tArr* _pArr, int _iData)
{
	//힙 영역에 할당한 공간이 다 찬 경우
	if (_pArr->iMaxCount <= _pArr->iCount)
	{
		//재할당
		Reallocate(_pArr);
	}
	//데이터 추가한 뒤, 후위 연산자로 한계치 1 증가
	_pArr->pInt[_pArr->iCount++] = _iData;
}

4) 메모리 재할당 함수

  • malloc()으로 메모리를 동적할당 받을 때, 원하는 위치의 주소를 할당받을 수는 없었다.

  • 할당받은 공간 이외의 공간을 침범하면 문제가 발생할 수 있다.
    (힙손상 오류 등)
    -> 가변배열의 공간이 부족할 때, 메모리 확장은 어떻게 가능할까?
    👉 만약 int형 2칸(8byte)을 사용하는데, 2칸이 더 필요하다면 2칸을 뒤에 이어붙이는 게 아니라, 한꺼번에 4칸을 새로 할당받아야 한다.
    +💡 처음에 동적할당 받을 때 충분히 넉넉한 공간을 할당하는 게 좋음.

  • 순서 )

    1. malloc()으로 2배 더 큰 공간을 동적 할당한다. 이 때 리턴되는 공간 주소를 지역변수로 받는다.
    2. 기존 공간에 있던 데이터들을 새로 할당한 공간으로 복사한다.
    3. 기존 공간은 메모리 해제해 준다.
    4. 가변 배열이 새로 할당한 공간을 가리키게 한다.
    5. MaxCount 변경점을 적용한다.(최대치 2배 커짐)

선언

void Reallocate(tArr* _pArr);

정의

void Reallocate(tArr* _pArr)
{
	//간단하게 2배씩 늘려서 재할당해보기

	int* pNew = (int*)malloc(_pArr->iMaxCount * 2 * sizeof(int));
    
    // 기존 공간 -> 새로운 공간 으로 데이터 복사
	for (int i = 0; i < _pArr->iCount; ++i)
	{
		pNew[i] = _pArr->pInt[i];
	}
	free(_pArr->pInt);
	_pArr->pInt = pNew;
	_pArr->iMaxCount *= 2;
}

-> 가변배열 객체의 pInt 멤버로 새로 할당한 주소를 넣으면 기존에 있던 메모리 주소는 알 수 없게 되어버리는 문제가 생긴다.


💡 추가

  • 재할당 함수는 메모리 공간이 부족할 때 할당하려고 만든 함순데, 헤더 파일에 선언해 두면 메모리 공간이 부족한 게 아닐 때도 main 쪽에서 호출하는 것이 가능하다.

-> 방지하려면?
: 헤더 파일에 선언해 두지 않는다. 어차피 가변배열 cpp 파일 안에 구현이 되어 있으므로 문법적으로 문제 없다.

최종 코드

//[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);
	_pArr->iCount = 0;
	_pArr->iMaxCount = 2;
}

void ReleaseArr(tArr* _pArr)
{
	free(_pArr->pInt);
	_pArr->iCount = 0;
	_pArr->iMaxCount = 0;
}

//메모리 재할당
void Reallocate(tArr* _pArr)
{
	//간단하게 2배씩 늘려서 재할당해보기

	int* pNew = (int*)malloc(_pArr->iMaxCount * 2 * sizeof(int));

	// 기존 공간 -> 새로운 공간 으로 데이터 복사
	for (int i = 0; i < _pArr->iCount; ++i)
	{
		pNew[i] = _pArr->pInt[i];
	}
	free(_pArr->pInt);
	_pArr->pInt = pNew;
	_pArr->iMaxCount *= 2;
}


void PushBack(tArr* _pArr, int _iData)
{
	if (_pArr->iMaxCount <= _pArr->iCount)
	{
		//메모리 재할당
		Reallocate(_pArr);
	}
	_pArr->pInt[_pArr->iCount++] = _iData;
}

//[main.cpp]
#include <iostream>
#include "Arr.h"

int main()
{
	tArr s = {};
	InitArr(&s);

	for (int i = 0; i < 10; ++i)
	{
		PushBack(&s, i);
	}

	for (int i = 0; i < s.iCount; ++i)
	{
		printf("%d\n", s.pInt[i]);
	}

	ReleaseArr(&s);

	return 0;
}
[출력]
0
1
2
3
4
5
6
7
8
9

과제 - 가변 배열 데이터 버블 정렬

  • 가변 배열의 데이터를 버블 정렬을 사용해 정렬하는 동작을 구현할 것

    • 오름차순으로 정렬

구현 

void BubbleSort(tArr* _pArr)
{
	while (true)
	{
		bool bFinish = true;
		for (int i = 0; i < _pArr->iCount-1; i++)
		{
			//왼쪽 요소가 오른쪽 요소보다 크면 서로 교환
			if (_pArr->pInt[i] > _pArr->pInt[i + 1])
			{
				int temp = _pArr->pInt[i];
				_pArr->pInt[i] = _pArr->pInt[i + 1];
				_pArr->pInt[i + 1] = temp;

				bFinish = false;
			}
		}
        //for문 마친 후, 왼쪽 요소가 오른쪽 요소보다 크지 않은 상태면 break
		if (bFinish)
			break;
	}
}

-> for (int j = 0; j < _pArr->iCount-1-i; j++)
: 버블 정렬 할 때마다 데이터 개수-1 만큼 비교하기 때문에 j < _pArr->iCount-1-i;


  • 난수 함수 rand(), srand()
    헤더 : <time.h>
    • rand() : 난수 페이지 참조, but 페이지 순서를 따르기 때문에 완벽한 난수가 아님
    • srand() : 여러 난수 페이지를 참조, rand()보단 보완됨
    • 난수 값 범위 지정 방법 :원하는 범위만큼 나머지 연산
      ex) 1~100 원하면 %100한 후 1 더하기
      rand() 활용하여 구현
      함수 구현
      위에 있는 코드와 동일

main.cpp

#include <iostream>
#include "Arr.h"
#include <time.h>

int main()
{
	tArr s = {};
	InitArr(&s);


	for (int i = 0; i < 10; ++i)
	{
		int iRand = rand() % 100 + 1;
		PushBack(&s, iRand);
	}

	printf("정렬 전\n");
	for (int i = 0; i < s.iCount;++ i)
	{
		printf("%d\n", s.pInt[i]);
	}

	printf("\n정렬 후\n");

	BubbleSort(&s);

	for (int i = 0; i < s.iCount; ++i)
	{
		printf("%d\n", s.pInt[i]);
	}

	ReleaseArr(&s);

	return 0;
}

출력


💡 팁

  • 함수 바로 정의할 수 있는 단축키 Ctrl + + + .
  • srand() 함수
  • (과제)삽입/선택/합병/쾌속/힙 정렬 구현해 보기

[참고]
https://youtu.be/osL_ngXRmA4
https://youtu.be/UV30FZqQsAM
https://syrang.tistory.com/51

profile
꿈별
이전 포스트

[C++] 동적 할당 (new/delete 추가하기)

다음 포스트

[C++] 연결 리스트

0개의 댓글