선형 구조 자료 - 배열 , 동적 배열

 배열이란 같은 자료형을 가진 자료들을 연속되게 공간을 배정받아 저장하는 것을 말한다. 배열은 사용할 공간을 고정값으로 가지고 있기 때문에 공간의 크기에 대한 변경은 불가하다. 

 

 배열은 앞서 언급한 것과 마찬가지로 원소들끼리 연속된다는 특징이 있다. 그러므로 사용자가 원하는 위치(인덱스)에 있는 원소값에 대한 접근이 빠르다는 장점을 가지고 있다. 그러나 삽입/삭제와 같은 기능에 제약이 생긴다.

 

 그래서 사용하는 것이 바로 동적 배열이다. 동적 배열은 배열의 개념을 이용하지만 조금더 유동적으로 배열을 사용할 수 있게 해준다. 기존 배열과는 다르게 사용할 방의 개수를 유동적으로 가지고, 삽입/삭제의 기능 또한 사용할 수 있게 된다. 하지만 이를 위해서는 반드시 공간에 대해 재할당의 과정을 거쳐야한다. 하나의 원소를 추가할 때 마다 재할당을 거쳐야 한다면 상당한 비효율적인 방식일 것이다. 그러므로 실제로 사용하는 공간보다 여유분을 두어 공간을 할당 받는다. 이 것이 바로 할당된 공간(Capacity)와 사용중인 공간(size)의 차이점이다. 이 개념은 분명히 해두는 것이 좋다.

 

아래는 C++에서 제공하는 vector 알고리즘의 몇몇 기능을 구현한 코드이다.

template<typename T>
class Vector
{
public:
	Vector()
	{
		
	}

	~Vector()
	{
		if (_data)
			delete[] _data;
	}

	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;
	}

	T& operator[](const int pos) { return _data[pos]; }
	int size() const { return _size; }
	int capacity() const { return _capacity; }
	
	void clear()
	{
		if (_data)
		{
			delete[] _data;
			_data = new T[_capacity];
		}

		_size = 0;
	}

public:
	T* _data		= nullptr;
	int _size		= 0;
	int _capacity	= 0;

};

동적 배열을 만들게 되면, capcity와 size를 각각 따로 가지게 되며, 해당 값은 배열에 원소들이 추가되면서 변경된다. size가 capacity보다 커지게 되는 순간, capacity를 늘려서 동적 배열의 할당된 공간의 크기를 늘리고, 해당 크기가 다시 가득 찰 때까지 size의 크기를 늘려가며 원소를 채우게 되는 것이다. vector 컨테이너에서 제공하는 clear는 vector의 원소들을 지우는데에 많이 사용하지만, 사실 할당된 공간 자체를 사라지게 하는 것이 아니기 때문에 이를 유의하여야 한다. 

 

 

이렇게 배열 및 동적 배열에 대한 소개를 마치도록 하겠습니다. 포바~!