컨테이너 선택 기준표
컨테이너는 값의 보관 방식보다 조회, 삽입, 순회 패턴을 먼저 보고 고릅니다. 빅오가 같아도 캐시 지역성, 반복자 무효화, 정렬 필요성이 결과를 바꿉니다.
연속 메모리
연속 메모리와 인덱스 접근이 필요할 때 기본 선택입니다. 중간 삽입보다 순회와 cache hit가 중요할 때 강합니다.
앞뒤 삽입
앞뒤 삽입이 자주 있지만 임의 접근도 필요할 때 맞습니다. 완전한 연속 메모리는 아니므로 vector와 캐시 특성이 다릅니다.
정렬된 키
정렬된 키, lower_bound, 범위 순회가 중요한 경우에 씁니다. 삽입 후에도 정렬 순서가 유지됩니다.
빠른 조회
평균 O(1) 조회가 중요하고 순서가 필요 없을 때 씁니다. hash 품질과 rehash 비용을 함께 고려합니다.
삽입과 삭제 후 기존 반복자, 참조, 포인터가 유효한지 먼저 확인합니다.
빅오뿐 아니라 원소 크기, 이동 비용, 메모리 할당 횟수, 캐시 친화성도 같이 봅니다.
조회가 많은지, 순회가 많은지, 정렬이 필요한지 말하면 후보가 자연스럽게 좁혀져야 합니다.