vector 순회 vs map 순회

Question

안녕하세요. 루키스님 STL 강의를 보다가 순회하는 속도에 대해서 궁금한 점이 있어서 질문을 남깁니다. 1만개의 데이터가 있을 때 vector로 순회하는 것보다 map으로 순회하는 것이 느리다고 하셨는데 그 이유가 무엇인가요? vector 같은 경우 iterator를 직접 사용하지 않고 바로 인덱스로 순회할 수 있고 map은 iterator를 한칸씩 증가하면서 순회해야하기 때문인 것인가요? 혹은 vector는 메모리가 연속되어 있기 때문에 템퍼럴 로컬리티와 스페이셜 로컬리티 특성으로 인해 캐시히트가 잘 일어나게 되고 map은 메모리가 연속되어 있지 않기 때문에 반대로 캐시 미쓰가 많이 일어나서 그런 것인가요?? list또한 궁금합니다. 나머지 2개의 컨테이너와 비교했을 때 순회하는 속도가 어떤지도 궁금합니다. vector list map을 for문으로 순회하는 것에 대해서 무엇이 빠르고 느린지 이유를 알고 싶습니다!

Rookiss · Answer

이 부분은 자료구조&알고리즘에 대한 이해도가 필요하고 여기서 모든 원리를 설명드릴 수가 없습니다. 각기 다른 container에 대해 동일한 iterator 형식이라고 내부적으로 iterator가 동일하게 동작하는 것은 아닙니다. vector는 동적 배열이니 가장 빠르고 (+ 캐시 영향도 물론) list는 연결 리스트 방식이니 조금 더 느리고, map은 red-black-tree 방식이니 전체 순회는 더더 느린 것이죠. 순회 테스트는 직접 데이터 100만개를 넣어서 실행 시간 테스트를 해보시기 바랍니다.