자료구조 맵(Map)과 셋(Set)
맵(Map)
map은 고유한 키를 기반으로 키 - 값 (key - value) 쌍으로 이루어져 있는 정렬된(삽입할 때마다 자동 정렬되는) 자료구조이다.
균형잡힌 이진탐색트리인 레드 - 블랙트리로 구현된다.
고유한 키를 갖기 때문에 하나의 키에 중복된 값이 들어갈 수 없으며
자동으로 오름차순 정렬되기 때문에 넣은 순서대로 map을 탐색할 수 있는것이 아니라 아스키코드순으로 정렬된 값들을 기반으로 탐색하게 된다.
또한 대괄호 연산자 [] 로 해당 키로 직접 참조할 수 있다.
예를들어 string : int 형태로 값을 할당해야 하는 경우
map을 사용한다.
맵의 키와 value는 string, int 뿐 아닌 다양한 값이 들어갈 수 있다.
시간 복잡도
- 참조 : O(logn)
- 탐색 : O(logn)
- 삽입 / 삭제 : O(logn)
셋 (Set)
고유한 요소만을 저장하는 자료구조이다.
셋은 중복을 허용하지 않으며,
map 처럼 {key, value}로 집어넣지 않아도 되며
중복된 값은 제거된다.
map과 같이 자동 정렬된다.
시간복잡도
- 참조 : O(logn)
- 탐색 : O(logn)
- 삽입 / 삭제 : O(logn)
