[Algorithm] STL Map과 MultiMap

맵과 멀티맵

맵과 멀티맵은 키/값 쌍을 요소로 관리하는 컨테이너이다.

이 두 컨테이너는 키 값에 대한 특정 정렬 기준을 적용하여 요소를 정렬한다.

맵은 중복을 허용하지 않으며, 멀티맵은 허용한다.

 

맵과 멀티맵을 사용하기 위해서는 <map>을 인클루드 해야한다.

이는 namespace std 안에 정의 되어 있다.

 

첫 번째 템플릿 파라미터는 키의 자료형이며 두 번째 템플릿 파라미터는 요소의 값의 자료형이다.

맵/멀티맵의 요소는 2가지 요구 사항을 만족하는 어떠한 Key와 T라는 자료형을 사용할 수 있다.

1. 키와 값은 복사할 수 있거나 이동할 수 있어야 한다.

2. 키는 정렬 기준으로 비교할 수 있어야 한다.

 

세번째 템플릿 파라미터는 정렬 기준이다.

정렬 기준에서 요소는 아무 영향력이 없으며 동등 검사를 할 때에도 키가 같으면 같은 요소이다.

정렬 기준이 없으면 기본적으로 less이다.

 

멀티 맵의 경우 동등한 요소들의 순서는 무작위지만 안정적이다.

따라서 요소를 삽입/삭제 하여도 동등한 요소들 사이의 상대적 순서는 유지된다.(C++11 이후 보장)

 

기능 

맵과 멀티맵은 항상 균형 이진 트리로 구현된다.

셋과 멀티셋, 맵과 멀티맵은 같은 내부 자료형을 사용한다.

따라서 맵/멀티맵은 셋/멀티셋이 가지는 기능을 모두 갖추고 있다.

하지만 차이점도 존재한다.

맵/멀티맵의 요소는 키/값의 쌍이다.

맵/멀티맵은 연관 배열로 사용할 수도 있다.

 

맵/멀티맵은 키 값에 따라 자동으로 정렬하기 때문에 특정 키를 갖는 요소를 검색할 때 성능이 좋다.

특정 값을 갖는 요소를 검색하는 것은 성능이 좋지 않다.

요소의 키 값을 수정하기 위해서는 예전 키 값을 갖는 요소를 제거한 뒤 새로운 키 값을 갖는 새 요소를 삽입해야 한다.

그 결과로 반복자의 입장에서 키는 상수이다.

그러나 요소의 값이 상수가 아닌 경우 직접 수정할 수 있다.

 

연산 

생성자/소멸자

연산	설명
map c	기본 생성자, 아무 요소도 갖지 않는 빈 맵/멀티맵이 만들어진다
map c(op)	op를 정렬기준으로 하는 멥/멀티맵을 만든다
map c(c2)	복사 생성자, 같은 자료형의 다른 맵/멀티맵의 복사본을 만든다( 모든 요소 복사 )
map c = c2	복사 생성자, 같은 자료형의 다른 맵/멀티맵의 복사본을 만든다( 모든 요소 복사 )
map c(rv)	이동 생성자, rv의 내용을 갖는 새로운 맵/멀티맵을 만든다.
map c = rv	이동 생성자, rv의 내용을 갖는 새로운 맵/멀티맵을 만든다.
map c(beg, end)	범위 [ beg, end) 내의 요소를 갖는 맵/다중맵을 만든다.
map c(beg, end, op)	범위 [beg, end) 내의 요소를 가지며 정렬 기준이 op인 맵/다중맵을 만든다
map c(initlist)	초기화자 목록 내의 요소로 초기화된 벡터를 만든다
map c = inilist	초기화자 목록 내의 요소로 초기화된 벡터를 만든다
c~map()	모든 요소를 삭제하고 메모리를 해제한다.

 

 

수정하지 않는 연산

연산	설명
c.key_comp()	비교 기준 반환
c.value_comp()	값을 비교하는 기준 반환
c.empty()	컨테이너가 비엇는지 여부를 알려줌
c.size()	현재 요소으이 수를 반환
c.max_size()	최대 저장 가능한 요소의 개수 변환
c1 == c2	c1이 c2와 같은지 반환
c1 != c2	c1이 c2와 다른지 반환
c1 < c2	c1이 c2보다 작은지 반환
c1 > c2	c1이 c2보다 큰지 반환
c1 <= c2	c1이 c2보다 작거나 같은지 반환
c1 >= c3	c1이 c2보다 크거나 같은지 봔환

 

 

특별 검색 연산

연산	설명
c.count(val)	키의 값이 val인 요소의 수를 반환
c.find(val)	키의 값이 val인 첫 번째 요소의 위치 반환, 찾지 못한 경우 end() 반환
c.lower_bound(val)	키가 val인 요소가 삽입되게 될 첫 번째 위치 반환, 키 값이 val보다 크거나 같은 첫 번쨰 요소 위치
c.upper_bound(val)	키가 val인 요소가 삽입되게 될 마지막 위치 반환, 키 값이 val보다 큰 첫 번째 요소 위치
c.equal_range(val)	키가 val인 모든 요소의 범위, 키 값이 val인 요소가 삽입될 처음과 마지막 위치 사이

 

 

할당

연산	설명
c = c2	c2의 모든 요소를 c에 할당
c = rv	rv의 모든 요소를 c에 이동 할당 (C++11 이후 지원 )
c = initlist	초기화자 목록 내 모든 요소를 c에 할당 ( C++11 이후 지원 )
c.assign(n, elem)	n개의 elem을 요소로 할당
c.assign(beg,end)	범위 [beg, end) 내 요소를 할당
c.assign(inilist)	초기화자 목록 내 모든 요소를 c에 할당
c1.swap(c2)	c1과 c2의 데이터를 교환
swap(c1,c2)	c1과 c2의 데이터를 교환

 

 

반복자 함수와 요소 접근

연산	설명
c.begin()	첫 번째 요소에 대한 양방향 반복자 반환
c.end()	마지막 요소 다음 위치에 대한 양방향 반복자 반환
c.cbegin()	첫 번째 요소에 대한 양방향 상수 반복자 반환 ( C++11 이후 지원 )
c.cend()	마지막 요소 다음 위치에 대한 양방향 상수 반복자 반환 ( C++11 이후 지원 )
c.rbegin()	역방향 반복에서의 첫 번째 요소에 대한 역방향 반복자 반환
c.rend()	역방항 반복에서의 마지막 요소 다음 위치에 대한 역방향 반복자 반환
c.crbegin()	역방향 반복에서의 첫 번째 요소에 대한 역방향 상수 반복자 반환 ( C++11 이후 지원 )
c.crend()	역방향 반복에서의 마지막 요소 다음 위치에 대한 역방향 상수 반복자 반환 ( C++11 이후 지원 )

 

 

요소 삽입/제거

연산	설명
c.insert(val)	val의 복사본 삽입 후 새 요소의 위치를 반환, 맵의 경우 삽입 성공 여부 반환
c.insert(pos,val)	val의 복사본 삽입 후 새 요소의 위치 반환, pos는 삽입 연산에서 검색을 시작할 위치에 대한 힌트
c.insert(beg,end)	범위 [beg, end)내 모든 요소의 복사본을 삽입한다. 반환값 없음
c.insert(initlist)	초기화자 목록 내 모든 요소의 복사본 삽입, 반환값 없음 ( C++11 이후 지원 )
c.emplace(args...)	args로 초기화된 요소의 복사본 삽입 후 새 요소의 위치 반환, 맵의 경우 성공 여부 반환 ( C++11 이후 지원 )
c.emplace_hint(pos,args...)	args로 초기화된 요소의 복사본 삽입 후 새 요소의 위치 반환, pos는 삽입 연산에서 검색을 시작할 위치에 대한 힌트
c.erase(val)	val과 같은 요소를 모두 제거한 후 제거한 요소의 수 반환
c.erase(pos)	반복자 위치 pos에 있는 요소를 제거한 후 다음 위치 반환 ( C++11 이전은 반환 값 없음 )
c.erase(beg, end)	범위 [beg, end) 내 요소를 모두 제거한 뒤 다음 위치 반환 ( C++11 이전은 반환 값 없음 )
c.clear()	모든 요소를 제거

 

 

맵을 연관 배열로 사용하기 

연관 컨테이너는 일반적으로 요소에 직접 접근할 수 없지만 맵은 예외이다.

비상수 맵은 요소를 직접 접근할 수 있도록 첨자 연산자를 제공한다.

연산	효과
c[key]	만약 키 값으로 key가 없었다면 키 값이 key인 요소 삽입. 키 값이 key인 요소의 값 반환
c.at[key]	키 값이 key인 요소의 값에 대한 참조자 반환 ( C++11 이후 지원 )