#include<map>
map은 c++ STL 컨테이너이다.
균형이진트리로 구성되어 있으며, 각 노드는 key와 value 값을 갖는다.
한 트리에는 동일한 key 값을 가진 노드가 존재할 수 없기에, 중복을 허용하지 않는 특징이 있다.
이진트리로 구성되었기 때문에 검색, 삽입, 삭제에 O(log n)의 시간 복잡도를 갖는다.
key 값을 기준으로 오름차순 정렬이 되며, 값이 삽입 될 때마다 자동으로 정렬이 된다.
value 값은 수정이 가능하지만, key 값은 수정이 불가능하다.
map<key_type, value_type> m;
key와 value의 type을 명시하며 선언하게 된다.
key와 value의 type에는 int 뿐 아니라 string, bool 등의 형태 또한 가능하다.
#include <map>
헤더를 선언해야만 사용할 수 있다.
사용 빈도가 잦은 함수들 위주로 정리하였다.
m.begin(); // 첫 번째 노드를 가리키는 반복자 반환
m.end(); // 마지막 노드를 가리키는 반복자 반환
m.clear(); // 전체 노드를 삭제
m.empty(); // 컨테이너가 비어있으면 true 반환
m.size(); // 컨테이너에 있는 요소의 수를 반환
m.insert();
m.erase;
m.find();
새로운 노드를 삽입하는 함수이다.
m.insert(pair<int,int>(30,40));
m.insert({30,40});
m[30] = 40;
위 코드들은 key가 30이고 value가 40인 노드를 삽입하는 코드이다.
insert() 함수의 경우 앞에 나온 값이 key 값이고, [] operator의 경우 괄호 안의 값이 key 값이다.
하지만 마지막 줄은 약간의 차이점이 있다.
insert() 함수를 사용할 경우, 이미 존재하는 key 값을 삽입하려고 하면 오류가 뜨는 반면, [] operator을 이용한 경우 30이라는 key 값이 이미 존재하면 그 노드의 value 값을 40으로 변경한다.
erase(iter); // 반복자가 가리키는 노드를 삭제한다.
erase(start,end); // [start, end)범위의 노드를 삭제한다.
erase(key); // key 값을 가진 노드를 삭제한다.
find(key);
key 값을 가진 노드를 찾아, 그 노드를 가리키는 반복자를 반환한다.
key 값을 가진 노드가 없으면 end()와 같은 반복자를 반환한다.
m.find(3)->first
m.find(3)->second
위와 같은 방식으로 사용할 수 있다.