[스터디] vector/list/map 차이

vector

동적 배열을 기반으로 하는 컨테이너

동적 배열을 기반으로 하기 때문에 인덱스 접근이 가능하다.

삽입 시에는 앞에서 할 수 없으며, 맨 뒤에서부터 삽입해 나간다.

중간 삽입 시에는 삽입 공간의 확보

중간 삭제 시에는 삭제 공간의 활용 -> 을 위해 인덱스 이후 원소 개수만큼 포인터 이동이 발생한다. -> 선형 시간 복잡도

단, 맨 뒤에 삽입 및 삭제 시에는 빠르다! -> 상수 시간 복잡도

동적 배열이므로 배열의 크기를 넘어서는 삽입의 시도가 있을 경우

배열의 재할당 및 복사가 발생한다.

 

-> vector는                      삽입/삭제                         불리하다.

-> vector는                        탐색                              용이하다.

 

vector(인벤토리/맵 만들 때 사용: 맵의 17번째 그림이 바뀌었다면 빠르게 탐색하여 변경해야하니 vector 컨테이너 사용)    

 

삽입/삭제 -> 선형 시간 복잡도(불리하다)

탐색       -> 상수 시간 복잡도(용이하다)

 

 

list(총알 만들 때 사용: 만약 vector로 만든다면 개발 시 미리 총알 개수를 받아와야 하는데 플레이어가 총알을 10발 쏠지 20발 쏠지 알 수가 없다-> list로 런타임 시에도 사용자가 원할 때 언제든지 계속해서 노드를 삽입해 나갈 수 있다!)

삽입/삭제 -> 상수 시간 복잡도(용이하다)

탐색       -> 선형 시간 복잡도(불리하다)

 

노드를 기반으로 하는 컨테이너이다!

더블 링크드 리스트로 구현되어 있다.

앞, 뒤 원소 삽입 및 삭제가 가능하다.

각 노드는 연속적인 메모리에 나열된 것이 아니다!

-> 메모리 여기저기 저장되지만 포인터로 연결되어 있을 뿐!

-> 인덱스 접근이 불가능하다.

임의 원소에 접근하기 위해서는 모든 노드를 순차적으로 탐색해야한다.->선형 시간 복잡도

중간 삽입 및 삭제 시에는 앞, 뒤 노드의 포인터 연결을 해제,

삽입할 노드에 재 연결만 하면 된다!-> 상수 시간 복잡도

또한, 동적 배열처럼 한정된 공간을 사용하는 것이 아니기 때문에

런타임 시에도 사용자가 원할 때 언제든지 계속해서 노드를 삽입해 나갈 수 있다!

 

 

map

map의 원소들은 key와 value로 한 쌍을 이룬다.

각 원소들은 삽입 시에 key값에 따라 자동 정렬이 발생한다.( 기본 정렬방식: less(오름차순) greater(XXXXX) )

-> 중복 key값은 허용하지 않는다.

key값에 따라 정렬이 되고 있기 때문에 반복자를 통한 탐색 또한 가능하다.

key값으로 인해 노드 기반 컨테이너들 중 유일하게 탐색이 가능하다.

리소스 탐색 용으로 많이 사용된다.

로그 시간 복잡도이다.