Dynamic array

정적 배열의 진화 버전, 동적 배열에 대해 공부해보자.

 

그 전에 정적 배열과 다르게 동적 배열에서는 반드시 구현해줘야 하는 기능이 있다.

바로, destructor, copy constructor, 그리고 overloaded assignment operator 이다.

왜냐하면(destructor 구현의 이유), 정적 할당을 하는 경우에는 런타임 중 함수 실행 순간에 stack 공간에 메모리 공간이 할당되고,

함수 종료시 자동으로 메모리 공간이 해제가 되는데, 

동적 할당의 경우에는 런타임 중 new(c++) 또는 malloc(c) 와 같은 키워드로 인해 중간에 메모리 공간이 할당이 되는데,

개발자가 delete 또는 free와 같은 명령어로 해제해 주지 않으면, 프로세스 종료시까지 메모리공간이 살아있기 때문에,

메모리 누수의 문제가 생기기 때문이다.

따라서 개발자는 동적 배열 할당시 destructor 기능을 필수적으로 구현하여 메모리 공간에 대한 책임(?)을 져야 한다.

 

또한, bag b1(b2) 나, bag b1 = b2 같이 동일한 객체를 만들거나,

bag operator+(const bag &b1, const bag &b2); 같이 객체를 반환하거나,

void operator+=(const bag &eddend); 같이 객체를 인자로 넘겨주는 경우

c++에서는 내부적으로 copy constructor을 호출하게 된다.

뿐만 아니라, 동적으로 배열을 복사하여 생성하는 경우 개발자는 객체를 다른 객체에게 정확히 복사해줘야 하는 책임이 있다.

따라서 copy constructor, overloaded assignment operator을 필수적으로 구현해야 한다.

 

이번 포스트의 구현은 아래의 클래스의 헤더 파일 중 일부를 기준으로 구현하겠습니다.

class bag {
    public:
        bag(size_t init_capacity = 20); // constructor
        bag(const bag &source); // copy constructor
        ~bag(); // destructor

        bag &operator=(const bag &source); //= (assingment oparator) overloading
        ...
    private:
        value_type *data; // member variable: data container
        size_t capacity; // member variable: max qty of data
        size_t used; // member variable: counting data qty
};

 

 

따라서 먼저 Constructor와 Destructor를 구현해보자.

// Constructor
bag::bag(size_t init_capacity) {
    data = new value_type[init_capacity];
    capacity = init_capacity;
    used = 0;
}

// Destructor
bag::~bag() {
    delete[] data;
}

생성자에서는 data 포인터에 새로운 메모리 공간을 할당하여 주소값을 넣어준다.

반대로 파괴자에서는 data에 저장된 할당 받은 메모리 공간을 해제해준다.

 

이 파괴자 함수에서 객체의 동적 메모리 해제에 대한 책임을 지는 것이다.

 

 

다음은 Copy constructor 와 Assignment operator overloading을 구현해보자.

// Copy constructor
bag::bag(const bag& source) {
    data = new value_type[source.capacity];
    capacity = source.capacity;
    used = source.used;

    copy(source.data, source.data + used, data);
}

// Assignment operator overloading
bag& bag::operator=(const bag& source) {
    if (this == &source) {
        return *this;
    }
    if (capacity != source.capacity) {
        delete[] data;
        data = new value_type[source.capacity];
        capacity = source.capacity;
    }

    used = source.used;
    copy(source.data, source.data + used, data);

    return *this;
}

복제 생성자 에서는 생성자와 마찬가지로 동적 메모리 할당을 통해 새로운 객체를 만들어준다.

차이점은 배열의 생성 초기값을 인자로 받은 bag 클래스의 객체 데이터를 받아 초기화 한다는 것이다.

대입 연산자 오버로딩에서는 기존의 가방(왼쪽의 피연산자)을 인자로 받은 가방(오른쪽 피연산자)로 데이터를 덮어씌우는 기능을 수행한다.

이 때 왼쪽, 오른쪽에 같은 가방 객체가 들어올 경우 바로 *this를 리턴하여 기능을 수행하지 않도록 하고,

다른 경우 가방의 최대 크기를 맞춰준 후, 데이터를 복사하여 *this를 리턴한다.

*this, 즉 가방 객체를 리턴하기 때문에 b1 = b2 = b3 같은 연속된 연산도 처리할 수 있다.

 

참고로 리턴 타입이 bag가 아닌 bag & 인 이유는 데이터 전달의 효율 때문이다.

bag 사용시 데이터를 복사하게 되므로, 효율이 떨어진다.

하지만, bag & 사용시 변수 자체를 넘겨주기 때문에(c++ 내부에서 포인터로 구현됨) 전달 효율이 높다.

(마치 reference parameter와 같은 원리)

 

이 복사하는 기능을 구현하여 동적 메모리를 할당하는 과정에서 객체의 복사를 올바르게 할 수 있도록 책임을 지는 것이다.

 

 

다음은 정적 배열과 비교되는 동적 배열의 기능인 reserve 기능을 구현해보자.

void bag::reserve(size_t new_capacity) {
    value_type *larger_array;
    if (new_capacity == capacity) {
        return;
    }
    if (new_capacity < used) {
        new_capacity = used;
    }

    larger_array = new value_type[new_capacity];
    copy(data, data + used, larger_array);
    delete[] data;
    data = larger_array;
    capacity = new_capacity;
}

이 함수를 통해서 배열의 사이즈를 늘리거나 줄일 수 있게 되는데,

늘리고자 하는 사이즈가 이미 배열의 사이즈와 같다면 별다른 기능을 수행하지 않고 바로 리턴한다.

늘리고자 하는 사이즈가 이미 배열에 저장된 데이터의 양보다 적다면, 최소한 데이터의 양 만큼 공간을 할당할 수 있도록 한다.

 

그 이후에는 새로운 크기로 배열을 동적 할당하여 copy로 기존 데이터를 복사하고,

기존의 공간은 delete로 해제해주는 과정을 거치게 된다.

 

 

다음은 배열에 데이터를 추가하는 함수를 구현해보자.

void bag::insert(const value_type& new_entry) {
    if (used == capacity) {
        if (used == 1) {
            reserve(2);
        else {
            reserve(used * used);
        }
    }

    data[used++] = new_entry;
}

기존의 정적 배열과의 차이점은 공간이 꽉 찼을 때, assert로 에러를 출력하는 것이 아닌,

reserve함수로 배열의 크기를 동적으로 늘려주고, 데이터를 추가한다는 것이다.

 

 

마지막으로 두 가방을 합쳐주는 + operator overloading을 구현해보자.

bag operator+(const bag& a, const bag& b) {
    bag answer(a.size() + b.size());

    answer += a;
    answer += b;
    return answer;
}

앞서 봤던 operator overloading과 다르게 이 연산자 오버로딩은 클래스 밖에서 선언 및 구현되었다.

하지만, 앞서 봤던 연산자 오버로딩과 동일한 기능을 수행할 수 있다.

 

 

동적 배열은 앞서 봤던 정적 배열보다는 확실히 매력적이다.

하지만, 배열의 크기를 늘리는 과정에서 기존 배열에서 새로운 배열로 데이터를 복사하는 과정은

프로그램 성능에 영향을 끼칠 수 밖에 없다.

 

만약 1억개가 넘은 데이터를 복사한다면?

아마 수 초 동안은 컴퓨터가 정지할지도 모른다.

 

다음에 배울 자료구조, linked list는 이러한 문제를 해결할 수 있는 자료구조 이다.