[C++] 나만의 Vector만들기 (3) - 원소 삽입, 삭제

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

---

삽입코드

	//마지막 위치에 원소를 추가합니다
	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

GitHub - ForestBird1/MyContainer