자료구조 SearchTime - map,set,unordered_map
map, set, multimap, multiset 은 일반적으로 binary tree로 구현되어 있다. (VS 컴파일러의 경우, Red Black Tree로 구현되어 있음) https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC 오른쪽, 왼쪽을 비교해가면서 'Key'를 찾아가는 구조이다. 이와 같은 구조는 O(log n) 의 시간이 소요된다. 반면, unordered_map 이나 unordered_set의 경우 (c++11 이상에서 사용가능), 해쉬테이블로 구현되어 있다. bucket이라는 일종의 슬롯형태에 데이터를 해쉬알고리즘에 나누어서 집어넣는 구조인데, 해쉬함수가 constant time이라고 가정..
더보기
