[c++] map과 set

[map]

• 자료를 저장하고 키를 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 자료구조
• key에 대응하는 value도 같이 저장하는 컨테이너
• #include <map>을 해야 사용 가능

 

• 중복 저장이 안됨
• 전체 조회 시 정렬된 상태로 출력 됨
• 추가, 탐색, 삭제 시간 복잡도는 O(log n)
  => map은 균형 이진 검색 트리로 이루어져 있기 때문!

 

 

map 사용법

// map 생성 & 초기화
map<int, string> book = { {1, "봄"}, {2, "여름"}, {3, "가을"} };
map<int, int, greater<int>> map; // 내림차순으로 정렬

// 삽입1 (pair 객체 사용)
book.insert(make_pair(4, "겨울"));

// 삽입2 (operaotr 사용)
book[1] = "봄";

// 전체 조회1 (반복자 사용)
for (auto iter = book.begin(); iter != book.end(); iter++)
{
	cout << "Key : " << iter->first << endl;
	cout << "Value : " << iter->second << endl;
}

// 전체 조회2 (범위 기반 for문 사용)
for (auto a : book)
{
	cout << "Key : " << a.first << endl;
	cout << "Value : " << a.second << endl;
}

// 특정 key의 value 조회 (조회되지 않는다면, book.end()가 출력됨)
cout << "Value : " << book.find(1)->second << endl;

// 특정 key의 value 조회 (operator 사용)
cout << "Value : " << book[1] << endl;

// 삭제1 (key 값)
book.erase(1);

// 삭제2 (map의 모든 요소 삭제)
book.erase(book.begin(), book.end());
book.clear();

 

 

[해시 테이블]

• 다른 탐색 방법들은 키 값 비교하여 항목에 접근
• 해시 테이블은 키 값의 연산에 의해 직접 접근이 가능한 구조

 

 

[배열과 다른 점]

• 배열은 인덱스를 통해 주소에 접근하지만 해시 테이블은 키를 사용하여 메모리에 접근하여 키가 인덱스로 변환된다.
  (키는 숫자, 문자열 모두 가능)

해싱	배열
특정 데이터가 들어온 순서 상관 없이 삽입, 삭제, 검색이 자주 발생하는 경우에 사용하기 좋음	index 기반으로 데이터간의 순서가 확실하게 매겨져 있음
순서 상관 없이 각각의 데이터가 자주 들어오고 나가는 경우에 해싱이 꼭 필요!

 

[충돌과 오버플로우]

• 충돌 (collision) : 어떤 키 값으로 도출된 주소에 이미 다른 키가 자리함
  - 해시 충돌이 일어나면 데이터의 삽입, 삭제, 검색을 원하는 대로 바로 할 수 없고 시간이 걸림
  - 충돌 수를 줄이기 위해 해시 테이블은 일반적으로 들어갈 최대 데이터의 3~4배 정도의 크기로 설정함
  
  
• 오버플로우 : 충돌이 슬롯 수보다 많이 발생하는 것

 

충돌 해결 방법

• 체이닝 (Chaining)
  - 같은 자리에서 충돌이 일어난 원소들은 하나씩의 연결 리스트로 관리함
  - 테이블의 각 원소 (table[i])는 연결 리스트 하나씩을 링크함

 

 

• 개방 주소 방법 (Open Addressing)
  - 주어진 배열 안에서 해결 (선형 탐색, 이차원 탐색, 더블 해싱)

 

[unordered_map]

• 자료를 저장하고 키를 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 자료 구조
• key에 대응하는 value도 같이 저장하는 컨테이너
• #include <unordered_map>을 해야 사용 가능
• 중복 저장 안됨
• 전체 조회 시 정렬이 안된 상태로 출력 됨
• 추가, 탐색, 삭제 시간 복잡도는 O(1)
  -> 해시 테이블로 구현되있기 때문!

 

[set]

• key라 불리는 원소의 집합으로 이루어짐
• #include <set>을 해야 사용 가능
• 균형 이진 트리(레드블랙트리)로 구현됨
  - 중복 삽입 불가
  - 데이터 정렬
  - 연산 시간 복잡도 O(log n)

 

[unordered_set]

• #include <unordered_set>을 해야 사용 가능
• 해시 테이블로 구현됨
  - 정렬 x
  - 시간 복잡도 O(1)

 

 

[정리]

	Key	Value	Key 정렬 여부	탐색 시간 복잡도
map	O	O	O	O(log n)
unorderd_map	O	O	X	O(1)
set	O	X	O	O(log n)
unorderd_set	O	X	X	O(1)

•