map과 unordered_map의 차이 mapunordered_map순서오름차순 정렬정렬 없음구현트리 구조해시 테이블탐색 시간log(N)O(1)삽입 시간log(N)O(1) 요약map은 정렬 순서를 보장하고 unordered_map은 보장하지 않는다.unordered_map은 hash 기반으로 map보다 속도가 빠르다.map은 BST(Binary Search Tree) 기반으로 해시 충돌에서 안전하다.set과 unordered_set도 동일하게 각각 트리, 해시 기반이다.multimap과 multiset은 BST 기반이다.참조https://zshchun.github.io/posts/map%EA%B3%BC-unordered-map%EC%9D%98-%EC%B0%A8%EC%9D%B4/
unordered_map
unordered_map과 배열의 성능 차이오프라인 쿼리 문제를 풀다가 unordered_map을 이용하면 시간초과가 나고 배열을 사용하면 시간이 단축되는 경험을 했다. 둘 다 접근할 때 O(1)으로 알고 있었는데, 어디서 차이가 날까 생각해보았다. 해시충돌 때문이라고 넘어갈까 했지만 자세히 알아보고 기록해두는 게 좋을 거 같아서 포스팅하기로 결정했다. 1. unordered_map vs 배열a) unordered_map의 특성시간 복잡도평균적으로 O(1) 시간에 접근 가능핮만 최악의 경우 O(N)으로 느려질 수 있음 (해시 충돌 발생 시)캐시 활용도unordered_map은 내부적으로 해시 테이블을 사용하며 데이터가 메모리 상에 분산되어 저장된다.따라서 캐시 적중률(cache hit rate)가 낮아질..
