[C++/STL] 셋(Set), 맵(Map)

 

 

1. 셋(Set)

 

셋(Set) 이란?

 

 - 완전 이진 트리 형태로 정렬되어 있기 때문에 빠른 검색 속도를 보장한다.

 

 - 원소 삽입, 삭제, 탐색 등의 연산은 O(logn)을 보장한다.

 

 - 중복된 원소는 추가할 수 없다.

 

---

 

셋 사용 방법

 

 - 셋 선언

// 헤더 선언 필요
#include <set>

// int 자료형을 저장하는 셋 선언
set<int> s;

 

 - 원소 추가

// 원소 n 추가
s.insert(n);

 

 - 원소 탐색

// 원소 n 찾기, 해당 원소가 존재하면 해당 주소 반환, 없으면 s.end() 반환.
s.find(n);

 

 - 원소 제거

// 값이 n인 원소 제거
s.erase(n);

// 모든 원소 제거
s.clear();

 

 - 기타

// set의 크기(원소의 개수) 반환
s.size();

 

---

 

2. 맵(Map)

 

맵(Map) 이란?

 

 - 키와 값 형태의 데이터를 보관하는 딕셔너리형 자료 구조.

 

 - 원소 삽입, 삭제, 탐색 등의 연산은 O(logn)을 보장한다.

 

 - 중복된 원소는 추가할 수 없다.

 

---

 

 

맵 사용 방법

 

 - 맵 선언

// 헤더 선언 필요
#include <map>

// int, string 자료형을 저장하는 맵 선언
map<int, string> m;

 

 - 원소 추가

// 원소 추가(insert)
m.insert(1, "test1");

// 원소 추가(인덱스)
// 해당 키 값이 존재하지 않으면 원소가 추가되고, 존재하면 값이 수정된다.
m[2] = "test2";

 

 - 원소 조회

// 원소 찾기
// 해당 key가 존재하면 iterator 반환. 없으면 m.end() 반환.
m.find(key);

auto mf = m.find(3);
cout << mf->first << " : " << mf->second << endl;

 

 - 원소 제거

// key에 해당하는 원소 제거
m.erase(key);

// 모든 원소 제거
m.clear();

 

 - 기타

// 저장된 원소 개수 출력
m.size();

 

---

 

3. 멀티 셋, 멀티 맵

 

 - 셋과 맵은 중복 key를 허용하지 않지만, 멀티 셋과 멀티 맵은 중복 key를 허용한다.

 

 - 선언 방법

// 헤더 선언 필요
#include<set>
#include<map>

// 사용법은 일반 셋, 맵과 동일하다.
multiset<int> ms;
multimap<int, int> mm;

 

---

 

 

4. unordered_set, unordered_map

 

 - 원소들이 순서대로 정렬되어 들어가지 않는다.

 

 - 삽입, 삭제, 조회가 평균 O(1)를 보장한다.(최악의 경우는 O(n))

 

 - 해시 함수를 이용하여 저장 공간을 결정한다.

 

 - 너무 빈번하게 자료를 삽입, 삭제하지 않고 많은 자료 저장과 빠른 검색 속도를 사용할 때 사용한다.

 

 - 선언 방법

// 헤더 선언 필요
#include<unordered_set>
#include<unordered_map>

// 사용 방법은 set, map과 동일하다
unordered_set<int> us;
unordered_map<int, int> um;