Vector

특징

 

연속된 컨테이너를 가지고있다( = 메모리상 연속적으로 저장이 됨 )

 

탐색의 경우 처음부터 끝까지 하나씩 탐색해야하기 때문에 O(n)

 

인덱스를 지원하기때문에 랜덤한 접근은 빠르다(조회) O(1)

 

데이터의 끝부분에 삽입, 삭제는 빠르다. amortized O(1)

[ 삽입시 메모리를 다시 동적할당 받아올 경우 n개만큼 복사가 이루어지기때문에 이 상황에는 O(n) ]

하지만 중간에 삽입, 삭제시에는 그 뒤에 있는 모든 데이터를(n) 한칸씩 앞이나 뒤로 복사가 이루어져 느리다. O(n)

 

컨테이너의 크기가 고정이 아닌 동적으로 이루어진다

하지만 크기가 자주 변경된다면 불리한 자료구조이다.

=> 잦은 동적할당과 해제 => 메모리 단편화가 발생 할 소지가 많다.

 

---

결론

 

크기가 변할 가능성이 있으나 자주는 아닌 경우,

인덱스를 이용한 접근을 사용하는 경우,

처음부터 쭉 순회를 해야할 경우,

중간 삽입,삭제가 적을 경우

vector를 사용할것이다.

 

---

사용처

 

만약 내 게임에서 사용 한다면

 

게임 내의 모든 아이템 데이터를 담는 자료구조로 vector를 사용할거 같다.

아이템은 거의 꾸준히 업데이트 되기 때문에 가변적 특성을 띄고

꼭 순차하여 아이템 정보를 가져오는게 아닌

인덱스를 통해 원하는 아이템정보를 가져올 수 있기 때문이다.

 

플레이어의 분신같은 스킬을 사용할때

각 분신을 vector에 넣을거 같다.

이 스킬에 분신의 개수가 변경될 가능성이 있다고 생각하기 때문에 가변적 특성을 띄고

분신이 나타나고 사라지기 전까지 분신이 추가되는 중간 삽입,삭제가 없어 잘 맞는다고 생각했다.

 

한 맵에서 출현하는 몬스터들의 데이터를 저장할거 같다.

출현하는 몬스터의 수는 거의 고정적이지만 이벤트성이나 다른 몬스터의 추가로 수정 될 수 있다고 생각하였고

중간에 삽입 삭제할 경우가 없다고 생각이 들어 vector가 적당하다 생각했다.

 

---

추가

 

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)이 나오는데

나는 처음에 왜 상수시간복잡도가 나오지? 라고 생각이 들었다.

 

만약에 3번째 데이터를 찾는다 하면

0번 데이터를 찾고 카운트 0, 다음으로 넘어가

1번 데이터를 찾고 카운트 1, 다음으로 넘어가

2번 데이터를 찾고 카운트 2, 다음으로 넘어가

3번 데이터를 찾고 카운트 3.

 

이렇게 3번째 데이터를 찾아서 O(n)이 나오지 않을까? 라는 생각이 들어

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

 

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

 

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

그래서 인덱스가 연속된 메모리의 컨테이너에서 가능한 이유였다~

ㅋㅋㅋㅋㅋ

 

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