[C++/STL]map, set

5. map

1) 정의

인덱스로 int가 아닌 다른 자료형을 사용할 수 있는 배열

(후에 사용법을 이해하기 편하도록 '배열'이라고 했지만, map의 내부적인 구조는 각 노드가 key와 value의 쌍으로 이루어진 '트리'입니다. 특히 검색, 삽입, 삭제 등의 속도를 빠르게 하기 위해 균형 이진 트리 중의 하나인 '레드 블랙 트리'로 구현되어 있습니다. 검색 속도가 특히 빠른데 이는 key를 기준으로 정렬된 상태이기 때문입니다.)

2) 용도

연관 있는 두 값을 함께 묶어서 관리하되, 검색을 빠르게 하고 싶은 경우

(Ex. 만약 SNS상 사람들의 친구 관계를 그래프를 이용해 나타내고, 이 그래프에 여러가지 알고리즘들을 적용해 멋진 일들을 하고 싶다고 합시다. 일반적인 경우라면, 사람을 정점으로, 사람들 간의 친구 관계를 간선으로 나타내게 되겠죠?? 문제는! 그래프의 연결관계를 배열에 저장하려면, 각 정점을 사람 이름으로 나타내는 것이 아니라 번호로 나타내야 한다는 점입니다. 그러려면, 어떤 과정이 필요할까요?? 사람의 이름을 정점의 번호로 변환해주는 과정이 필요하겠죠?? 이 때, map을 이용해 문제를 해결할 수 있습니다. key를 사람의 이름으로, value를 정점 번호로 묶어서 저장해놓는다면 나중에 몇 번 정점에 해당하는지 알고 싶은 사람의 이름이 있을 때, 이름을 검색해 해당 정점 번호를 빠르게 알아낼 수 있습니다.

3) 사용법

map을 사용하기 위해선, <map>을 include 해야 합니다. map은 unique(중복 불가)한 key와 value쌍으로 이루어진 노드의 트리라고 할 수 있습니다. 그렇다면, 같은 key값을 갖는 노드를 추가하면 어떻게 될까요?? 해당 key값을 갖고 있던 원래 노드의 value값에 덮어씌워지게 됩니다. (Ex. (2,3)인 노드A가 이미 존재하는 map에 (2,4)인 노드B를 추가하려는 경우, 노드A의 value가 4로 덮어씌워지고, map에는 key가 2인 노드는 하나만 존재하게 됩니다.)

map은 요소에 접근할 때, 반복자(iterator)를 이용하는 방식과 인덱스(key)를 이용하는 방식, 두 가지 방식을 이용할 수 있습니다.

편의상 멤버 함수의 적용 대상이 되는 map을 m이라고 부르도록 하겠습니다.

멤버 함수	기능
m.size()	m의 노드 개수를 리턴
m.empty()	m의 사이즈가 0인지 아닌지를 확인
m.begin()	m의 첫 번째 원소를 가리키는 iterator 리턴
m.end()	m의 마지막 원소를 가리키는 iterator 리턴
m[k] = v	m에 key가 k이고, value가 v인 노드 추가
m.insert(make_pair(k,v))
m.erase(k)	m에서 key가 k인 노드 삭제
m.find(k)	m에서 key가 k인 노드를 찾아, 해당 노드를 가리키는 iterator 리턴  (key가 k인 노드가 존재하지 않는 경우, m의 마지막 원소를 가리키는 iterator 리턴)
m.count(k)	m에서 key가 k인 노드의 개수를 리턴

cf) insert와 erase함수의 경우, 파라미터로 값 자체가 아닌 iterator를 넘겨주는 방식을 사용할 수 있습니다. iterator를 넘겨주는 방식을 통해, array(배열)나 vector(벡터)에 있는 모든 값들을 추가하거나, map의 첫 번째 원소나 마지막 원소를 삭제할 수도 있습니다.

ex1) vector v에 있는 모든 값 추가    ->    m.insert(v.begin(), v.end())

ex2) map의 첫 번째 원소 삭제         ->    m.erase(m.begin())

 

4) 예제

map은 다른 컨테이너에 비해, iterator의 사용이 잦은 컨테이너입니다. iterator의 사용법을 잘 모른다면, 아래의 예제를 통해 익혀보도록 합시다.

map<char,int> m;
map<char,int>::iterator it;
 
m['B'] = 2;                        //m : (B,2)
m.insert(make_pair('A',1));        //m : (A,1) (B,2)
m['C'] = 3;                        //m : (A,1) (B,2) (C,3)
 
m.erase('A');                      //m : (B,2) (C,3)
 
 
//m전체를 순회하며 key와 value 출력
for(it = m.begin(); it != m.end(); it++)
    cout << it->first << ' ' << it->second << '\n';
 
if(m.find('B') != m.end()) 
    cout << "key값이 B인 노드가 존재합니다." << '\n';
else
    cout << "key값이 B인 노드가 존재하지 않습니다." << '\n';
 

6. set

1) 정의

key만 있는 map 혹은 정렬된 집합

(set은 map과 구조가 매우 유사합니다. 단, key만 있고 value가 없는 map이라고 생각할 수 있습니다. 따라서, 사용법도 map과 크게 다르지 않습니다. 정렬된 집합 이라고 정의한 이유는 set이 갖는 값들이 중복을 허락하지 않고 정렬되어 있기 때문입니다. (위의 map에서 설명한 key값의 특성)

2) 용도

특정 값에 대해 검색을 빠르게 하고 싶은 경우

3) 사용법

set을 사용하기 위해선, <set>을 include 해야 합니다. 기본적인 사용법은 map과 매우 유사합니다.

편의상 멤버 함수의 적용 대상이 되는 set을 s라고 부르도록 하겠습니다.

멤버 함수	기능
s.size()	s의 노드 개수를 리턴
s.empty()	s의 사이즈가 0인지 아닌지를 확인
s.begin()	s의 첫 번째 원소를 가리키는 iterator 리턴
s.end()	s의 마지막 원소를 가리키는 iterator 리턴
s.insert(k)	s에 값이 k인 노드 추가
s.erase(k)	s에서 값이 k인 노드 삭제
s.find(k)	s에서 값이 k인 노드를 찾아, 해당 노드를 가리키는 iterator 리턴  (값이 k인 노드가 존재하지 않는 경우, s의 마지막 원소를 가리키는 iterator 리턴)
s.count(k)	s에서 값이 k인 노드의 개수를 리턴

4) 예제

set<int> s;
set<int>::iterator it;
 
s.insert(4);               //s : 4
s.insert(1):               //s : 1 4
s.insert(2);               //s : 1 2 4
 
vector<int> v;
v.push_back(3);            //v : 3
v.push_back(5);            //v : 3 5
v.push_back(6);            //v : 3 5 6
 
s.insert(v.begin(), v.end());        //s : 1 2 3 4 5 6
 
s.erase(4);                //s : 1 2 3 5 6
s.erase(s.begin());        //s : 2 3 5 6 
 
//지울 원소를 입력받음
int toErase;
scanf("%d", &toErase);
 
it = s.find(toErase);
 
//지울 원소가 존재하는 원소일 때만 지움
if(it != s.end())
    s.erase(it);