[C++ STL] Map 사용설명서

안녕하세요! 코딩하는 경제학도 쏘코입니다.

 

작년 2학기에 자료구조 수업을 들으면서 여러 자료구조를 짜면서 STL의 위대함을 느꼈습니다.

여러 알고리즘을 보다보니 다양한 STL들에 대해서도 간접적으로나마 알게 되었죠.

 

하지만 Map.. 이녀석은 자료구조 시간에 등장하지 않았던 친구였습니다.

하필 프로그래머스 고득점 Kit의 첫 주제가 해시여서 어쩔 수 없이 정보 없이 맞닥뜨릴 수 밖에 없었습니다.

(그나마 익숙한 스택/큐 문제를 먼저 풀까 생각했지만 뭔가 지는 느낌이 들어서 그만.. ㅋㅋㅋㅋ)

 

지금에 와서야 어느 정도 map에 대한 사용법을 익혔지만, 처음에는 분명 당황할 수밖에 없었습니다. 

그리고 느낀 것은 STL에 대한 공부도 분명 필요하다는 것이었습니다.

그래서 PS를 하면서 마주치는 다양한 STL, 혹은 자료구조에 대해서 정리를 해보도록 하겠습니다.

 

STL이 무엇인지에 대해서는 이전 포스팅에서 이미 이전 포스팅에서 남겼으니 확인하시면 도움이 조금이나마 되실겁니다!

 

[C++ STL] STL이 뭘까?

 

목차

 

---

0. Map..이 뭔데? 지도?

map을 이해하기 위해서는 먼저 set에 대한 이해가 필요합니다.

set은 key라고 불리는 원소들의 집합으로 이루어진 컨테이너입니다.

key값의 가장 중요한 특징은 중복이 허용되지 않는다는 점입니다.

또한 이 set은 key값의 순서대로 정렬(inorder traversal 방식)이 되는 특징을 가지고 있습니다.

복잡해 보일 수 있지만, 정렬되고 중복이 없다고만 이해하셔도 충분합니다!

 

map container는 set에 존재하는 key값에 value값이 추가된 버전입니다. 

map 역시 중복을 허용하지 않습니다. 다만 key값에 한해서 중복을 허용하지 않고, value값은 중복이 가능합니다.

 

다시 돌아와서 map은 key값과 value값으로 이루어져있으며, 이게 pair 형태(순서쌍 형태)로 저장됩니다. 파이썬에서는 dictionary 형태와 비슷하겠네요!

 

set과 마찬가지로 자동으로 오름차순으로 정렬이 되고, 동적할당됩니다.

형태는 노드 기반의 균형 이진 트리 구조로 되어있습니다. (더 자세하게는 레드-블랙 이진트리!)

 

Red-Black tree의 예 / 출처 : https://en.wikipedia.org/wiki/Red-black_tree

 

※ Map의 특징 정리

 

• key값과 value값이 pair형태로 구성되어 있습니다.
• 자동으로 오름차순으로 정렬됩니다. (unordered_map의 경우 정렬이 되지 않습니다!)
• key값은 중복이 되지 않고, value값은 중복이 됩니다. (multimap의 경우 key값도 중복이 가능합니다!)
• 동적할당합니다. (필요에 따라 메모리를 사용합니다)

map의 예시, key값에 따라 정렬이 된 모습!

---

1. Map의 사용법

먼저 사용을 위해서 헤더에 #include <map>을 해 줘야 합니다.

(편하게 사용하시려면 using namespace std;를 include 밑에 넣어줍니다)

 

그 다음으로 map container는 map<key, value> 변수이름; 의 형식으로 사용할 수 있습니다.

key값과 value값에는 다양한 값들이 들어갈 수 있습니다.

 

map<int, int> map1;

map<int, string> map2;

map<int, string> map3;

map<string, int> map4;

​​

이제 선언을 했으면 이 map에 요소들을 넣어줘야 하지 않겠습니까!

넣어주기 위해서 std::map::Insert의 기본 형식을 살펴보면 다음과 같습니다.

​

 

pair<iterator,bool> insert (const value_type& val);

 

 

val값에는 pair 객체가 들어가야 합니다. 즉, insert는 pair 객체를 인자로 받아야 한다는 말입니다.

key값과 value값은 쌍을 이뤄야 하기 때문이죠.

아래와 같은 방식으로 다양하게 사용할 수 있습니다. map3이 조금 독특하긴 한데, iterator를 사용한 방법입니다.

​

 

map1.insert({3,5});

map2.insert(pair<int, string>(1,"나나콘"));

map3.insert(map2.begin(), map2.end()); // map2를 처음부터 끝까지 복사

map4.insert(make_pair("아부지",4));

​

​

위의 기본 형식을 자세히 보시면 아실 수 있지만

결과값으로 iterator(위치)값과 bool(제대로 삽입되었는지)값을 가진 pair를 리턴​해주기 때문에

이걸 써먹을 수도 있습니다.

 

range를 참고!! / 출처 : https://www.cplusplus.com/reference/map/map/insert/

​

auto itr = map2.find(1);

​

이렇게 하면 방금 넣은 pair값인 (1,"나나콘")에 대한 <iterator, bool>이 추출됩니다.

​

가져온 반복자 위치에 있는 친구의 value값을 바꿔주기 위해서 itr->second = "프링글스";

하면 key가 1인 값의 value가 나나콘에서 프링글스로 바뀌게 되는 것이죠.

 

처음엔 iterator에 대한 이해가 부족하다면 이것도 이해가 잘 안될 수 있는데, 차근차근 반복해서 읽어보다보면 언젠가 쉽게 이해하실 수 있을겁니다!!

 

---

2. Map의 멤버함수

iter, start, end 세 개의 반복자를 선언하며, k와 l은 일반 원소입니다!

멤버	설명
begin()	첫 번째 원소의 랜덤 접근 반복자를 반환
end()	마지막 원소 다음의 반복자를 반환
empty()	저장 하고 있는 요소가 없으면(비어있으면) True 반환
clear()	저장하고 있는 모든 원소를 삭제
erase(iter), erase(start,end)	특정 위치의 원소나 지정 범위의 원소들을 삭제 후 다음 원소를 가리키는 반복자를 반환
find(k)	key와 연관된 원소의 반복자 반환 (없으면 end()와 같은 반복자 반환)
insert(l,k), insert(iter,k)	l이라는 key, k라는 value를 가진 pair을 추가, iter 위치에 k라는 원소 추가 (위에서 설명함!)
upper_bound(k)	지정한 key 요소를 가지고 있다면 해당 위치의 다음 위치의 반복자를 반환
lower_bound(k)	지정한 key의 요소를 가지고 있다면 해당 위치의 반복자를 반환
rbegin()	역방향으로 첫 번째 원소의 반복자를 반환
rend()	역방향으로 마지막 원소 다음의 반복자를 반환
size()	원소의 개수를 반환
operator[]	지정한 key 값으로 원소 추가 및 접근

 

여기서 마지막에 위치한 operator[]에 대해 궁금해하실 수 있습니다.

​

1이라는 key값을 가진 10이라는 원소를 map1에 넣으려고 한다면

이것은 insert(l,k), insert(iter,k)를 사용하는 방법도 있지만

operator[]을 사용할 수도 있습니다.

​

map1.insert(1,10);

map1[1] = 10;

​

두 가지 방법이 모두 가능하다는 뜻입니다. 역시 Python의 Dictionary 형식을 안다면 매우 쉽게 응용할 수 있습니다.

(map을 사용할 때 매우 많이 사용하게 될겁니다 크크크)

​

사용할 때 가장 주의해야 할 점은 find(k)에서 빨간색으로 강조해놓은 (없으면 end()와 같은 반복자 반환) 입니다.

​

해시 알고리즘 문제를 풀면서, 혹은 map 컨테이너를 사용하면서

end()가 맨 끝 값이 아니라 맨 끝 값에서 그 다음 값을 나타내는 반복자를 반환한다는 것만 알고 있다면

조금 더 수월하게 다른 코드들을 이해하거나, 본인이 map(혹은 연관 컨테이너인 multimap, set, multiset 등)을 사용할 때 구조를 이해하면서 사용할 수 있을 것입니다.

​

​

※ 실제 알고리즘 퀴즈에서 사용 예시

​

for(auto elem : completion)
{
    if(strMap.end() == strMap.find(elem))
        strMap.insert(make_pair(elem, 1));
    else
        strMap[elem]++;
}
// end와 find가 같은 값을 가리킨다면(nullptr) -> map에서 원소(key)를 찾지 못했다면
// strMap에 {elem,1}라는 pair 형태의 원소를 넣고
// end와 find가 같은 값을 가리키지 않는다면 -> map에서 원소(key)를 찾았다면
// 그 elem의 value값을 1 더해준다

​

또한 원소들을 출력하고 싶다면 아래와 같은 방식으로 출력할 수 있습니다.

(기본 틀은 이렇고 출력 방법은 자기 마음대로 만들 수 있습니다!!)

 

for(iter = m.begin(); iter != m.end(); iter++)
{   
    cout << "[" << iter->first << ", " << iter->second << "]" << " ";
}

---

3. 참고자료

en.cppreference.com/w/cpp/container/map/insert

std::map<key,t,compare,allocator>::insert - cppreference.com</key,t,compare,allocator>

www.cplusplus.com/reference/map/map/

map - C++ Reference

www.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS9990721111

About STL : C++ STL 프로그래밍(7)-맵(Map)