• 카테고리

    질문 & 답변
  • 세부 분야

    게임 프로그래밍

  • 해결 여부

    미해결

vector 순회 vs map 순회

21.11.21 19:36 작성 조회수 531

0

안녕하세요. 루키스님 

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

 

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

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

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

 

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

 

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

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

 

답변 1

답변을 작성해보세요.

0

이 부분은 자료구조&알고리즘에 대한 이해도가 필요하고
여기서 모든 원리를 설명드릴 수가 없습니다.

각기 다른 container에 대해 동일한 iterator 형식이라고
내부적으로 iterator가 동일하게 동작하는 것은 아닙니다.
vector는 동적 배열이니 가장 빠르고 (+ 캐시 영향도 물론)
list는 연결 리스트 방식이니 조금 더 느리고,
map은 red-black-tree 방식이니 전체 순회는 더더 느린 것이죠.

순회 테스트는 직접 데이터 100만개를 넣어서
실행 시간 테스트를 해보시기 바랍니다.