[ComputerScience] c++의 map과 set

이 게시글은

서울대학교 데이터사이언스대학원

조요한 교수님의

데이터사이언스 응용을 위한 컴퓨팅 강의를

학습을 위해 재구성하였습니다.

---

저번시간엔 c++의 list에 대해서 정리해보았고

오늘은 map과 set 대해서 정리해보려한다

 

 

Map

 

 

map은 python의 dict와 비슷하다고 볼 수 있는데

key-value가 서로 associate되어있는 구조이다

 

key들은 모두 unique하며

각 element들은 key들의 ascending order로

sort 되어있다

 

hash table과는 완전히 다른 구조이다

 

 

map은 내부 구조로

balanced binary search tree를 갖고있다

 

각 node들은 Key-value pair인

std::pair 오브젝트로 구현되어있다

 

balance tree이기 때문에

tree의 차수가 계속해서 최소가 되도록 유지시킨다

 

 

 

map의 초기화 방식이다

 

#include <map>을 헤더에 정의해준다

 

key와 value의 데이터타입을

반드시 선언해줘야한다

 

빈 map을 먼저 선언할 수도 있고

선언과 동시에 데이터를 넣어줄 수도 있다

 

 

 

map에 요소를 넣는 방법이다

insert 메소드를 사용하거나

[] operator를 사용할 수 있다

 

insert를 사용할 경우

pair로 넣어줘야하기 때문에

make_pair("Charlie", 40)으로 넣어주거나

{"Alice", 30}과 같이

pair로 만들어서 넣어줘야한다

 

[] operator를 사용할 땐

ageMap["Alice"] = 30

과 같은 방법으로 해주면 된다

 

그럼 기존에 있는 Key에 대해서

insert와 [] operator는 어떻게 작용할까?

insert 메소드는 기존에 있는 Key로

새로운 value가 들어오면 그걸 무시해버린다

 

따라서 이미 Alice라는 key가 있는데

ageMap.insert({"Alice", 35}를

실행시켜주면 35는 무시되고

Alice의 value는 그대로 30이다

 

하지만 ageMap["Alice"] = 35로해주면

Alice의 value는 35로 업데이트된다

 

 

map에서 찾고자하는 key를 찾는 법이다

 

find 메소드를 사용하면 되는데

find(key)를 실행시켜주면된다

 

찾고자하는 key가 존재하면

해당 iterator를 반환하고

만약 key가 존재하지않으면

map의 end()값을 가져온다

 

 

 

map의 key를 지우는 방법이다

그냥 erase(key)를 해주면 된다

 

만약 존재하지 않는 key를

erase의 parameter로 넘겨도

에러뜨지않고 그냥 무시된다

 

 

map을 iteration하는 방법이다

for문이나 iterator 두가지 모두 가능하다

 

for문으로 할 경우

각 요소들은 pair이기 때문에

pair.first가 key

pair.second가 value가 된다

 

iterator로 접근할 경우

it->first

it->second

와 같은 방식으로 접근해줘야한다

 

 

map에서 쓸 수 있는 메소드들이다

---

set

 

set은 unique한 element들의 모음이다

내부적으로는 map과 비슷하지만 key만 갖고있는 느낌이다

sorting이 되어있고

map과 마찬가지로 내부적으로 binary search tree 구조를 갖고있다

 

 

set의 초기화방법이다

요소들의 데이터 타입을 정의해줘야한다

 

 

insertion, search, deletion

모두 다른 container들과 유사하다

 

insert, erase로 추가 혹은 제거할 수 있고

찾고싶은 element를 find해주면

만약 찾으면 찾은 요소의 Iterator를

찾지못하면 end를 반환한다

 

 

set의 iteration도

다른 container들의 방식과 비슷하다

 

for문으로 하거나

iterator로 해줄 수 있다

---

 

python과 c++을 비교한 표이다