[C++] 나만의 Vector만들기 (1) - 기초설명

벡터는 '동적 배열 클래스'입니다

 

1. 벡터는 배열(array)과 다르게 크기 수정이 언제는 가능하다

배열은 한번 크기를 설정한 이후 수정이 불가능하지만, 벡터는 언제는 크기 수정이 가능합니다.

이렇게 보면 크기수정이 매우 마법처럼 보이지만 사실은,

크기가 수정되면 새로운 배열을 만들어 기본 배열의 원소를 이동시키게 됩니다

사실은 하나의 배열을 늘렸다 줄였다 하는것이 아니라 !새로운!배열을 만들어 버립니다.

 

그렇기 때문에 벡터생성시 캐퍼시티를 미리 생성해주는것이 매우 중요합니다.

캐퍼시티를 미리 생성하지 않아도 벡터가 꽉차면 새로운 배열을 생성해서 늘려주긴 합니다만, 

상황에 따라서 퍼포먼스에 악영향을 미칠 수 있습니다.

여기서 캐퍼시티란, 벡터의 원소개수가 아니라 빈공간을 포함한 벡터의 크기입니다.

 

예를 들자면, 벡터라는 아파트에 캐퍼시티라는 빈 집을 미리 만들어놔야 원소라는 입주민을 언제든 받을 수 있습니다

만약 한층에 하나의 입주만 받는 20층짜리 아파트는 20가구의 입주민만 받을 수 있죠.

21번째 가구가 입주한다고 했을 때 이미 지어진 아파트에 1층을 올릴순 없습니다.

그래서 21층짜리 아파트를 새로 짓습니다.

그리고 이전 아파트에 살던 입주민들을 새로운 아파트로 재입주 시키게 됩니다.

그렇기 때문에 처음 아파트를 지을때 미리 캐퍼시티라는 빈 집을 입주민에 맞게 지어놔야 다시 아파트를 지을일이 없습니다.

 

꼭 추가될 원소개수를 고려해 캐퍼시티를 고려합시다.

 

2. 원소가 메모리상에 인접해 있어서 벡터의 어떤 원소든 쉽게 접근할 수 있지만,

항상 인접해야있어야하므로 벡터의 중간원소의 삽입,삭제가 일어나면 빈공간을 메꿔야하므로

빈번하게 일어나면 비효율적이다.

벡터는 모든 원소가 메모리상에 순서대로 붙어있습니다. 덕분에 원소의 순서가 보장되어 있지만, 중간에 원소가 삽입, 삭제가 발생하면 빈공간을 메꿔야하기 때문에 비효율적이고 이유는 해당 지점을 기준으로 모든 원소가 옆 메모리로 이동하게 됩니다.

 

중간삭제이슈:

위에 설명했듯이 20층짜리 벡터가 있고 입주민이 꽉차있는 상황에서 10층 입주민이 삭제라는 이사를 하게 되었습니다. 그럴때 10층을 빈 공간으로 두지 않고 11층 입주민은 10층으로, 12층입주민은 11층으로...20층입주민은 19층으로 이동하게 됩니다.

그저 원소 하나를 삭제했을 뿐인데 10개의 원소가 모두 이동하게 되었습니다.

환경에 따라서 가끔 한두번 그러는건 문제 없겠지만, 빈번하게 일어나면 퍼포먼스에 악영향을 끼치게 됩니다.

 

중간삽입이슈:

마찬가지로 20층짜리 벡터가 있고 입주민이 꽉차있는 상황에서 10층에 새롭게 입주하려는 입주민이 있습니다.

그럼 역시 기존10층입주민은 11층으로... 11층입주민은 12층으로... 20층입주민은 21층으로....

삭제와 마찬가지로 11개의 원소가 이동하게 됩니다. 게다가 21층을 필요로하니 아파트를 새로 짓기까지 해야합니다.

 

이렇게 모든 원소를 꼭 붙혀놓으려고 하는 이유는 언제는 쉽게 벡터의 원소에 접근하기 위해서 입니다.

만약 10번째 원소를 삭제했을 때 빈공간으로 놓으면 우리는 원소를 가져올 때마다 비어있는지 확인해야하고, 원소를 삽입할 때 마다 빈공간을 찾아야하고 굉장히 바빠질것입니다. 

 

순서를 보장받고싶진 않지만 벡터를 사용하고 싶을 때 사용할 수 있는 꼼수가 하나 있습니다.

순서를 보장받을 필요가 없다면 중간삽입을 할 필요가 없으므로 중간삭제에 대해서만 확인하면됩니다.

그 방법은 원소삭제후 빈 공간을 벡터의 마지막원소만 이동시켜 채워넣으면 됩니다.

 

마지막원소의 위치가 변경되었으니 순서는 바뀌었지만, 대신 중간삭제에 대해선 문제없이 할 수 있습니다.

해당 방법은 예제에 있습니다.

---

제가 구현한 벡터의 함수들입니다.

 

생성자()

생성자(std::initializer_list<Data>)

소멸자()

 

Reserve(): 캐퍼시티할당

Clear(): 배열의 모든원소 삭제(실제로 삭제되지 않고 배열사이즈를0으로 변경합니다. 캐퍼시티는 그대로입니다)

Num(): std::vector.size()와 동일한 함수로 배열의 원소개수를 알려줍니다

Max(): 배열의 캐퍼시티를 알려줍니다

 

Add(): 배열 마지막위치에 원소추가

Insert(): 배열의 원하는 위치에 원소추가

RemoveAt(): 배열의 원하는 위치의 원소를 삭제합니다(실제로 삭제되지 않고 배열사이즈를 1줄입니다)

RemoveAtSwap(): 배열의 원하는 위치의 원소를 삭제하고, 그 자리에 마지막원소를 가져와 채웁니다.(실제로 삭제되지 않고 배열사이즈를 1줄입니다). 해당방법을 사용하면 원소의 순서는 보장할 순 없지만, 삭제된 위치부터 마지막위치까지 원소를 +1만큼 이동시키지 않아도 됩니다.

PopBack(): 스택의 Pop()처럼 마지막 원소를 삭제하고 반환합니다.

 

그외에...

이터레이터

오퍼레이터[], =

---

기능을 추가로 넣는다면 Clear()는 원소사이즈를 0으로 변경하지만 새로운 함수를 만들어서 캐퍼시티까지 0으로 변경하는 방법도 있겠습니다.

Add, Num, Max등 기존 벡터함수이름와 다르게 언리얼엔진의 TArray를 참고해서 함수명을 작성했습니다.

제가 언리얼엔진을 써서 그런지 TArray의 함수명이 더 직관적이라 편하다고 생각됩니다

 

앞으로 시간될 때 공부도 할겸 Stack, LinkedList등등 기초 자료구조를 만들어서 포스팅할 생각입니다.

 

---

우선 클래스를 먼저 보여드리겠습니다

#pragma once

template <typename Data>
class Container_Master
{
protected:
	Data* my_base = nullptr;
	size_t my_capacity = 0;
	size_t my_size = 0;

	//캐퍼시티를 늘릴 때 지정된 값이 없다면 해당 값만큼 늘립니다
	size_t base_capacity = 32;
public:
	//컨테이너의 공간을 새로 생성합니다
	void Reserve(size_t capacity)
	{
		//기존 캐퍼시티가 더 크다면 재할당을 하지 않습니다
		if (my_capacity > capacity)
			return;

		Data* temp = new Data[capacity];
		my_capacity = capacity;

		//컨테이너에 원소가 있다면 새로 할당한 주소로 옮겨줍니다
		if (my_size >= 1)
		{
			for (size_t i = 0; i < my_size; i++)
			{
				temp[i] = my_base[i];
			}
			delete[] my_base;

		}

		my_base = temp;
	}

	//배열의 원소를 삭제하지않고
	//사이즈를 0으로 만듭니다
	//Clear()함수후에 원소룰 추가하면 기존에 있던 원소를 덮어씌웁니다
	void Clear()
	{
		my_size = 0;
	}

	//컨테이너의 원소개수입니다
	size_t Num()
	{
		return my_size;
	}

	//컨테이너의 캐퍼시티개수입니다
	size_t Max()
	{
		return my_capacity;
	}
	
    	//인덱스 유효성검사를 합니다
	//유효하지 않으면 throw
	bool CheckValidIndex(const size_t index)
	{
		if ((index >= 0) && (index < this->my_size))
		{
			return true;
		}
		else
		{
			throw printf("범위를 벗어난 인덱스를 사용하였습니다. 접근하려는 인덱스: %d, 배열크기: %d", index, this->Num());
		}
	}
};

#include "Container_Master.h"

template <typename Data>
class MyVector : public Container_Master<Data>
{

};

Container_Master를 부모를 두고 MyVector클래스가 있습니다.

벡터를 구현하다보니까 앞으로 스택을 구현할 때 중복될거같은 부분을 부모클래스로 올렸습니다.

아직 스택을 구현해본적이 없지만... 그럴거같아서요...

 

std::vector의 템플릿방식으로 클래스를 생성했습니다.

 

템플릿에 대한 자세한 내용은 여기서 확인해주세요

https://modoocode.com/219

https://modoocode.com/219

 

벡터의 사이즈를 int, unsigned int를 사용하지 않고 size_t를 사용한 이유는 여기서 확인해주세요

https://forestbird0.tistory.com/37

[C++] size_t의 역할

---

https://github.com/ForestBird1/MyContainer

GitHub - ForestBird1/MyContainer