map
map (std::map — 정렬 연관 컨테이너)
std::map은 고유한 키를 가진 키-값 쌍을 담는 정렬 연관 컨테이너예요. 키는 비교 함수 Compare로 정렬돼요. 검색·제거·삽입 연산은 로그 시간 복잡도를 가져요.
출처: cppreference
본문
std::map은 고유한 키를 가진 키-값 쌍을 담는 정렬 연관 컨테이너예요. 키는 비교 함수 Compare를 써서 정렬돼요. 검색·제거·삽입 연산은 로그(logarithmic) 복잡도를 가져요. 맵은 보통 Red–black tree로 구현돼요.
std::map의 이터레이터는 키의 오름차순으로 순회해요. 이때 오름차순은 구성에 쓰인 비교 함수로 정의돼요. 즉, std::map m과 it_l < it_r인 역참조 가능한 이터레이터 it_l, it_r에 대해 m.value_comp()(*it_l, *it_r) == true예요(기본 비교를 쓰면 가장 작은 것에서 큰 것 순).
표준 라이브러리가 Compare 요구 사항을 쓰는 곳마다, 동등성은 동치 관계(equivalence relation)로 결정돼요. 간단히 말해 두 객체 a와 b는 서로가 상대보다 작다고 비교되지 않을 때(!comp(a, b) && !comp(b, a)) 동등한 것으로 봐요.
std::map은 Container, AllocatorAwareContainer, AssociativeContainer, ReversibleContainer의 요구 사항을 만족해요.
템플릿 매개변수
Key: 키의 타입.T: 매핑된 값의 타입.Compare: 엄격한 약순서(strict weak ordering)를 제공하는 Compare 타입. 기본값은std::less<Key>.Allocator: 할당자. 기본값은std::allocator<std::pair<const Key, T>>.
멤버 타입
key_type=Key,mapped_type=T,value_type=std::pair<const Key, T>key_compare=Compare,value_compare— 쌍의 첫 성분을 비교하는 중첩 비교 타입size_type,difference_typereference,const_reference,pointer,const_pointeriterator,const_iterator— 양방향 이터레이터reverse_iterator,const_reverse_iteratornode_type,insert_return_type
멤버 함수
- 생성자/파괴자,
operator=,get_allocator - 원소 접근:
at,operator[] - 이터레이터:
begin,end,rbegin,rend - 용량:
empty,size,max_size - 수정자:
clear,insert,insert_range,insert_or_assign,emplace,emplace_hint,try_emplace,erase,erase_if,swap,extract,merge - 탐색:
count,find,contains,equal_range,lower_bound,upper_bound - 관찰자:
key_comp,value_comp - 비멤버 함수:
operator==,operator<=>,std::erase_if,std::swap