STL 컨테이너 - map

map

**키(Key)와 값(Value)**의 관계를 기반으로 데이터를 저장하고 검색하는 기능을 제공합니다. std::map은 연관 배열(associative array) 또는 연관 컨테이너로 불리며, 내부적으로는 이진 검색 트리 또는 **레드-블랙 트리(Red-Black Tree)**를 사용하여 데이터의 삽입, 삭제, 검색 등의 연산을 효율적으로 처리합니다.

 

std::unordered_map과 헷갈린다면 아래 글에서 둘의 차이를 확인하세요.

https://coding-potato-record.tistory.com/268

STL 컨테이너 - unordered_map

 

1. std::map의 특징

• 연관 배열: std::map은 키(key)와 값(value)의 쌍을 저장하는 컨테이너입니다. std::pair 형식으로 데이터를 저장합니다. 따라서 std::pair 관련 연산(.first, .second)이 가능합니다. 
• 자동 정렬: 기본적으로 std::map은 키를 자동으로 정렬합니다. 기본 정렬은 오름차순이며, 사용자가 정의한 비교 함수에 따라 정렬을 변경할 수 있습니다.
• 고유한 키: 각 키는 고유해야 하며, 같은 키를 두 번 삽입할 수 없습니다. 동일한 키를 삽입하려고 하면 값만 갱신됩니다.
• 탐색 효율성: 내부적으로 std::map은 Red-Black Tree를 사용하여 O(log n)의 시간 복잡도로 삽입, 삭제, 검색이 가능합니다.
• 구조체/객체 사용 가능: 키와 값은 사용자 정의 타입으로도 사용할 수 있습니다.

2. 헤더 파일

std::map을 사용하려면 <map> 헤더파일을 포함해야 합니다.

3. 선언 및 초기화 방법

std::map은 템플릿을 이용해 선언합니다. 기본적인 선언과 초기화 방법은 다음과 같습니다.

• 기본 선언

• 초기화(2가지)

• 예시

4. 주요 멤버 함수

함수명	설명	반환값
insert	키와 값을 삽입합니다. 이미 존재하는 키는 삽입되지 않습니다.	삽입이 성공하면 std::pair<iterator, bool> 반환 (삽입 여부와 iterator)
operator[]	주어진 키에 대한 값을 반환합니다. 키가 없다면 새로운 항목을 추가합니다.	값 타입 (value_type)
at	주어진 키에 대한 값을 반환합니다. 키가 존재하지 않으면 예외 std::out_of_range 발생.	값 타입 (value_type)
erase	주어진 키를 삭제합니다. 여러 요소를 삭제하는 방식도 제공.	삭제된 요소의 개수 또는 void
find	주어진 키를 검색하고, 해당 키가 존재하면 그 위치를 반환합니다. 키가 없으면 end() 반환.	iterator (키가 없으면 end())
count	주어진 키가 몇 번 등장하는지 확인합니다. (특히 다중 맵에서 유용)	0 또는 1 (키가 존재하면 1, 없으면 0)
begin	맵의 첫 번째 요소를 가리키는 iterator를 반환합니다.	iterator
end	맵의 마지막 요소 뒤를 가리키는 iterator를 반환합니다.	iterator
empty	맵이 비어있는지 확인합니다.	bool (비어있으면 true, 아니면 false)
size	맵에 저장된 요소의 개수를 반환합니다.	size_t
clear	모든 요소를 삭제합니다.	void
lower_bound	주어진 키보다 크거나 같은 첫 번째 요소를 찾습니다.	iterator
upper_bound	주어진 키보다 큰 첫 번째 요소를 찾습니다.	iterator
rbegin	맵의 마지막 요소를 가리키는 역방향 iterator를 반환합니다.	reverse_iterator
rend	맵의 첫 번째 요소 앞을 가리키는 역방향 iterator를 반환합니다.	reverse_iterator