[자료구조와 알고리즘] 동적 배열 구현(size, capacity, reserve, resize)

본 내용은 <Rookiss- [C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part3: 자료구조와 알고리즘>을 토대로 작성하였습니다.

 

 

Vector 구현

 

vector - size() vs capacity()

 

size() : 실제 사용중인 데이터 갯수

capacity() : 할당된, 예약된 총 공간

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> v;

	v.reserve(100);
        cout << v.size() << " " << v.capacity() << endl;
	for (int i = 0; i < 100; i++)
	{
		v.push_back(i);
		cout << v[i]<<" "<< v.size() << " " << v.capacity() << endl;
	}

	v.clear();
	cout << v.size() << " " << v.capacity() << endl;
}

 

capacity는 용량이 꽉 찼을 때 기존의 capacity보다 1.5배정도를 증가시켜 다시 할당을 하는 증설 작업을 한다.

 

한 번 늘어난 capacity는 그대로 남는다. 근데 큰 문제는 아니라고 함

 

확실하게 몇 개의 데이터가 있어야 하는지 예측할 수 있다면 reserve 함수를 통해 충분한 양을 먼저 예약하자

reserve를 쓰면 양이 다 찰때까진 push_back을 할 때마다 capacity를 늘리는 일이 없음

 

resize() vs reserve()

 

reserve : capacity 조정

resize: size 조정. 따라서 실제 데이터 개수를 조정

 

v.resize(10);
cout << v.size() << " " << v.capacity() << endl; // 10 10 

v.reserve(100);
cout << v.size() << " " << v.capacity() << endl; //10 100

 

v.reserve(100);
cout << v.size() << " " << v.capacity() << endl; //0 100

v.resize(10);
cout << v.size() << " " << v.capacity() << endl; // 10 100

 

v.reserve(100);
cout << v.size() << " " << v.capacity() << endl;

for (int i = 0; i < 100; i++)
{
	v.push_back(i);
	cout <<  v.size() << " " << v.capacity() << endl;
}

v.resize(10);
cout << v.size() << " " << v.capacity() << endl; //10 100

 

 

코딩 시험 단골 - 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() { return _size; }
	int capacity() { return _capacity; }

	void clear()
	{
		if (_data)
		{
			delete[] _data;
			_data = new T[_capacity];
		}
		_size = 0;
	}
private:
	T*		_data = nullptr;
	int		_size = 0;
	int		_capacity = 0;
};