안녕하세요! vecotr map

Question

면접을 보다가 면접질문 중 map 과 정렬된 vector> 비교하여 설명 하시오 라는 문제가 나왔습니다. 답변을 map 는 레드블랙트리기반의 중복이 허용되지않고 key 로 오름차순 정렬되어있으며, 안에 데이터는 pair 로 되어있다. vector> 연속적인 메모리 구조를 가지고 있으며 랜덤엑세스가 가능하며, sort 시 pair<> 의 first 값의로 기본 정렬한다. 라고 답변을 했습니다. 답변을 들으시더니 면접관님께서 "정렬된" 이라는 키워드를 중점으로 다시 생각해보라고 하셨는데 답변을 못했습니다. 어떤의도로 문제를 내신지 알 수 있을까요?

Rookiss · Answer

조금 질문이 애매하긴 하네요.
정확한 의도는 질문자만 알겠지만, '정렬된'을 강조하는 것을 보니
이미 정렬된 상태의 vector vs map를 비교하라는 의도 같습니다.

탐색:
map은 레드블랙트리 기반이니 임의의 자료를 찾을 때 O(logN)
일반 vector라면 임의의 자료를 찾을 때 O(N)이겠지만
이미 정렬되어 있는 상태라면 이진 검색을 통해 O(logN)이 가능합니다.
map은 노드 기반인 반면 vector는 인접한 배열을 서칭하게 되니,
자료가 100% 더 이상 추가되지 않는다면
map보다 정렬된 vector을 이용하는 것도 괜찮을 수 있겠죠.

추가/삭제:
하지만 결국 데이터가 삭제 되거나 추가 되어야 한다면,
노드 기반의 map은 여전히 O(logN)에 빠른 처리가 가능하지만
vector의 경우 중간 삽입/삭제가 느리기 O(N)+@ 때문에 문제가 될 수 있습니다.

정렬된 vector vs map을 비교하라는 문제에서
sort 시 pair<> 의 first 값의로 기본 정렬한다
위 답변이 질문자 의도와는 달라 조금 아쉬웠을 것 같네요.

안녕하세요! vecotr<pair<int,int>> map