[C++] STL Map 정리 + 사용법까지!
💚ref.
1. map 자료구조
key와 value가 서로 한 쌍(노드)을 이루는 레드-블랙 트리 형태의 자료구조이다.
데이터를 검색하거나 삽입/삭제하는데 $O(log N)$의 시간 복잡도를 가진다.
그림 출처: [위키백과] 레드-블랙 트리
👀info) 레드-블랙 트리 특징
이진트리가 균형이 맞지 않을 경우 검색 성능이 저하되는 문제를 해결하기 위해 고안된 자료구조이다.
이진트리에 색상을 추가해 자료구조의 균형을 잡는다.
언제 map 자료구조를 사용해야 할까?
- 많은 양의 데이터 정렬
- 빠르게 특정 데이터에 접근해야 함 (데이터 양과 시간 조건이 반비례)
- 삽입이나 제거가 빈번하지 않음
2. map 클래스
연관 컨테이너에 해당하는 표준 라이브러리로 각 원소가 key와 value 쌍을 가진다. key는 고유성을 가져 새 데이터를 삽입하려면 이전 데이터를 삭제해야 한다. 중복된 key가 필요할 경우 multimap 클래스를 사용하자.
각 원소들은 비교 함수를 통해 키 값을 기준으로 자동 정렬된다.
map 클래스를 사용하기 위해 헤더 파일 <map>을 선언한다.
map 변수 선언시 key와 value에 해당하는 자료형을 모두 지정해야 한다. 두 타입 모두 클래스를 지정할 수도 있다.
(eg. map<Class, int> mymap => Class를 key, int를 value로 하는 map 변수 mymap 선언)
값을 저장할 때 key와 value를 한 쌍으로 만드는 make_pair를 사용한다. (m.insert(make_pair(key, value)))
자료를 찾으려면 key을 입력해 해당하는 데이터를 받아야 한다. map에서 key를 찾지 못했다면 기본값 0을 출력한다.
key/value로 사용된 클래스 객체에 대한 데이터를 찾으려면 해당 클래스 내부에 오퍼레이터를 생성한다. map에서 오퍼레이터를 통해 객체 데이터를 바로 반환할 수 있다.
3. 멤버 함수
Iterator
| 함수명 | 기능 |
|---|---|
m.begin() |
m의 첫 번째 pair에 대한 이터레이터 반환 |
m.end() |
m의 마지막 pair에 대한 이터레이터 반환 |
(+ rbegin, rend, cbegin, cend, crbegin, crend)
Capacity
| 함수명 | 기능 |
|---|---|
m.empty() |
m이 빈 상태인지 확인 (bool) |
m.size() |
m의 크기 반환 |
m.max_size() |
m의 최대 길이 반환 |
Element access
| 함수명 | 기능 |
|---|---|
m.at(key)m[key] |
key에 대한 value 반환 |
Modifiers
| 함수명 | 기능 |
|---|---|
m.insert(make_pair(key, val))m.insert({key, val}) |
key와 value의 pair 삽입 |
m.erase(key) |
key를 검색해 pair쌍 삭제 |
m1.swap(m2) |
m1과 m2의 원소 교환 |
m.clear() |
m 초기화 |
m.emplace(key, val) |
m에 key와 val 생성자 원소 삽입 |
Operations
| 함수명 | 기능 |
|---|---|
m.find(key) |
key에 해당하는 이터레이터 반환 |
m.count(key) |
key에 해당하는 val 개수 반환일반 map의 경우 0과 1만 반환 가능 |
auto res = m.find(key)처럼 find를 통해 이터레이터를 받았다면 출력시 포인터 변수를 작성하자 ((*res).first/second).
👀info) at vs find
at 함수를 활용해 key에 대한 원소를 찾을 경우 map에서 pair 자체를 넘겨줘 바로 출력이 가능하다. (eg.m[key])
반면 find 함수는 pair에 대한 포인터를 이터레이터로 반환하므로, 역참조 연산자를 사용해 데이터에 접근해야 한다.
Leave a comment