[Linear Data] Chapter 01. 동적 배열 구현

GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/2e1fffb765ff77ea1e260e027e2d0a23d81f7f73

동적배열(Vector) 구현 · developeSHG/Data_Structure-Algorithm@2e1fffb

 

 

---

 

 

선형 구조는 자료를 순차적으로 나열한 형태

- 배열

- 연결 리스트

- 스택 / 큐

 

비선형 구조는 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태

- 트리

- 그래프

 

---

 

배열 VS 동적 배열 VS 연결 리스트

 

{

배열 :

- 사용할 데이터를 고정해서 할당하고 (절대 변경 불가)

- 연속된 메모리를 배정받아 사용

장점 : 연속된 데이터

단점 : 메모리를 추가 / 축소 불

}

 

{

동적 배열 :

- 사용할 데이터를 유동적으로 계약

- 연속된 메모리를 배정받아 사용

 

문제점 : 데이터 이동 비용은 어떻게?

동적 배열 할당 정책 :

- 실제로 사용할 데이터보다 많이, 여유분을 두고 (대략 1.5 ~ 2배) 예약

- 이동 횟수를 최소화

 

장점 : 유동적인 계약 (데이터 여유분 추가 예약으로 이동 횟수 최소화)

단점 : 중간 삽입/삭제 (연속된 데이터로 이루어져야하기 때문에 모든 데이터를 복사해야하는 이동 문제)

}

 

{

연결 리스트 :

- 연속되지 않은 메모리를 사용

장점 : 중간 삽입/삭제 이점

단점 : N번째 데이터를 바로 찾을 수 없음 (임의 접근 Random Access 불가)

}

 

---

 

- size는 실제 사용한 데이터 개수
- capacity는 전체 데이터 용량

 

몇 개의 데이터를 사용할지 예상할 수 있다면, 초반에 충분한 양을 예약하는 게 효율적이다. (reserve)

vectdor를 clear 해서 size가 0이 돼도 capacity는 유지된다.
그러면, 데이터를 할당해서 capacity가 증가했다가 나중에 필요없게 되면 낭비가 아닐까? 생각하게 된다.
물론 낭비가 맞긴 하지만, 동적 배열의 특성상, 메모리 이사 횟수를 최소화 하는게 중요한 일이라
어느 정도의 여유분 데이터를 두어서 일부 메모리를 낭비하는 건, 사실상 메인 이슈는 아니다.

 

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

int main()
{
	Vector<int> v;

	v.reserve(100); // 몇 개의 데이터를 사용할지 예상할 수 있다면, 초반에 충분한 양을 예약하는 게 효율적이다.

	// size는 실제 사용한 데이터 개수
	// capacity는 전체 데이터 용량
	cout << v.size() << " " << v.capacity() << endl;

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

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

	// clear를 해서 size가 0이 돼도 capacity는 유지된다.
	// 그러면, 데이터를 할당해서 capacity가 증가했다가 나중에 필요없게 되면 낭비가 아닐까? 생각하게 된다.
	// 물론 낭비가 맞긴 하지만, 동적 배열의 특성상, 메모리 이사 횟수를 최소화 하는게 중요한 일이라
	// 어느 정도의 여유분 데이터를 두어서 일부 메모리를 낭비하는 건, 사실상 메인 이슈는 아니다.
}