자료구조 : C++ 가변배열(Dynamic Array), 배열 동적할당 하기

가변배열은 흔히 C#이나 JAVA와 같은 언어에서만 사용하는데, C++에서도 구현할 수 있습니다. 

오늘은 가변배열이 무엇인지, 어떻게 사용할 수 있는지 알아보고 풀 소스까지 공개하겠습니다. 

가변배열(Dynamic Array)

int array[num];
//또는
int a[] = new input[num];

C나 C++에서는 위와같이 배열의 크기를 사용자로부터 입력받는 코드는 작성할 수 없습니다. 그런데 우리는 배열을 생성할때 몇개의 방을 만들어야 할지 잘 모르지요. 가장 간단한 방법은

int array[1000];

이와같이 무식하게 큰 크기의 배열을 정적으로 만드는것. 그러나 만약 1000개 중에 10개 20개만 사용이 된다면, 나머지 900개가 넘는 메모리들은 전부 버려지는 것이 됩니다. 그렇기 때문에 꼭 필요한 만큼만, 혹은 입력되는 데이터보다 약간 큰 정도로 배열을 만드는것이 좋은데, 앞서 이야기 했듯이 C#이나 JAVA에서는 기본적인 문법으로 이를 제공 하나, C, C++에서는 불가능 하기 때문에 임의의 클래스로 생성해야 합니다.

class dynamicArray
{
private:
    int* m_array;
    int m_size;
    int m_used;
public:
    dynamicArray();
    dynamicArray(int size);
    ~dynamicArray();
 
    void popBack();
    void pushBack(int data);
    void print();
    int &operator[](int index);
};

클래스의 헤더입니다. 순서대로 설명할테니 잘 따라 오시기 바랍니다.

멤버 변수부터 차례로 보겠습니다. 배열을 동적 할당할 int의 포인터형 m_array, m_array의 size를 저장할 m_size, 그리고 몇번째 방까지 사용중인지 표시할 m_used 세개의 멤버 변수가 선언되었습니다.

멤버 함수에는 기본적으로 생성자와 소멸자가 있구요, 배열의 마지막 데이터를 지워줄 popBack(), 그리고 배열에 데이터를 추가하는 pushBack(), 배열에 있는 데이터를 모두 출력 해줄 Print(), 그리고 클래스를 배열처럼 사용하기 위하여 [] 연산자를 연산자 오버로딩을 통하여 선언하였습니다.

연산자 오버로딩에 대한 지식이 없으신 분은 아래 글을 참고 하시기 바랍니다.

C++ : 연산자 오버로딩(Operator overloading) : http://andrew0409.tistory.com/147

이제 함수 하나하나를 정의해보도록 하겠습니다.

dynamicArray::dynamicArray() : m_size(1), m_used(0)
{
    m_array = new int[m_size];
}
 
dynamicArray::dynamicArray(int size) : m_size(size), m_used(0)
{
    m_array = new int[m_size];
}
 
dynamicArray::~dynamicArray() 
{
    delete[] m_array;
}

생성자와 소멸자에 대한 정의부터 살펴보겠습니다.

초기화에 있어서는 콜론 초기화를 사용하였습니다. 콜론 초기화는 이후 별도의 포스팅으로 정리하여 올리도록 하겠습니다.

인자가 아무것도 들어있지 않은 디폴트 생성자부터 보시겠습니다.

m_size는 1로, m_used는 0으로 초기화 시켜줍니다. 디폴트 생성자의 장점은 별도로 인수를 지정하지 않더라도, 일괄된 값으로 생성을 보장해준다는 장점이 있습니다.

추후에 생성, 소멸자에 관해서도 별도의 포스팅으로 정리해서 올리겠습니다.

배열의 경우 콜론 초기화를 이용하여 초기화를 할 수 없습니다. 그래서 내부에 별도로 정의했는데, 정수값의 주소를 가리키도록 선언된 m_array에 new int[m_size]라고 입력했습니다. 해석하자면 m_array가 int형 방을 가지며 m_size만큼 가지겠다는 뜻 입니다.

new는 메모리를 할당하는 함수이며, C 에서 비슷한 함수로 malloc()이 있습니다. 추가적으로 new로 메모리를 할당했으면 해당 메모리가 필요 없어진 시점에서 delete를 해 주어야 합니다. 그렇지 않으면 메모리 누수(Memory leak)이 발생하여 나도 모르는 새에 프로그램이 터지게 되기 때문에 C/C++ 코딩에서는 필수적인 사항입니다. 여담이지만 JAVA에서는 GC라고 불리우는 가비지 콜렉터가 자동으로 사용하지 않는 메모리를 해제해 줍니다. 그렇기 때문에 JAVA에서 C로 전향한 개발자들이 많이 하는 실수가 메모리를 해제하지 않는 것이죠.

다음으로 인자가 있는 생성자의 경우 size를 전달인자로 받게 되는데, 이 size만큼 m_array의 크기를 할당해 줍니다. 나머지는 기본 생성자와 동일합니다.

소멸자는 클래스가 소멸할때 실행이 되는 함수입니다. 앞서 말씀드렸듯이 사용이 끝난 메모리는 반드시 해제를 해야 합니다. new는 delete로 new []는 delete[]로 해제하면 됩니다. 소멸자에서는 delete함수를 이용하여 할당되었던 메모리를 돌려보냅니다.

다음으로 pushBack 함수에 대해 알아보겠습니다.

void dynamicArray::pushBack(int data)
{
    if(this->m_used < this->m_size)
    {
        this->m_array[this->m_used] = data;
    }
    //메모리가 있으면
    else
    {
        int* temp = new int[m_size];
        for(int i=0; i<this->m_used; i++)
            temp[i] = this->m_array[i];
 
        delete[] this->m_array;
        this->m_size *= 2;
        this->m_array = new int[m_size];
        
        //this->m_array = temp;
        for(int i=0;  i<this->m_used;  i++)
        {
            this->m_array[i] = temp[i];
        }
        delete[] temp;
        this->m_array[this->m_used] = data;
    }
 
    this->m_used++;
    //메모리가 없으면(더이상 넣을 공간이 없으면 확장)
}

int 형의 data를 전달인자로 받습니다. 이때 가장 먼저 이 data를 배열에 추가하기 위해 배열에 빈 방이 있는지 확인합니다.

m_size가 배열의 방 갯수, m_used가 사용중인 방의 갯수라고 했으니 m_used가 m_size보다 작으면 빈방이 있는 것이겠죠, 그럼 m_array의 마지막 방의 인덱스인 m_used번 방에 data를 넣고 m_used를 1 증가시킨채로 리턴하고 종료합니다. 간단하죠

그러나 이렇게 데이터를 추가시키다 보면 메모리가 가득차서 더이상 넣을 수 없을때 즉, m_used가 m_size보다 같거나 클때가 올 것입니다. 이때 else문으로 빠지게 됩니다. 한번 살펴보도록 하지요. 가장먼저 int* temp 를 선언과 동시에 초기화 했는데, m_array와 똑같은 방의 갯수를 가진 배열을 한개 더 선언한 것입니다.

그리고 for문을 통하여 m_array의 데이터를 모두 temp배열에 복사하게 되죠.

다음으로 지금까지 사용하던 m_array의 메모리를 과감하게 해제해 줍니다. 왜냐하면 작은집을 무너뜨리고 큰 집을 짓듯이 더 크게 지을거니까....

m_size의 크기를 2배로 늘려줍니다. 그리고 m_array에 새 집을 짓습니다.

메모리 할당을 집짓기에 비유했는데, 이미 해당 자리에 집이 지어져있으면 새 집을 지을 수 없듯이 메모리가 할당된곳에 다시 메모리를 할당할 수 없습니다. 반드시 해제하고 해야 합니다.

그리고 다시 for문을 통해서 temp배열에 있던 데이터들을 m_array로 옮겨줍니다. 그리고 temp배열을 해제하고 마지막방에 data를 넣은다음, m_used를 하나 증가시키면 끝.

공간이 부족하다 -> 데이터를 임시배열에 복사한다 -> 배열을 없에고 더 큰 배열을 만든다 -> 임시배열에서 다시 복사한다 순의 진행이 되겠습니다.

popBack 함수도 살펴보도록 하겠습니다.

void dynamicArray::popBack()
{
    if (m_used == 0) return;
 
    m_used--;
    int* temp = new int[m_used];
 
    for (int i = 0; i < m_used; i++)
        temp[i] = m_array[i];
 
    delete[] m_array;
    m_array = new int[m_size];
 
    for (int i = 0; i < m_used; i++)
        temp[i] = m_array[i];
 
    delete[] temp;
    return;
}

pushBack 함수의 흐름을 잘 따라 오셨다면 popBack도 이해하기 쉬울것이라 생각합니다.

가장 먼저 예외처리를 해야죠 m_used가 0이면 데이터가 아무것도 들어있지 않은 배열이기 때문에 return 합니다.

일단 m_used를 1 줄여줍니다.

그리고 푸시백에서와 마찬가지로 temp 임시 배열을 만들어주고, m_array의 데이터를 복사해줍니다. 앞서 m_used를 1 줄인 이유는 마지막 방은 복사하지 않기 위해서 1을 줄이고 m_used만큼 복사했습니다.

아래는 푸시백과 마찬가지로 새로 만들어서 옮기고 임시배열을 지우는 순입니다. 이해가 잘 되셨나요?

int dynamicArray::operator[](int index)
{
    return this->m_array[index];
}

마지막으로 연산자 오버로딩 함수입니다. 위와 같이 작성하시면 main 함수에서 int num = array[5]; 이런식으로 작성했을때 해당 배열의 5번 인덱스에 적힌 값을 리턴하게 됩니다.

아래는 전체 소스코드 올려드리겠습니다.

<dynamicArray.h>

#pragma once
#include <stdio.h>
class dynamicArray
{
private:
    int* m_array;
    int m_size;
    int m_used;
public:
    dynamicArray();
    dynamicArray(int size);
    ~dynamicArray();
 
    void popBack();
    void pushBack(int data);
    void print();
    int &operator[](int index);
};

<dynamicArray.cpp>

#include "dynamicArray.h"
 
 
dynamicArray::dynamicArray() : m_size(1), m_used(0)
{
    m_array = new int[m_size];
}
 
dynamicArray::dynamicArray(int size) : m_size(size), m_used(0)
{
    m_array = new int[m_size];
}
 
dynamicArray::~dynamicArray() 
{
    delete[] m_array;
}
 
 
void dynamicArray::popBack()
{
    if (m_used == 0) return;
 
    m_used--;
    int* temp = new int[m_used];
 
    for (int i = 0; i < m_used; i++)
        temp[i] = m_array[i];
 
    delete[] m_array;
    m_array = new int[m_size];
 
    for (int i = 0; i < m_used; i++)
        temp[i] = m_array[i];
 
    delete[] temp;
    return;
}
 
void dynamicArray::pushBack(int data)
{
    if (m_size > m_used)
    {
        m_array[m_used] = data;
        m_used++;
        return;
    }
 
    int* temp = new int[m_size];
 
    for (int i = 0; i < m_used; i++)
        temp[i] = m_array[i];
 
    delete[] m_array;
 
    m_size *= 2;
 
    m_array = new int[m_size];
    
    for (int i = 0; i < m_used; i++)
        m_array[i] = temp[i];
 
    m_array[m_used] = data;
    m_used++;
 
    delete[] temp;
 
    return;
}
 
void dynamicArray::print()
{
    for(int i=0; i<this->m_used; i++)
        printf("%d ",this->m_array[i]);
    printf("\n");
}
 
int& dynamicArray::operator[](int index)
{
    return this->m_array[index];
}

질문은 댓글로 받습니다. 추가적으로 도움이 되셨다면 본문에 붙어있는 광고를 한번씩 클릭해주시면, 콘텐츠 제작에 큰 힘이 됩니다.