std::vector vs std::map 비교

std::vector와 std::map은 C++에서 가장 많이 사용되는 컨테이너 중 두 가지이지만, 내부 구조와 성능 특성이 매우 달라 명확한 목적에 따라 선택해야 한다.

1. 핵심 비교

특징	std::vector	std::map
컨테이너 종류	시퀀스 컨테이너 (Sequence Container)	연관 컨테이너 (Associative Container)
내부 구현	동적 배열 (Dynamic Array)	레드-블랙 트리 (Red-Black Tree)
메모리 구조	연속된 메모리 블록 (Cache-Friendly)	노드 기반의 비연속 메모리 (Pointer Chasing)
데이터 정렬	삽입 순서 유지	키(Key)에 따라 자동 정렬
원소 접근	[], at(): O(1)	[], at(): O(log N)
검색 (Search)	std::find: O(N) (정렬 후 std::binary_search: O(log N))	find: O(log N)
삽입/삭제	맨 뒤: Amortized O(1) 중간: O(N)	모든 위치: O(log N)
반복자 무효화	삽입/삭제 시 재할당이 발생하면 모든 반복자, 포인터, 참조 무효화. 중간 삽입/삭제 시 해당 위치 이후의 모든 반복자 무효화.	삽입 시 무효화되지 않음. 삭제 시 삭제된 원소를 가리키는 반복자만 무효화.

2. 상세 분석

2.1. 메모리 구조와 캐시 효율성

• std::vector: 원소들이 메모리에 연속적으로 나열되어 있다. CPU가 첫 번째 원소에 접근할 때, 그 주변의 다른 원소들까지 함께 CPU 캐시(Cache)에 로드(Prefetching)할 가능성이 높다. 따라서 벡터 전체를 순회하는 작업은 캐시 히트(Cache Hit)가 연속적으로 발생하여 std::map보다 월등히 빠르다.
• std::map: 각 원소(노드)가 힙의 서로 다른 위치에 동적으로 할당된다. 한 노드에서 다음 노드로 이동하려면 포인터를 따라가야 한다(Pointer Chasing). 이 과정에서 CPU 캐시 미스(Cache Miss)가 발생할 확률이 높아져, 순차 접근 성능이 std::vector에 비해 떨어진다.

2.2. 주요 연산의 성능 특성

• 접근(Access): std::vector는 v[100]과 같이 인덱스를 사용해 한 번의 연산으로 원소에 접근한다(O(1)).
  반면 std::map은 m[key]를 찾기 위해 레드-블랙 트리를 루트부터 탐색해야 하므로 O(log N)의 시간이 걸린다.
• 검색(Search): std::vector에서 특정 값을 찾으려면 처음부터 끝까지 순차적으로 비교해야 하므로 O(N)이 걸린다.
  std::map은 트리의 이진 탐색 능력 덕분에 O(log N)만에 원하는 키를 찾을 수 있다.
• 삽입/삭제(Insertion/Deletion): std::vector의 중간에 원소를 삽입/삭제하면, 그 뒤의 모든 원소를 한 칸씩 밀거나 당겨야 하므로 O(N)의 비용이 발생한다.
  std::map은 트리 구조를 재조정(회전, 색상 변경)하기만 하면 되므로 O(log N)의 안정적인 성능을 보인다.

3. 언제 무엇을 사용해야 할까?

두 컨테이너의 선택은 '무엇을 더 자주 하는가'에 따라 결정된다.

std::vector가 이상적인 경우:

"모든 원소를 자주 순회하거나, 인덱스로 빠르게 접근해야 할 때"

• 렌더링 목록: 화면에 그려야 할 모든 오브젝트의 목록. 매 프레임마다 전체 목록을 순회하며 draw() 함수를 호출해야 하므로 캐시 효율성이 매우 중요하다.
• 파티클 시스템: 수천 개의 파티클 위치를 매 프레임 업데이트할 때. 전체를 순회하며 물리 계산을 적용한다.
• 게임 로비의 플레이어 목록: 1번 플레이어, 2번 플레이어 등 순서가 중요하고, 전체 목록을 UI에 표시해야 할 때 사용한다.
• 미리 로드된 레벨 데이터: 맵의 타일 정보나 고정된 NPC 위치처럼, 한 번 로드된 후에는 거의 변경되지 않고 읽기 위주로 사용되는 데이터에 적합하다.

std::map이 이상적인 경우:

"고유한 ID(키)로 특정 원소를 빠르게 찾아야 할 때"

• 리소스 관리자: "player_sprite.png"라는 이름(키)으로 텍스처(값)를 빠르게 찾아 로드할 때 사용한다.
• 플레이어 데이터 관리: 플레이어의 고유 ID(키)를 사용해 해당 플레이어의 정보(체력, 레벨, 위치 등) 객체(값)를 즉시 찾아야 할 때 적합하다.
• 아이템/스킬 데이터베이스: 1001번 아이템(키)의 상세 정보(이름, 설명, 능력치 등)를 담은 구조체(값)를 조회할 때 사용한다.
• 랭킹 시스템: 플레이어의 점수(키)를 기준으로 닉네임(값)을 저장하면, 점수 순으로 정렬된 랭킹 보드를 쉽게 만들 수 있다.

4. 결론

• std::vector: 속도와 순회가 중요하다면 첫 번째 선택지. 데이터에 대한 접근이 대부분 순차적이거나 인덱스 기반일 때 최고의 성능을 발휘.
• std::map: 검색과 정렬이 중요하다면 std::map을 사용. 데이터의 순서보다 특정 키를 통해 데이터를 빠르고 안정적으로 찾는 것이 우선일 때 적합.