ForestBird

벡터의 특징중 하나인 어느 위치에서든 원소의 삽입과 삭제를 고려해서 짜야한다

삽입코드

	//마지막 위치에 원소를 추가합니다
	void Add(const Data& data)
	{
		Insert(this->Num(), data);
	}
	
	//정해진 위치에 원소를 추가합니다
	//원소 삽입시 기존 위치의 원소부터 마지막원소까지 전부 인덱스가 +1씩 밀리기 때문에
	//원소가 많고 0의 가까운위치에 삽입될수록 느려질 수 있습니다
	void Insert(const size_t insert_index, const Data& data)
	{
		//컨테이너에 비어있는 자리가 있는지 확인
		if (this->my_size == this->my_capacity)
		{
			//빈자리 없음. 재할당을 시도합니다
			this->Reserve(this->my_capacity + this->additive_capacity);
		}


		//컨테이너 중간에 원소가 들어간다면 원소를 해당 지점부터 한칸씩 뒤로 이동시킵니다.
		for (size_t i = this->my_size; i > insert_index; --i)
		{
			this->my_base[i] = this->my_base[i - 1];
		}
		

		//추가합니다
		this->my_base[insert_index] = data;
		++this->my_size;
	}

Add()는 마지막위치에 원소를 삽입하는 함수이므로 Insert()만 보겠다.

Insert()는 아래 순서로 작동한다

1. 컨테이너(배열)에 빈자리가 있는지 확인-> 빈자리가 없다면 재할당

2. 삽입해야할 위치의 원소부터 마지막원소까지 전부 한칸씩 이동

3. 삽입해야할 위치가 비었으니 원소추가

여기서 우린 2번항목을 잘 봐야한다. 왜 중간에 원소를 삽입하면 퍼포먼스가 떨어지는지...

단순히 원소를 옮기는 작업이기에 가끔 한두번 삽입하는건 일반적인 환경에선 문제가 없지만,

자주, 빈번하게, 매 프레임 중간삽입을 한다면 분명히 문제를 가져올것이라고 생각한다.

원소가 0번째 인덱스에 가까울수록 퍼포먼스가 떨어진다. 반대로 말하면

마지막에 원소를 추가하는것은 퍼포먼스에 문제가 없다. 

중간삽입은 작업내용을 고려해서 사용해야 한다.

삭제코드

	//해당 위치의 원소를 삭제합니다
	void RemoveAt(const size_t index)
	{
		this->CheckValidIndex(index);

		--this->my_size;
		for (size_t i = index; i < this->my_size; ++i)
		{
			this->my_base[i] = this->my_base[i + 1];
		}
	}

	//원소이동의 부하를 줄이기 위해 삭제될 원소와 마지막 원소의 위치만 변경하고 삭제합니다
	//마지막 원소가 삭제된 원소의 위치로 오기 때문에 원소의 순서는 보장되지 않습니다
	void RemoveAtSwap(const size_t index)
	{
		--this->my_size;
		this->my_base[index] = this->my_base[this->my_size];
	}

RemoveAt(): 해당 위치(인덱스)의 원소 삭제.

RemoveAtSwap(): 해당 위치의 원소를 삭제후 빈공간을 마지막 원소로 대체. 순서가 보장되지 않음.

RemoveAt()을 보면 Insert()와 동일하게 원소를 이동시킨다. 역시 마지막 원소를 삭제하는것은 퍼포먼스에 문제가 없다.

벡터는 순서를 보장하는 장점이 있지만, 순서상관없이 사용하는 경우도 많이 있다.

가령 쉽게 원소에 접근하기 위해 등등...

그런 사람들을 위해 RemoveAtSwap()을 사용하면 순서는 보장되지 않지만 어느 위치의 원소를 삭제해도 퍼포먼스에 문제가 없다.

https://github.com/ForestBird1/MyContainer

생성자와 소멸자 코드

	MyVector()
	{
		//my_base가 nullptr지만
		//사이즈및 캐퍼시티가 0이므로 원소를 추가할때 Reserve()함수에서 할당이 이뤄집니다
		this->my_base = nullptr;
		this->my_capacity = this->my_size = 0;
	}
	MyVector(std::initializer_list<Data> list)
	{
		this->my_capacity = this->my_size = 0;
		this->Reserve(list.size());

		for (auto& element : list)
		{
			this->my_base[this->my_size++] = element;
		}
	}
    //MyVector<int> my_vector({ 1, 2, 3, 4 });
	~MyVector()
	{
		if (this->my_base)
		{
			delete[] this->my_base;
		}
	}

벡터를 생성할 때 즉시 원소를 넣고싶으면 2번째 생성자처럼

MyVector<int> my_vector({ 1, 2, 3, 4 });

이렇게 넣으면된다. 

소멸자가 호출되면 벡터 내부에 포인터로 작성된 배열을 해제하는것을 볼 수 있다.

캐퍼시티(Capacity)란?

캐퍼시티: 배열의 빈공간을 포함한 최대크기.

사이즈: 배열의 원소갯수.

std::vector는 원소를 추가할 때 사이즈가 캐퍼시티를 초과하면 새롭게 캐퍼시티를 할당합니다.

그냥 배열에 추가하면 알아서 되는거아냐?

새롭게 캐퍼시티를 할당하는게 왜?

어쨌든 잘 돌아가면 되는거 아냐?

라고 생각하면 당신은 주니어(라고 포프님이 그랬습니다)

캐퍼시티의 할당을 고려하지 않고 배열을 생성하게 되면 퍼포먼스의 악영향을 끼칠 수 있습니다.

단순히 10개 100개 1000개를 만드는건 크게 체감되지 않을테지만, 특정한 상황에선 고려해야합니다.

왜그럴까요? 우선 코드부터 봅시다

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

	//캐퍼시티를 늘릴 때 지정된 값이 없다면 해당 값만큼 늘립니다
	const size_t additive_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;
	}
};

Reserve()함수 입니다.

간단하게 문장으로 표현하면 이렇습니다

1. new를 사용해 새롭게 할당.

2. for루프로 기존 원소를 새롭게 할당한 곳에 전부 이동.

3. 기존에 할당된 배열(Data*)은 삭제하고 새롭게 할당된 배열을 등록합니다

이미지로 보자면...

첫번째 이미지 처럼 원소를 가진상태로 배열의 사이즈가 꽉차서 재할당이 이뤄지면 모든 원소가 새로운 배열로 이동하는것을 볼 수 있다. 이미지는 7개밖에 되지 않지만

만약 원소가 만개라면? 십만개라면?

게다가 재할당할때 마다 캐퍼티시는 여러개가 추가되는게 아니라 std::vector를 기준으로 1개만 추가된다.

그러면 만개의 원소를 하나 추가한다고 가정하면 1+2+3+4+5+...+9999 만큼 원소가 이동하게 되고 10000번의 재할당이 이뤄진다. 메모리 파편화의 가능성도 있다.

언리얼엔진같은 경우는 더 많이 캐퍼시티가 증가하지만 그것이 근본적인 해결책이 되진 않는다.

그렇기에 배열(벡터)을 생성하게 된다면 꼭 미리 할당을 해야한다.

원소를 10개 채울려면 원소를 추가하기 전에 Reserve(10)함수를 사용하면된다.

만약 원소를 몇개 채울지 모르겠다면 추정치라도 Reserve()해준다.

std::vector는 예기치 않게 캐퍼시티를 늘릴 경우 1만 늘어나는것을 나는 32개의 캐퍼시티를 늘리게 구현해놨다.

처음엔 기존원소개수의 2배씩 캐퍼시티를 늘릴까 생각했지만, 그렇게까지 할 필요를 못느껴서 32개로 고정했다.

32개로 설정한 이유는... 없다. 그냥 느낌이 32개가 좋다. 뭔가 적절한느낌 이다.

https://github.com/ForestBird1/MyContainer

size_t는 unsigned_int와 동일합니다

그렇다면 굳이 size_t가 존재하는 이유가 무엇일까요?

size_t의 선언부를 보게되면 이렇게 되어있습니다

#ifdef _WIN64
    typedef unsigned __int64 size_t;
#else
    typedef unsigned int     size_t;
#endif

64비트일땐 64바이트, 32비트일땐 32바이트의 unsigned_int로 정의되어 있습니다.

환경에 따라서 size_t의 크기가 보장되지만

int는 64비트환경이더라도 64바이트를 보장받을 수 없습니다.

이것이 size_t와 unsigned int의 차이점입니다.

하지만 이것은 size_t의 사용목적을 제대로 알려주진 않습니다

size_t를 사용해야하는 가장 큰 이유는...

size_t는 메모리나 문자열등의 길이를 표현할 때 사용한다

메모리와 문자열은 0미만의 사이즈는 존재할 수 없습니다. 그런데 자신이 직접 컨테이너를 작성했는데 size_t를 사용하지 않고 int, short 등의 signed 자료형을 사용하고, 다른 컨테이너는 unsigned를 사용하게 되어 중구난방이 되면 어떤 문제를 가져올지 알 수 없습니다. 

그래서 특정상황에서 통일된 자료형을 사용하기 위해 size_t를 사용하고 있습니다.

이것이 size_t를 사용하는 중요한 이유라고 생각됩니다

자신이 size_t를 사용하지 않고 unsigned_int를 사용해서 컨테이너를 만들어도 자료형 때문에 문제가 생기진 않을겁니다. 다만, size_t를 사용하면 이것이 컨테이터의 메모리사이즈라는 의미를 '명확'하게 주기 때문에

코드 가독성을 더 높여줄 것이라고 기대합니다.