multimap
multimap (std::multimap — 정렬 멀티맵)
std::multimap은 같은 키를 여러 개 허용하면서 키-값 쌍의 정렬된 목록을 담는 연관 컨테이너예요. 키는 비교 함수 Compare로 정렬돼요. 검색·삽입·제거 연산은 로그 시간 복잡도를 가져요.
출처: cppreference
본문
std::multimap은 같은 키를 가진 여러 항목을 허용하는 키-값 쌍의 정렬된 목록을 담는 연관 컨테이너예요. 정렬은 키에 적용되는 비교 함수 Compare에 따라 수행돼요. 검색·삽입·제거 연산은 로그(logarithmic) 복잡도를 가져요.
std::multimap의 이터레이터는 키의 비내림차순(non-descending)으로 순회해요. 즉, multimap m과 it_l < it_r인 역참조 가능한 이터레이터 it_l, it_r에 대해 m.value_comp()(*it_r, *it_l) == false예요(기본 비교를 쓰면 가장 작은 것에서 큰 것 순).
키가 동등하게 비교되는 쌍들의 순서는 삽입 순서이며 변하지 않아요. (since C++11)
표준 라이브러리가 Compare 요구 사항을 쓰는 곳마다, 동등성은 동치 관계(equivalence relation)로 결정돼요. 간단히 말해 두 객체 a와 b는 서로가 상대보다 작다고 비교되지 않을 때(!comp(a, b) && !comp(b, a)) 동등한 것으로 봐요.
std::multimap은 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_comparesize_type,difference_type,reference,const_reference,pointer,const_pointeriterator,const_iterator,reverse_iterator,const_reverse_iteratornode_type,insert_return_type
멤버 함수
- 생성자/파괴자,
operator=,get_allocator - 이터레이터:
begin,end,rbegin,rend - 용량:
empty,size,max_size - 수정자:
clear,insert,insert_range,emplace,emplace_hint,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
참고로 multimap에는 operator[]와 at이 없어요(중복 키가 있어 키만으로 값을 특정할 수 없기 때문).