Vector

Vector

배열의 크기를 동적으로 관리할 수 있는 컨테이너.

 

Vector는 배열처럼 메모리상 연속적으로 저장이 되는데, 이 뜻은 두 가지 장점을 지닌다.

• 연속적인 메모리를 가지고 있기 때문에 캐시 효율이 좋으며,
• 인덱스 기반 랜덤 접근이 가능해진다.

그에 반해 성능 저하가 되는 요인은 크게 2가지가 있다.

• 메모리 재할당
• 복사 비용
  메모리 재할당에 따른 복사
  중간 삽입/삭제에 따른 복사

 

시간 복잡도

• 탐색 : O(n)
  배열기반이라 처음부터 끝까지 하나씩 값을 확인해야 한다.
  
  
• 접근 : O(1)
  인덱스를 통해 각 원소에 접근할 수 있으므로 상수시간을 가진다.
  
  
• 삽입 (마지막 원소) : O(1) or O(n)
  공간이 여유로울 경우 바로 삽입하면 되기 때문에 O(1),
  공간이 부족해서 공간 재할당 후 새로운 공간으로 복사, 그 후 삽입은 O(n)
  
  
• 삭제 (마지막 원소) : O(1)
  인덱스를 이용해 마지막 원소 접근 후 삭제.
  
  
• 삽입, 삭제 (중간 원소) : O(n)
  삽입이라면 삽입 후 그 뒤의 원소를 한 칸씩 밀어야 하므로, O(n)이다.
  삭제라면 삭제 후 그 뒤의 원소를 한 칸씩 당겨야 하므로, O(n)이다.
  
  

어떻게 사용해야 하는가

인덱스로 자주 접근이 가능해야 할 때,

Stack처럼 대부분 끝에서 삽입, 삭제가 이루어지는 구조를 생각할 때 사용하면 좋다.

 

또한 배열의 크기가 늘어나 재할당이 필요한 순간이 있을 것 같다 생각하면 사용해야 한다.

하지만 메모리 재할당이 발생한다는 건 복사과정 또한 동반되므로, 재할당이 자주 발생한다면 속도가 저하될 수 있다.

그렇기 때문에 크기가 예측 불가능하게 자주 변하고, 중간 삽입/삭제가 빈번하다면 Vector는 적합하지 않다.

 

예전에는 "아니 크기를 동적으로 늘리려고 만들어주셨는데 자주 늘리지 말라고? 이게 무슨..?" 이라는 생각을 했었다.

근데 이제와서 생각해보면 크기를 늘린다는 벡터의 Identity는 고정 크기의 완벽한 대안책이라기보다는,

사람의 예상을 벗어나갔을 때를 대비한 기능이라고 생각한다.

 

"배열 크기는 계속 늘어나니까 계속 늘리자!" 라는 생각보다는 "첫 예상치보다 크기가 많아지네? 그러면 이 정도로 크기를 늘려놓자"
라는 생각으로 사용하면 된다. 그러니까 벡터에는 reserve를 최대한 사용할 수 있는 만큼 사용해야한다!

 

사용 예시

그래서 Vector를 만약 내 게임에서 사용한다면 아이템 데이터를 담는 구조에 사용할 거 같다.

아이템은 거의 꾸준히 업데이트되기 때문에 가변적 특성을 띄고, 꼭 인덱스를 통해 빠르게 접근이 가능하기 때문이다.

 

또 게임에서 쓰이지 않는다고 해서 DB 안에서 진짜 삭제되는 경우는 많이 못 본 것? 같다? 그래서 중간 삭제는 많이 없을 것 같다.

그 경우에는 삭제 대신에 비활성화 bool을 두는 방식으로 하면 좋을 듯 하다.

 

 

구현

멤버 변수

멤버 변수는 3가지로 이루어진다.

• 시작 포인터 : T* 형태의로 연속 메모리를 관리하고, 재할당시 이동 혹은 복사가 이루어진다.
• size : 내가 집어넣은 데이터 개수
• capacity : 벡터에 할당된 메모리 공간 크기

private:
    T* m_data; // vector의 시작 포인터
    size_t m_size; // 내가 넣은 데이터 개수
    size_t m_capacity; // vector의 메모리 할당 크기

 

재할당

할당 부분은 자주 사용되므로 함수화 하여 사용한다.

void reallocate() 
{
	// 첫 동적할당에서는 1만큼 할당하고, 재할당시 2배로 할당한다.
	size_t newCapacity = (m_capacity == 0) ? 1 : m_capacity * 2;
	T* newData = new T[newCapacity];
	
	// 새롭게 할당된 메모리로의 복사
	for (size_t i = 0; i < m_size; ++i)
	{
		newData[i] = std::move(m_data[i]);
	}
	
	// 기존 메모리 반환 후 멤버 변수 갱신
	delete[] m_data;
	m_data = newData;
	m_capacity = newCapacity;
}

 

접근

접근 방식은 [] 오버로딩과 at함수가 있는데, 두 방법의 차이는 범위 검사의 유무뿐이다.

연산자 오버로딩은 검사는 하지 않지만 빠르고, at 함수의 경우 검사를 진행하기 때문에 보다 느리다.

 

구현내용은 모두 간단하다.

T& operator[](size_t index) 
{
	return m_data[index];
}

 

T& at(size_t index)
{
	// (size - 1)이 마지막 원소의 인덱스가 된다.
	if (size - 1 < 	index)
	{
    	throw std::out_of_range("out of range");
	}
	return m_data[index];
}

 

삽입

size는 1부터 시작하고 capacity는 0부터 시작한다.

그렇기 때문에 size = capacity인 경우 메모리에 남은 공간이 없다는 의미가 된다.

메모리에 남은 공간이 없을 때 추가를 해야 한다면 메모리 재할당을 실행하고 보통 이전 메모리의 2배를 할당한다.

void push_back(const T& value) 
{
    if (m_size >= m_capacity)
    {
        reallocate();
    }

    m_data[m_size++] = value;
}

 

삭제

메모리 해제를 하지 않고 size만 줄이는 방법으로 삭제를 구현한다.

쓰레기 값을 처리하지 않아도 되지만 0으로 초기화했다.

 void pop_back() 
 {
    if (m_size > 0)
    {
    	m_data[m_size - 1] = 0;
        --m_size;
    }
}

 

 

덧붙임

vector의 순회 속도

 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=4roring&logNo=221337048963

이 글과 비슷하게 나도 데이터를 순회하는 데 있어서 밑의 5가지 방법을 테스트해봤다

1. 함수 at 사용

2. operator [ ] 사용

3. 주소를 직접 받아 연산해 순회

4. iterator 사용

5. 범위기반 for문 사용

 

20,000,000개의 데이터를 순회하면서 int형 변수 result에 계속 더하여 테스트했다.

(좌) Debug mode (우) Release mode

느낀 점

 

1.

이번에 찾아보면서 at과 [ ]를 비교하는 글이 많았었다.

at은 out of range 검사를 해주지만

[ ]은 검사를 하지 않기 때문에 at보다 빠르다고 많이들 적혀있었는데

평균적으로 debug모드에서는 정말 차이가 없고 release모드에서만 차이가 확실히 났다.

 

2.

iterator를 사용한 경우 debug모드에서는 굉장히 느렸지만 release모드에서는 굉장히 빠른 모습을 보였다

반전매력 ㄷㄷ

 

3.

다른 결괏값이 나오기 전까지 vector를 순회할 때는 range based for문을 사용해야겠다

 

4.

그래도 이 테스트는 절대적인 성능이 아니라 대략적으로 파악하기 위한 거니

상황이 달라지면 결과도 바뀔 수 있기에 일반화하지 말자

 

코드 부분

설정 부분

테스트 부분

 

왜 Index로 인한 조회는 O(1)?

Index로 인한 조회는 빅오가 O(1)이 나오는데,

정확히 어떤 과정이 수행되길래 상수시간복잡도로 나오지? 라고 궁금해했었다.

왜냐하면 아직 for문을 사용한 순차탐색만 알고 있었기 때문이다..

 

Index의 조회가 어떻게 이루어지는지 궁금해서 찾아보았다.

바로 주소값을 계산해서 주소로 들어가 한번에 찾는 건데

 

"시작위치 + (인덱스 * 데이터 타입 크기)" 로 계산하여 찾으려는 데이터를 한 번에 O(1)로 찾아내는 것이었다...!

 

https://dc7303.github.io/essay/2020/02/23/whyUseArrayInsteadOfList/