std::map
std::map (정렬 연관 컨테이너)
정렬된 연관 컨테이너로, 고유한 키를 갖는 키-값 쌍을 저장해요. 키는 정렬 기준(sort key)에 따라 정렬돼요. 탐색·삽입·제거가 로그 시간 O(log n)이에요.
출처: cppreference
본문
<map> 헤더에 정의돼 있고, 정렬 연관 컨테이너예요.
template<
class Key,
class T,
class Compare = std::less<Key>,
class Allocator = std::allocator<std::pair<const Key, T>>
> class map;
C++17부터 pmr 별칭도 있어요: std::pmr::map<Key, T, Compare>.
std::map은 고유한 키를 갖는 키-값 쌍을 저장하는 정렬 연관 컨테이너예요. 키는 비교 함수 Compare를 써서 정렬돼요. 탐색·삽입·제거 연산이 로그 시간 복잡도를 가져요. map은 보통 레드-블랙 트리(red-black tree)로 구현돼요.
표준에선 이 컨테이너가 (정렬 연관 컨테이너의 일반적 정의와 달리) 레드-블랙 트리로 구현될 필요는 없지만, insert·emplace·erase 같은 연산에 대해 O(log n) 복잡도와 노드 기반 구조를 보장해요.
키-값 쌍을 반복자로 역참조하면 std::pair<const Key, T>&를 얻어요. 이때 키 부분은 const이므로, 반복자를 통해 키를 수정할 수 없어요(수정하려면 제거 후 재삽입해야 함). 키가 같으면 새 값이 기존 값을 대체해요.
map은 Container, AllocatorAwareContainer, AssociativeContainer, ReversibleContainer 요구사항을 만족해요.
특화된 멤버 함수
- 원소 접근:
at,operator[]. - 관찰자:
key_comp,value_comp. - 노드 핸들(NodeHandle, C++17):
extract,merge.
멤버 타입
key_type, mapped_type, value_type(std::pair<const Key, T>), size_type, difference_type, key_compare, allocator_type, reference, const_reference, pointer, const_pointer, iterator, const_iterator, reverse_iterator, const_reverse_iterator.
멤버 함수
- 생성자, 소멸자,
operator=,get_allocator. - 원소 접근:
at,operator[]. - 반복자:
begin/cbegin,end/cend,rbegin/crbegin,rend/crend. - 용량:
empty,size,max_size. - 수정자:
clear,insert,insert_range(C++23),insert_or_assign(C++17),emplace,emplace_hint,try_emplace(C++17),erase,erase_if(C++20),swap,extract(C++17),merge(C++17). - 탐색:
count,find,contains(C++20),equal_range,lower_bound,upper_bound.
비멤버 함수
operator==,!=,<,<=,>,>=,<=>: 두 map 사전식 비교.std::swap(std::map):std::swap특수화.erase_if(std::map)(C++20): 특정 기준을 만족하는 원소 모두 제거.
map은 보통 operator[]로 키에 값을 할당하거나(map[key] = value), find·at으로 키를 탐색하는 용도로 쓰여요. operator[]는 키가 없으면 기본 생성된 값을 삽입할 수 있으므로 주의가 필요해요. (try_emplace/insert_or_assign는 이런 부작용을 피하는 데 유용해요.)