[자료구조] Vector

벡터

배열과 비슷하며, 크기가 동적으로 확장될 수 있는 동적배열 기반의 구조이다.
배열처럼 인덱스로 요소에 접근이 가능하다.
벡터안에 데이터가 꽉 차면, 벡터의 크기를 2배로 늘린 뒤 원래의 데이터 값을 복사하여 넣어주고, 새 값을 추가해야한다

Template T로 벡터 클래스를 구현해 볼 것이다

• private 에서 size변수와 capacity변수를 선언해주었다
  -> size는 현재 벡터에 들어있는 원소의 수 (실제 사용되고 있는 크기)
  -> capacity는 할당된 전체 메모리 공간의 크기
• T * container는 T타입의 동적배열이다
  
  
• 생성자에서 두 변수의 값을 초기화 하고 container 배열도 초기화

#include <iostream>
#define SIZE 2
using namespace std;

template <typename T>
class Vector
{
private:
	int  capacity;
	int size;
	T* container;


public:
	Vector()
	{
		capacity = 0;
		size = 0;

		container = nullptr;
	}

Resize( ) 함수

• 매개변수로 새 사이즈를 받고 새로운 포인터 변수를 이용해 새 사이즈 크기의 동적 배열을 만든다
• 해당 배열의 메모리 공간을 초기화해준 뒤 기존 배열container[_] 안의 값을 새 배열에 복사하여 넣어준다
• 기존 배열인 container를 해제하여준다
• 기존의 배열을 가리키던 container 포인터 변수를 새로운 변수로 이동
  
  
  

void Resize(int newSize)
{
	// 1. capacity에 새로운 size값을 저장합니다.

	capacity = newSize;

	// 2. 새로운 포인터 변수를 생성해서 새롭게 만들어진
	//    메모리 공간을 가리키도록 합니다. (크기가 capacity인)

	T* newContainer = new T[capacity];

	// 3. 새로운 메모리 공간의 값을 초기화합니다.

	for (int i = 0; i < capacity; i++)
	{
		newContainer[i] = NULL;
	}

	// 4. 기존 배열에 있는 값을 복사해서 새로운 배열에 넣어줍니다.

	for (int i = 0; i < size; i++)
	{
		newContainer[i] = container[i];
	}

	// 5. 기존 배열의 메모리를 해제합니다.

	if (container != nullptr)
	{
		delete[] container;
	}

	// 6. 기존에 배열을 가리키던 포인터 변수의 값을
	//	  새로운 배열의 시작 주소로 가리킵니다.

	container = newContainer;
}

---

PushBack( ) 함수

벡터에 데이터를 넣어주는 함수이다

void PushBack(T data)
{
	if (capacity <= 0)
	{
		Resize(1);
	}
	else if (size >= capacity)
	{
		Resize(capacity * 2);
	}
	container[size++] = data;
}

1. capacity가 0보다 같거나 작을 경우 -> 벡터에 메모리가 아직 할당되지 않은 상태 -> 메모리를 할당해주어야함
   

2. size 가 capacity보다 크거나 같을 경우 -> 할당된 메모리 크기보다 더 큰 양의 원소가 들어갈경우 capacity를 새로 할당해서 만들어 줘야 한다

3. 주로 capacity값을 2배로 할당해준 뒤 기존의 배열 데이터의 값을 새 배열로 복사하여주고 기존의 배열은 해제한다

4. container 포인터의 값을 새로 할당된 배열로 연결시켜주면 된다

5. 배열에 데이터를 넣어준 뒤 size++하여 이동
   

---

PopBack( ) 함수

벡터의 데이터를 빼는 함수이다

void PopBack()
{
	if (size <= 0)
	{
		cout << "Vector is Empty" << endl;
	}
	else
	{
		container[--size] = NULL;
	}
}

1. size 값이 0보다 작거나 같을 경우 -> 할당된 메모리 공간안에 원소가 하나도 들어있지않다 (벡터가 비어있다)
2. 벡터에 데이터가 들어 있을 경우 -> 배열에 전위감소한 인덱스를 NULL

• • 여기서 전위감소한 후 데이터를 NULL로 해주는 이유는 벡터의 인덱스가 0부터 시작하기 때문이다
• • 마지막 원소의 인덱스는 항상 size - 1 이다
• • 따라서, [--size] 인덱스 부터 시작하게 되면 마지막 원소에 바로 접근이 가능한 것! 그래서 마지막 원소부터 바로 삭제할 수 있는 것!
    

---

Size( )함수

const int& Size()
{
	return size;
}

• 여기서 const 란?
  반환하는 size를 상수로 지정하기 위해 사용된다
  반환된 size의 값은 상수이기에 값이 변할 수 없다

• 여기서 &를 사용하는 이유는?
  만약에 &(참조)없이 메인함수에서 Size( )함수를 호출 할 경우, size의 값이 복사되어 반환된다 -> 불필요한 복사비용이 발생한다
  그러나, &가 붙게되면 여기서는 반환되는 값은 size 변수에 대한 참조이다
  이는, 클래스 내부의 size값과 동일한 값을 가지면서 복사비용은 발생하지 않는다

• const와 &를 함께 쓰면 읽기 전용이 보장된다
  
  
  아래의 예시를 보면,

• 참조(&)가 없을 경우
  메인 함수에 들어있는 변수 a의 값은 10
  매개변수로 a의 값인 10이 복사 되어서 들어간다
  둘다 별도의 메모리 공간을 만들었기 때문에 a와 num은 서로 별개의 것이다
  매개변수로 들어간 num의 값은 함수를 거쳐서 1이 된다
  하지만, 메인함수 쪽 a에는 연관이 없다
  -> 결론: num의 값: 1 a의 값: 10

• 참조(&)가 있는 경우
  메인 함수에서 들어있는 변수 a의 메모리 공간이 있다
  변수 a가 복사되어 매개변수로 들어가지 않고, 본래 그대로 매개변수로 들어간다
  Function함수를 거치면 매개변수로 받은 값이 1로 변한다
  a 와 num은 서로 동일한 것 (같은 값을 가지고 이름만 2개를 쓴다는 뜻)
  -> 결론: a의 값: 1
  

---

연산자 오버로딩 & 소멸자

• 매개변수로 들어오는 값은 내가 접근할 인덱스의 번호를 가리킨다
  -> 메인함수에서 클래스의 객체를 만들고 객체를 통해 배열의 인덱스로 접근할 수 있다

• 내가 원하는 배열 인덱스에 들어있는 값을 반환

• operator [ ] 키워드
  [ ] 대괄호를 사용하여 객체의 멤버에 접근할 수 있는 메소드

Container[index]에 접근해서 이 값을 상수 형태로 반환하는 것!!!!!

ex) 클래스타입의 객체를 하나 생성하고 그 객체를 통해 배열의 인덱스에 접근한 뒤 값을 얻어낸다

int main()
{
	Vector vector;
    
    cout << vector[4];
}

소멸자

• 소멸자에서는 container 포인터가 가리키는 곳에 배열이 있다면 delete[ ] 로 동적으로 할당된 배열을 해제
  -> delete[ ] 로 하는 이유
  -> 배열의 각 요소를 차례대로 삭제하고, 배열 전체를 해제한다
  -> 그냥 delete를 사용하는 경우는 단일 객체를 동적으로 할당한 경우 해제할 때 사용된다

const T& operator [] (const int index)
{
	return container[index];
}

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

메인함수

int main()
{
	Vector <int> vector;

	vector.PushBack(10);
	vector.PushBack(20);
	vector.PushBack(30);

	vector.PopBack();

	for (int i = 0; i < vector.Size(); i++)
	{
		cout << vector[i] << endl;
	}
	cout << "Vector의 크기 : " << vector.Size();
	return 0;
}

벡터의 장/단점

벡터의 단점

• capacity와 size를 별도로 관리하기 때문에 메모리가 낭비된다
  ->capacity는 할당된 전체 메모리 크기이고, size는 현재 들어있는 원소의 수기 때문에 size값을 제외한 capacity의 빈 부분은 남는 메모리로 남게된다
  -> 새 메모리를 할당 한 경우, 사용하지 않는 공간이 일시적으로 발생한다

• 배열 처럼 사용되기 때문에 요소의 삽입과 삭제 시 요소를 이동시켜야한다 -> 시간복잡도가 O(n)

• size가 capacity 용량을 초과하게 되면 새 배열에 새 메모리를 할당하고 기존 데이터를 복사해야 하기 때문에 메모리 재할당 비용이 발생한다

벡터의 장점

• 벡터는 배열처럼 사용되기 때문에 인덱스를 통해서 원하는 요소에 바로 접근이 가능하다 -> 시간복잡도가 상수시간 O(1)

• 동적으로 메모리를 할당하기 때문에, 요소를 삽입하거나 제거하는 데 유리하다