[C++/자료구조] vector에 대해서

* 벡터에 대해 나름 정리해봤습니다!
수정이 필요할 시 댓글 주세요!

vector 란?

• 시퀀스 컨테이너에 대한 클래스 템플릿
• 동적 선형 배열 저장
• 빠른 임의 액세스 가능 (O(1))
• 중간 삽입/삭제 느림 (O(N))
• 시퀀스(size)가 현재 스토리지 용량(capacity)보다 더 크게 늘려야 할 때 벡터는 다시 할당을 수행 → 시퀀스 내의 여러 스토리지 주소가 변경될 수 있음 (메모리 이사)

• .capacity() / .size()
• 데이터 복사에 대한 비용을 최소화하기 위해서, 동적 배열은 사용하는 크기보다 여유 분의 크기(1.5~2배)를 두고 메모리를 할당한다.
• 이동 횟수를 조금씩 줄여 나간다.
• size()는 실질적인 데이터 양, capacity()는 저장할 수 있는 데이터 크기
• clear()를 호출해도 size는 0으로 리셋 되지만, capacity는 리셋 되지 않는다.

• reserve() : capacity의 크기를 조절하는 것
• resize() : size의 크기를 조절하는 것
  • size의 크기가 capacity보다 작으면, 두 변수의 크기를 일치 시켜준다.

• 벡터의 간단한 구현
  

template <typename T>
class Vector
{
public:

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

	void push_back(const T& value)
	{
		//데이터에 삽입
		if (_size == _capacity)
		{
			//크기 증설 작업
			int newCapacity = static_cast<int>(_capacity * 1.5);
			if (_capacity == newCapacity)
				newCapacity++;

			//데이터 새로 생성
			reserve(newCapacity);
		}

		_data[_size++] = value;
	}

	void pop_back()
	{
		_size--;
	}

	void clear()
	{
		//실질적으로는 malloc tree를 이용해 소멸자와 생성자를 관리
		if (_data)
		{
			delete[] _data;
			_data = new T[_capacity]; 
		}
		_size = 0;
	}

	//메모리 증설 역할
	void reserve(int capacity)
	{
		if (capacity < _capacity)
			return;
		_capacity = capacity;

		T* buffer = _data;
		_data = new T[_capacity];

		for (int i = 0; i < _size; i++)
			_data[i] = buffer[i];
		if(buffer!=nullptr)
			delete[] buffer;
	}

	T& operator[](const int pos)
	{
		return _data[pos];
	}

	int size() {
		return _size;
	}

	int capacity()
	{
		return _capacity;
	}

private:
	T* _data = nullptr;
	int _size = 0;
	int _capacity = 0;
};