multiset

multiset은 set과 매우 비슷한 컨테이너다. set과의 유일한 차이는 원소의 중복이 가능하다.
그 외의 템플릿 형식, 인터페이스, 멤버 모두 set과 동일하다.

인터페이스

multiset은 set과 인터페이스가 동일하다.

원소의 삽입

insert()의 시그니처는 multiset과 set이 동일하다.
하지만 반환형에서 조그만 차이가 존재한다.

set의 insert() 반환형은 pair<set::iterator, bool>이다.
multiset의 insert() 반환형은 multiset::iterator이다.

이 차이는 multiset이 원소의 중복을 허용하는 점에서 기인한다.

#include <iostream>
#include <set>

using namespace std;

int main(void)
{
    multiset<int> mset;

    mset.insert(10);
    mset.insert(20);
    mset.insert(30);
    mset.insert(30);    // 30은 중복된다.
    mset.insert(40);
    mset.insert(50);
    mset.insert(60);
    mset.insert(60);    // 60은 중복된다.
    multiset<int>::iterator iter = mset.insert(70);

    // 현재 iter 반복자는 70을 가리킨다.
    cout << *iter << endl;

    // 원소의 중복을 확인한다.
    for(iter = mset.begin(); iter != mset.end(); iter++)
        cout << *iter << ' ';
    cout << endl;
}

원소의 탐색

중복된 원소를 허용하는 multiset의 특징 덕분에 count(), lower_bound(), upper_bound(), equal_range()는 효과적으로 사용된다.

먼저 count()와 find()의 사용 예시를 살펴보자.

#include <iostream>
#include <set>

using namespace std;

int main(void)
{
    multiset<int> mset;

    mset.insert(10);
    mset.insert(20);
    mset.insert(30);
    mset.insert(30);
    mset.insert(40);
    mset.insert(50);
    mset.insert(60);
    mset.insert(60);
    mset.insert(70);

    int thirty_count = mset.count(30);
    if(0 < thirty_count)
    {
        multiset<int>::iterator iter = mset.find(30);
        cout << *iter << "30은 multiset 내부에 존재하네요." << endl;
    }

    multiset<int>::iterator iter = mset.find(80);
    if(iter == mset.end())
        cout << "저런.. 80은 multiset 내부에 없네요." << endl;
}

그 다음으로는 lower_bound()와 upper_bound() 그리고 equal_range()의 사용 예시를 보자.

#include <iostream>
#include <set>

using namespace std;

int main(void)
{
    multiset<int> mset;

    mset.insert(10);
    mset.insert(20);
    mset.insert(30);
    mset.insert(30);
    mset.insert(40);
    mset.insert(50);
    mset.insert(60);
    mset.insert(60);
    mset.insert(70);

    multiset<int>::iterator lower_iter = mset.lower_bound(30);
    multiset<int>::iterator upper_iter = mset.upper_bound(30);

    cout << *lower_iter << endl;
    cout << *upper_iter << endl;

    pair<multiset<int>::iterator, multiset<int>::iterator> pr = mset.equal_range(60);
    if(pr.first != pr.second)
        cout << "60은 multiset 내부에 존재합니다!" << endl;
}

정리

• multiset은 연관 컨테이너이자 노드 기반 컨테이너다.
• multiset은 원소의 중복을 허용한다.