STL - map

Jaedup·2023년 3월 20일
0

stl

목록 보기
1/1

map

#include<map>

map은 c++ STL 컨테이너이다.

  • STL 컨테이너에는 vector, queue, stack, tree 등이 있다.

균형이진트리로 구성되어 있으며, 각 노드는 key와 value 값을 갖는다.

한 트리에는 동일한 key 값을 가진 노드가 존재할 수 없기에, 중복을 허용하지 않는 특징이 있다.

이진트리로 구성되었기 때문에 검색, 삽입, 삭제에 O(log n)의 시간 복잡도를 갖는다.

key 값을 기준으로 오름차순 정렬이 되며, 값이 삽입 될 때마다 자동으로 정렬이 된다.

value 값은 수정이 가능하지만, key 값은 수정이 불가능하다.

  • 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();

insert();

새로운 노드를 삽입하는 함수이다.

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();

erase(iter); // 반복자가 가리키는 노드를 삭제한다.
erase(start,end); // [start, end)범위의 노드를 삭제한다.
erase(key); // key 값을 가진 노드를 삭제한다.

find();

find(key);

key 값을 가진 노드를 찾아, 그 노드를 가리키는 반복자를 반환한다.
key 값을 가진 노드가 없으면 end()와 같은 반복자를 반환한다.

m.find(3)->first
m.find(3)->second

위와 같은 방식으로 사용할 수 있다.

장, 단점

장점

  • 새로운 값을 삽입하면 자동으로 정렬해준다.
  • 검색 속도가 빠르다.

단점

  • 삽입과 삭제가 잦으면 정렬 횟수가 많아져 효율이 떨어진다.

0개의 댓글