2. 동적배열 구현

Q1. vector를 구현해 보는 이유는 무엇인가요?

 

A1.

첫번째 이유 : 나머지 자료구조 학습하는데 기초가 되기 때문에

두번쨰 이유 : 코딩 테스트에 가끔 나오기 때문

 

 

Q2. vector 의 특징을 size와 capacity의 관점에서 말해 보세요

 

A2. size는 실제 원소의 개수고, capacity는 할당된 데이터의 크기다. size가 capacity의 양만큼 늘어나면 1.5배로 capacity를 증량하고, 기존의 데이터를 증량한 capacity로 옮긴다. 

데이터를 삭제해서 size가 0이 되어도 capacity의 수는 변하지 않는다. 

 

 

Q3. vector를 구현해보세요.

(생성자, 소멸자, push_back, reserve, operator[], size, capacity, clear만 제한적으로)

 

A3. 

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

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) // 만약 처음 _capacity가 0같은 숫자면 1.5배여도 _capacity랑 같을거야. 
				newCapacity++;			  // 그럴 경우 1을 증가해준다.

			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]; // T타입에 따라 소멸자를 호출해 줘야해. 지금은 간단하게 하기 위해한거야. 원래는 malloc이라거나 사용해서 소멸자, 생성자 사용해야 한다. 서버 시간에 다뤘음. 
		}

		_size = 0; 
	}

private: 
	T*		_data = nullptr;	// 갖고 있는 데이터 배열
	int		_size = 0;			// 사용중인 데이터 개수
	int		_capacity = 0;		// 할당 받은 데이터 크기
};

int main()
{
	Vector<int> v; 

	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;

}