인프런 커뮤니티 질문&답변

안녕하세요. 루키스님 

STL 강의를 보다가 순회하는 속도에 대해서 궁금한 점이 있어서 질문을 남깁니다.

 

1만개의 데이터가 있을 때 vector로 순회하는 것보다 map으로 순회하는 것이 느리다고 하셨는데 그 이유가 무엇인가요?

vector 같은 경우 iterator를 직접 사용하지 않고 바로 인덱스로 순회할 수 있고 map은 iterator를 한칸씩 증가하면서

순회해야하기 때문인 것인가요?

 

혹은 vector는 메모리가 연속되어 있기 때문에 템퍼럴 로컬리티와 스페이셜 로컬리티 특성으로 인해 캐시히트가 잘 일어나게 되고 map은 메모리가 연속되어 있지 않기 때문에 반대로 캐시 미쓰가 많이 일어나서 그런 것인가요??

 

list또한 궁금합니다. 나머지 2개의 컨테이너와 비교했을 때 순회하는 속도가 어떤지도 궁금합니다.

vector list map을 for문으로 순회하는 것에 대해서 무엇이 빠르고 느린지 이유를 알고 싶습니다!