[C++] 자료구조 :: STL Map & STL Set

chooha·2024년 12월 31일

자료구조

목록 보기

2/2

< Map >

1. 정의

각 노드가 key와 value쌍으로 이루어진 트리
특히, 중복을 허용하지 않음
C++ map의 내부 구현은 레드 블랙 트리로 구성되어 있음

💡 레드 블랙 트리
: 자가 균형 이진 탐색 트리
삽입과 삭제가 일어나는 경우에 자동으로 그 높이를 작게 유지하는 이진 탐색 트리

높이를 작게 유지하는 이유
: 연산 과정에서 트리의 높이가 한쪽으로 치우치는 것을 막기 위함

시간 복잡도
: 삽입, 삭제, 검색 모두 O(logn)

2. 생성

#include <map>

std::map<string, int> m;

기본 구조는 map<key type, value type> 이름;

3. Map 정렬

map은 자료를 저장할 때 내부에서 자동으로 정렬함
key를 기준으로 오름차순으로 정렬
➕ 만약 내림차순으로 정렬하고 싶은 경우
map<int, int, greater> map1;
➕ 만약 정렬할 필요가 없는 경우
unordered_map을 사용

4. 멤버 함수

▸ 원소 추가

insert()
```
map<string, int> myMap;
 myMap.insert(pair<string, int>("apple", 5));
 myMap.insert(make_pair("banana", 3));
 myMap.insert({"orange", 4});

 auto result = myMap.insert({"apple", 10}); // 중복 삽입 시도 -> 추가 x

 if(!result.second)
 {
     cout << "키가 이미 존재합니다!" << endl;
 }
 else
 {
     cout << "키 삽입 성공!" << endl;
 }
```
원소를 추가할 때는 키-값 쌍을 pair 객체로 전달하여 추가
또한, insert 함수는 삽입 작업이 성공했는지 실패했는지를 나타내는 pair<iterator, bool>를 반환
여기서 bool값이 true이면 새로운 요소가 삽입된 것, false이면 중복된 키 때문에 삽입이 무시된 것

💡 emplace()
: emplace_back과 유사한 개념이지만, emplace는 키-값 쌍을 갖는 map이나 요소의 유니크한 값을 갖는 set과 같은 연관 컨테이너에 요소를 추가할 때 사용 (emplace_back은 주로 vector, deque, list 같은 시퀀스 컨테이너의 끝에 요소를 추가할 때 사용)
push_back과 emplace_back의 관계와 같아 복사나 이동 생성자의 비용이 큰 객체를 컨테이너에 추가할 때 효과적이지만, insert()와 달리 중복된 키 값도 추가됨
[키]로 값에 접근하여 원소 추가/수정
```
myMap["apple"] = 5;
 myMap["banana"] = 3;
```
map[키]=값 형태를 사용하면 해당 키가 이미 map에 존재하는 경우 그 키의 값을 업데이트하고, 키가 존재하지 않는 경우 새로운 키-값 쌍을 map에 추가함

▸ 원소 삭제

erase()

myMap.erase(myMap.begin()+2); // 특정 위치의 원소 삭제
 myMap.erase(myMap.begin(), myMap.begin()+1); // 특정 구간의 원소들 삭제
 myMap.erase("banana"); // 특정 key값의 원소 삭제

clear()
```
myMap.clear();
```

▸ 원소 탐색

인덱스 기반 반복문

for(auto iter = myMap.begin(); iter != myMap.end(); iter++)
{
    cout << "[" << iter->first << ", " << iter->second << "]\n";
    // [키, 값] 출력
}

iterator를 이용해 원소에 접근할 수 있음
first는 key 값을 second는 value 값을 나타냄

범위 기반 반복문

for(auto iter : myMap)
{
    cout << "[" << iter->first << ", " << iter->second << "]\n";
      // [키, 값] 출력
}

▸ 원소 검색

if(myMap.find("apple") != myMap.end())
{
	cout << "find!\n";
}
else
{
	cout << "not exist!\n";
}

데이터를 끝까지 찾지 못했을 경우, iterator는 map.end()를 반환

< Set >

1. 정의

key를 기준으로 원소를 정렬 상태로 저장 (map과 달리 value가 따로 있지 않음)

💡 연관 컨테이너 (Associative Container) & 연속 컨테이너 (Sequential Container)

map과 set과 같은 자료구조는 연관 컨테이너

array, vector, list와 같은 자료구조는 연속 컨테이너

연관 컨테이너는 찾고자 하는 원소를 빨리 찾기 위해 사용