multiset (STL)

multiset은 STL 컨테이너로, 중복된 값을 허용하면서 자동으로 정렬된 상태를 유지하는 데이터 구조다.
이는 일반적인 set과 달리 동일한 값을 여러 번 저장할 수 있다.

---

1. 특징

• 중복 허용: 같은 값을 여러 번 저장할 수 있다.
• 자동 정렬: 삽입할 때 자동으로 오름차순(기본 설정 기준)으로 정렬된다.
• 정렬 기준 커스터마이징 가능: 사용자 정의 비교 함수를 통해 정렬 방식을 지정할 수 있다.
• 균형 이진 트리 기반: 내부적으로 균형 이진 탐색 트리를 사용하여 효율적인 삽입, 삭제, 탐색이 가능하다.
  • 삽입, 삭제, 탐색의 시간 복잡도: O(log N)

---

2. 함수

삽입 (insert)

multiset에 값을 삽입한다. 동일한 값도 삽입이 가능하며, 자동으로 정렬된다.

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms;
    ms.insert(10);
    ms.insert(5);
    ms.insert(10); // 중복 허용

    for (int val : ms) {
        std::cout << val << " "; // 출력: 5 10 10
    }
    return 0;
}

삭제 (erase)

특정 값이나 반복자를 이용하여 원소를 삭제한다.

• 특정 값 삭제:

ms.erase(10); // 모든 10 삭제

• 특정 반복자 삭제:

auto it = ms.find(5); // 값 5를 가리키는 반복자
if (it != ms.end()) {
    ms.erase(it); // 해당 반복자에 해당하는 값만 삭제
}

탐색 (find)

특정 값을 탐색하여 반복자를 반환한다. 찾는 값이 없는 경우 end() 반복자를 반환한다.

auto it = ms.find(10);
if (it != ms.end()) {
    std::cout << "10 found in multiset" << std::endl;
}

개수 조회 (count)

특정 값이 몇 개 있는지 확인할 수 있다.

int count_10 = ms.count(10);
std::cout << "10의 개수: " << count_10 << std::endl;

범위 탐색 (equal_range)

특정 값의 범위를 나타내는 반복자 쌍을 반환한다.

auto range = ms.equal_range(10);
for (auto it = range.first; it != range.second; ++it) {
    std::cout << *it << " "; // 10 출력
}

---

3. 사용자 정의 정렬

기본적으로 multiset은 오름차순으로 정렬되지만, 사용자 정의 정렬 기준을 사용할 수 있다. 예를 들어 내림차순으로 정렬하려면 작성한다.

#include <iostream>
#include <set>

struct Descending {
    bool operator()(int a, int b) const {
        return a > b; // 내림차순 정렬
    }
};

int main() {
    std::multiset<int, Descending> ms;
    ms.insert(10);
    ms.insert(5);
    ms.insert(15);

    for (int val : ms) {
        std::cout << val << " "; // 출력: 15 10 5
    }
    return 0;
}

---

4. 활용 시기

(1) 중복 값을 허용하는 정렬된 리스트

• 예를 들어, 점수를 중복해서 저장하면서 항상 정렬된 상태로 유지해야 할 때 유용하다.
• 특정 범위의 점수 개수를 쉽게 구할 수 있다.

(2) 중복 요소 개수 세기

• 입력된 데이터를 중복 개수에 따라 정렬할 때 사용할 수 있다.
• 특정 값의 출현 빈도를 바로 확인할 수 있다.