[C++ STL] Map 사용법 이모저모

---

최근에 코테 주 언어를 모종의 이유로 C++로 바꾸게 되었다.

C++에서 Map자료 구조 활용의 이모저모를 정리해보았다.

Map이 뭔데?

 Map은 Key-value 형태로 데이터를 정리하는데 사용된다. unordered_map과의 차이점은 key를 기준으로 정렬을 내부적으로 시킨다는 것이다. 좀 더 깊이 이야기해보자면 Map은 C++내부적으로 Red-Black Tree로 구현되어 있기 때문에 Search, Insert, Delete에서 최악의 시간의 경우 O(logN)의 시간이 보장되는 무시무시한 놈이다. 대학교 2학년때 이거 구현한다고 진짜 밤날샌거 생각하면 진절머리가 난다.

 

문법

1. 정의

std::map <key의 자료형, value의 자료형> 변수명;

로 선언하게 된다. 자료형은 단순하게 int, string등이 들어갈수도 있고 새롭게 정의한 구조체의 형태의 자료형도 들어갈 수 있기 때문에 linked list같은 것의 node의 pointer를 value로 가진다면 linked list의 node 검색을 index만 안다면 O(1)의 형태로 진행할 수 있다.

 

2. INSERT

//컴파일러가 C++11을 지원한다면
변수명.insert({key값, value값});

//그게 아니면
변수명.insert(pair<key 자료형, value 자료형>(key값, value값));

C++11부터 Uniform initialization syntax가 지원되기 때문에 첫번째것처럼 쓸 수 있지만 그렇지 않다면 두번째 것처럼 써야한다.

 

3. DELETE

Delete는 key를 기준으로 삭제가 가능하다.

변수명.erase(key);

Value를 기준으로 삭제하고 싶다면 어떻게 할까?

int delete_key;
for(auto it = map변수.begin(); it != map변수.end(); ++pair변수){
    if(pair->second == "원하는 값"){
        delete_key = it->first;
        break;
    }
}
map변수.erase(delete_key);

이것보다 훨씬 효율적이고 멋있는 방법이 많겠지만 내 머리로는 이게 젤 편한거 같다.

 

4.SELECT

(1) key를 아는 경우

key를 아는 경우는 매우 편하다.

auto it = map변수.find(찾고자하는 pair의 key);
int key = it->key;
int value = it->value;

(2) key의 범위만 아는 경우

이것도 사실 꽤 편하다. 그동안 사람들이 C++를 편하게 만들려고 얼마나 노력했는지 느껴지는 부분이다.

auto lowerboundPair = map자료형.lower_bound(최소값);
auto upperboundPair = map자료형.upper_bound(최대값);

각 문법들의 활용 예제를 보면서 기능을 알아보자.

즉, upper_bound는 주어진 key값보다 큰 값을 key로 가지는 pair변수를 반환하는 반면 lower_bound는 주어진 key값이 있으면 그 값보다 같거나 큰 값을 key로 가지는 pair변수를 반환해준다.

 

5. 기타

(1) 순회하면서 key, value 출력하고 싶어!

for(auto it = map변수.begin(); it != end(); ++it){
    int key = it->first;
    int value = it->second;
}

(2) 역방향으로 순회하고 싶어!

그렇다면 다음과 같은 방식을 사용할 수 있다.

for(auto it = map변수.rbegin(); it != rend(); ++it){
	...역방향 순회
}

(3) 변수안에 있는거 다 삭제하고 싶어!

map변수.clear();

 

나중에 더 알게 되는 것이 있으면 차곡차곡 모아가지 않을까 싶다. python보고 싶다...

 

 

---

출처

- ChatGPT + NotionAI

- https://chanhuiseok.github.io/posts/algo-55/

알고리즘 - c++ lower_bound, upper_bound 활용하기

---

긴 글 읽어주셔서 감사합니다.

 

틀린 부분이 있으면 댓글을 달아주시면 감사하겠습니다.

 

📧 : realhwan1202@gmail.com

🔗 : https://github.com/RicardoKim