10. Set & Multiset

set(셋)은 가장 단순한 형태의 연관 컨테이너로 key라고 하는 원소들의 집합으로 이루어져 있다. 연관 컨테이너는 모두 노드 기반의 균형 이진 트리로 구현되어 있다. set의 원소는 중복될 수 없다.

헤더파일 <set>을 인클루드하면 set을 사용할 수 있다. set 클래스는 <set>에서 인클루드하는 헤더파일 <bits/stl_set.h>에 정의되어 있다.

set의 선언 방법도 크게 다섯 가지로 나눌 수 있다. 다른 연관 컨테이너에도 모두 같은 선언 방법이 적용된다.

1. set<int> s;
2. set<int> s(p);
3. set<int> s(k);
4. set<int> s(b,e);
5. set<int> s(b,e,p);

1, 3, 4번과 같은 선언 방법은 이미 벡터의 선언에서도 나왔다. 각각 빈 set, $k$의 복사본, 반복자 구간 $[b,e)$의 원소들로 초기화된 set이 생성된다. 2번과 5번은 조건자를 명시한 선언 방법이다. 연관 컨테이너 역시 우선순위 큐와 마찬가지로 조건자에 따라 원소들의 정렬 기준을 정하고 선언 시 생략할 경우 기본 조건자인 less<_Key>를 쓰게 된다.

다음은 set의 멤버 함수이다:

s.insert(x);	s에 x를 삽입한다.
s.insert(p,x);	p가 가리키는 위치에 x를 삽입한다.
s.insert(b,e);	s에 반복자 구간 [b,e)의 원소를 삽입한다.
s.size();	s에 들어 있는 원소의 개수를 반환한다.
s.clear();	s의 모든 원소를 삭제한다.
s.empty();	s가 비었는지 확인한다.
s.erase(x);	s에서 x 원소를 모두 삭제한다.
s.erase(p);	p가 가리키는 원소를 삭제한다.
s.erase(b,e);	반복자 구간 [b,e)의 원소를 삭제한다.
s.begin();	s의 첫 원소를 가리키는 반복자를 반환한다.
s.end();	s의 끝을 가리키는 반복자를 반환한다.
s.rbegin();	s의 역 순차열의 첫 원소를 가리키는 반복자를 반환한다.
s.rend();	s의 역 순차열의 끝을 가리키는 반복자를 반환한다.
s.emplace(x);	s에 x를 삽입한다.
s.emplace_hint(p,x);	p가 가리키는 위치에 x를 삽입한다.
s.count(x);	s에 포함된 원소 x의 개수를 반환한다.
s.find(x);	s에서 x가 처음으로 등장하는 위치를 가리키는 반복자를 반환한다.
s.contains(x);	s에 원소 x가 존재하는지 확인한다.
s.equal_range(x);	s에서 원소 x가 존재하는 범위를 반환한다.
s.lower_bound(x);	x의 시작 위치를 가리키는 반복자를 반환한다.
s.upper_bound(x);	x의 끝 위치를 가리키는 반복자를 반환한다.
s.max_size();	s가 담을 수 있는 원소의 최대 개수를 반환한다.
s.extract(x);	s에서 원소 x를 추출한다.
s.extract(p);	p가 가리키는 원소를 추출한다.
s.merge(k);	s에 k를 합친다.
s.key_comp();	s의 key 정렬 기준인 조건자를 반환한다.
s.value_comp();	s의 value 정렬 기준인 조건자를 반환한다.
s.swap(k);	s와 k를 맞바꾼다.
s.get_allocator();	s에 설정된 할당기를 반환한다.

일부 함수의 경우 설명이 더 필요한데,

• set::extract, set::merge 함수는 C++17 표준이고 set::contains 함수는 C++20 표준이므로 이전 표준에서는 작동하지 않는다.
• set::merge 함수는 $k$에 존재하고 $s$에 존재하지 않는 원소들을 $k$에서 삭제하고 $s$에 추가한다.
• set::extract 함수로 추출한 원소는 $s$에서 삭제된다.
• set::equal_range 함수의 반환형은 pair<iterator, iterator>형으로 각각의 iterator는 set::lower_bound 함수와 set::upper_bound 함수가 반환하는 반복자와 일치한다.
• set::find 함수는 찾는 값이 $s$에 없을 경우 set::end()를 반환한다.
• set::insert, set::emplace_hint 함수의 인자로 들어가는 $p$의 의미는 원소를 삽입할 위치를 지정하는 것이다. 자동 정렬은 마찬가지로 실행된다.

또한 set은 원소의 중복이 불가능하기 때문에 set::count 함수의 결과는 $0$ 또는 $1$이다.

---

multiset(멀티셋)은 set과 비슷하지만 원소의 중복이 가능하다. 헤더파일 <set>을 인클루드하면 multiset을 사용할 수 있으며, <set>에서 인클루드하는 헤더파일 <bits/stl_multiset.h>에 multiset 클래스가 정의되어 있다.

multiset의 선언 방법과 멤버 함수는 set과 같으므로 앞 문단에서 설명한 것을 참고하면 된다.

 

→ solved.ac tag: tree_set