동적 배열

동적 배열 (vector)

• 동적 배열은 원소가 추가됨에 따라 capacity를 적절하게 늘려주어 메모리 공간을 예약하는 방법을 사용한다.

• 일반 배열이 메모리를 축소, 추가하지 못하는 점을 개선하기 위함.

    void push_back(const T& value)
    {
        if (_size == _capacity)
        {
            // 증설 작업
            int newCapacity = static_cast<int>(_capacity * 1.5);
            if (newCapacity == _capacity)
                newCapacity++;

            reserve(newCapacity);
        }
        // 데이터 저장
        _data[_size] = value;

        // 데이터 개수 증가
        _size++;
    }
    
    void reserve(int capacity)
    {
        if (_capacity >= capacity)
            return;

        _capacity = capacity;

        T* newData = new T[_capacity];

        // 데이터 복사
        for (int i = 0;i < _size;i++)
            newData[i] = _data[i];

        if (_data)
            delete[] _data;
        _data = newData;
    }

• 현재 vector의 size와 capacity를 비교하여 둘이 같다면 vector가 꽉 차있다고 간주하고 메모리를 증설하여 예약을 받는다.

• 메모리 증설은 capacity의 1.5배 크기의 새로운 메모리를 할당받는 식으로 동작되는데, 이 때 새로운 메모리에 기존 메모리의 원소들을 옮겨줘야 하므로 추가적인 연산이 요구된다.