[C++/STL] - multiset

YH J·2023년 5월 31일
0

C++ STL

목록 보기
6/11

1. multiset 이란

multiset은 C++ STL(Standard Template Library)의 연관 컨테이너 중 하나입니다. set과 비슷하지만 중복된 값을 저장할 수 있습니다.

2. 특징

  • multiset은 set과 비슷하지만, 중복된 값을 저장할 수 있다는 차이가 있습니다.
  • multiset의 요소는 자동으로 정렬되며, 이 때 기준이 되는 것은 각 요소의 키 값입니다.
  • 각 요소의 키 값은 직접 변경되지 않으며, 이전 값을 삭제하고 새 값을 삽입해야 합니다.
  • multiset은 다음 헤더 파일을 포함해야 합니다: <set>
  • multiset은 template으로 정의되어 있으며, template 매개 변수로는 요소의 키 값 타입과 비교 함수(Compare) 타입, 할당자(Allocator) 타입이 올 수 있습니다. 이 때, 비교 함수와 할당자는 기본값으로 less와 allocator가 사용됩니다.

3. 장단점

장점 :

  • multiset은 중복된 값을 저장할 수 있는 연관 컨테이너입니다. 따라서, 중복된 값을 다룰 때 유용합니다.
  • multiset은 자동으로 정렬되는 특성을 가지므로, 정렬된 데이터를 다룰 때 유용합니다.
  • multiset은 특정 요소의 개수를 쉽게 구할 수 있습니다.

단점 :

  • multiset은 각 요소의 키 값이 변경되지 않으므로, 이전 값을 삭제하고 새 값을 삽입해야 합니다.
  • multiset은 각 요소를 검색할 때, 이진 탐색을 사용하므로 검색 속도가 느릴 수 있습니다.
  • multiset은 요소를 삽입하거나 삭제할 때, 기존 요소의 위치를 변경할 수 있으므로, 반복자 유효성을 유지하는 것이 어려울 수 있습니다.

4. 시간복잡도

  1. 접근 - O(logN)
    multiset은 이진 탐색 트리를 사용하므로, 임의 원소 접근의 시간복잡도는 O(logN)입니다.
  2. 검색 - O(logN)
    multiset은 이진 탐색 트리를 사용하므로, 검색의 시간복잡도는 O(logN)입니다.
  3. 삽입 및 삭제 - O(logN)
    multiset은 이진 탐색 트리를 사용하므로, 삽입 및 삭제의 시간복잡도는 O(logN)입니다.
    만약 multiset을 사용할 때, 키 값이 정렬된 상태에서 삽입되는 경우, multiset의 삽입 시간복잡도는 O(1)입니다.

5. 사용법

1) 초기화

multiset<int> myset; //빈 multiset 생성하기

multiset<int> myset = {3, 1, 4, 1, 5, 9, 2, 6, 5}; // 생성과 동시에 초기값으로 초기화하기

multiset<int, greater<int>> myset = {3, 1, 4, 1, 5, 9, 2, 6, 5}
// 생성과 동시에 키 값 비교 함수를 지정하여 초기화하기 ( 기본이 less(오름차순) )
// 예제는 greater(내림차순)

allocator<int> myalloc;
multiset<int, less<int>, allocator<int>> myset(myalloc);
// 생성과 동시에 할당자를 지정하여 초기화하기

multiset<int> myset1 = {3, 1, 4, 1, 5, 9, 2, 6, 5};
multiset<int> myset2(myset1);
// 다른 multiset으로부터 복사하여 초기화하기

2) 멤버 함수

set과 기본적으로 동일하지만 multiset은 중복된 값을 저장할 수 있다는 점이 다르므로 추가되는 함수가 있다.
count(key) : key의 개수 반환
equal_range(key) : key와 일치하는 요소의 처음과 끝 iterator를 pair로 반환
pair<iterator, iterator>
lower_bound(key) : key와 일치하는 요소의 처음을 반환 ( set과 같지만 multiset에선 더 유용하게 사용 가능 )
upper_bound(key) : key보다 큰 첫번째 요소를 반환 ( set과 같지만 multiset에선 더 유용하게 사용 가능 )
ex) {11,11,11,11,13,13} 일 때 upper_bound(11) -> 첫 13위치의 iterator 반환

profile
게임 개발자 지망생

0개의 댓글