[Basic C++] #71_multiset

 

#1. 개념

 

1. multiset

[정의] : multiset 컨테이너는 C++ STL에서 제공하는 연관 컨테이너입니다.
[특징] : multiset 컨테이너는 key 값을 레드-블랙 트리(균형 이진트리) 자료구조에 저장하며, 중복을 허용합니다.

 

#2. 선언

 

#include <set>
using namespace std;

int main()
{
    // #1. 기본 선언
    multiset<int> ms;
    // #2. 정렬 기준을 내림차순으로 변경하여 선언
    multiset<int, greater<int> ms
    // #3. vector 컨테이너를 통해 초기화
    vector<int> v = {5,1,6,4};
    multiset<int> ms(v.begin(), v.end());
    // #4. 초기화 리스트 활용
    multiset<int> ms = {10, 20, 30, 30, 40};
}

 

Details

1. [균형 이진 트리의 정렬] : 초기화 리스트에 작성한 원소들은 그 순서가 '내부 정렬'로 인해 바뀝니다.

 

#3. 반복자

 

#include <set>
using namespace std;

multiset<int> ms;

ms.begin() or beign(ms) : multiset의 첫 번째 원소를 가리키는 반복자

ms.end() or end(ms) : multiset의 마지막 원소를 가리키는 반복자

ms.rbegin() or rbegin(ms) : multiset의 역 방향 첫 번째 원소를 가리키는 반복자

 

#4. 삽입, 제거

 

#include <set>

multiset<int> ms;

ms.clear()		: 모든 원소를 제거

ms.insert(k)		: 새로운 원소 "K"를 삽입합니다. 성공 여부는 pair<iterator, bool>로 나옵니다.

ms.insert(iter, k)	: iter(반복자)가 가리키는 위치부터 K를 삽입할 위치를 탐색하여 K를 삽입합니다.

ms.erase(iter)		: iter가 가리키는 위치의 원소를 제거합니다.

ms.erase(k)		: 특정 Key 값을 갖는 원소를 제거합니다.

ms.erase(start, end)	: [start, end) 범위의 원소를 모두 제거합니다.

 

#5. 탐색

 

#include <set>

multiset<int> ms;

ms.find(K)		: 원소 K를 가리키는 반복자를 반환합니다. K가 없다면, end(ms)를 반환합니다.

ms.count(K)		: multiset 컨테이너 내 원소 K의 갯수를 반환합니다.

ms2.swap(ms1)		: ms1과 ms2를 swap합니다.

ms.upper_bound(K)	: (개구간) 마지막 K의 바로 다음 위치를 가리키는 반복자를 반환합니다.

ms.lower_bound(K)	: (폐구간) 첫 번째 K 위치를 가리키는 반복자를 반환합니다.

ms.equal_range(K)	: K의 lower_bound와 upper_bound를 "pair"로 반환합니다.

ms.size()		: 원소의 개수를 반환합니다.

 

Details

1. [find 알고리즘] : set의 find 연산은 pair를 반환하지만, multiset의 find 연산은 반복자를 반환합니다.
2. [lower_bound와 upper_bound] : lower_bound는 폐구간, upper_bound는 개구간입니다. 

 

#6. 예제-1, 반복자 순회

 

#include <set>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {30, 10, 20, 20};
    std::multiset<int> ms(vec.begin(), vec.end());

    for (auto iter = ms.begin(); iter != ms.end(); ++iter) {
        std::cout << *iter << ' ';
    }
    // 출력: 10 20 20 30

    return 0;
}

 

#7. 예제-2, count 활용 예제

 

#include <set>
#include <iostream>

int main() {
    std::multiset<int> ms = {10, 20, 30, 20};

    int count = ms.count(20);

    std::cout << "Count of 20: " << count << std::endl; // 출력: Count of 20: 2

    return 0;
}

 

#8. 예제-3, find 활용 예제

 

#include <set>
#include <iostream>

int main() {
    std::multiset<int> ms = {10, 20, 30, 20};

    auto it = ms.find(30);
    if (it != ms.end()) {
        std::cout << "Found: " << *it << std::endl; // 출력: Found: 30
    }

    return 0;
}

 

#9. 예제-4, lower_bound와 upper_bound 활용 예제

 

#include <set>
#include <iostream>

int main() {
    std::multiset<int> ms = {10, 20, 30, 20};

    auto lower = ms.lower_bound(20);
    auto upper = ms.upper_bound(20);

    for (auto it = lower; it != upper; ++it) {
        std::cout << *it << ' '; // 출력: 20 20
    }

    return 0;
}

 

#10. 예제-5, equal_range 활용 예제

 

#include <set>
#include <iostream>

int main() {
    std::multiset<int> ms = {10, 20, 30, 20};

    auto range = ms.equal_range(20);

    for (auto it = range.first; it != range.second; ++it) {
        std::cout << *it << ' '; // 출력: 20 20
    }

    return 0;
}

 

---