📒 vector<pair> vs map
📌 문득 vecotr\<pair>와 map 중 무엇이 더, 어떤 상황에서 효율적인지 궁금해졌다.
- 매우 작은 vector에서 항목을 찾는 것은 맵에서 동일한 항목을 찾는 것보다 쉽고 더 빠르게 찾을 수 있다고 한다.
- 그 이유는 vector의 모든 메모리는 항상 연속되어 있기 때문이라고 한다.
- 그래서 컴퓨터의 캐시 등과 더 잘 작동한다.
- map이 vector보다 빨라지는 지점은 구현, 프로세서, map에 있는 데이터, 프로세서 캐시에 있는 메모리와 같은 미묘한 사항에 따라 달라질 수 있다.
- 일반적으로 map이 더 빨라지는 지점은 약 5~30개 요소일 때이다.
- map은 일반적으로 binary search tree로 구현되어 탐색하는 데에 (항상)약간의 오버헤드(비교 수행, 링크 탐색 등)가 발생한다.
- 그에 비해 vector는 배열일 뿐이기 때문에 매우 작은 양의 데이터의 경우 때로는 binary search tree를 탐색하는 것보다 배열에 대해 선형 검색을 수행하는 것이 더 빠를 수 있다.
- map은 힙 전체에 걸쳐, 여러 개의 작은 할당을 갖는 경향이 있는 반면에 vector는 연속적이므로 모든 요소를 앞에서 뒤로 반복하는 경우 vector의 캐시 적중률이 약간 더 좋을 수 있다고 한다.
자료 출처 : https://stackoverflow.com/questions/454762/vector-or-map-which-one-to-use
복습하기 위해 쓰는 글