[STL] Set 컨테이너

set 컨테이너

연관 컨테이너 중 단순한 컨테이너로 Key라 불리는 원소(value)의 집합으로 이뤄진 컨테이너. 중복 혀용X
노드 기반의 컨테이너로 균형 이진 트리로 구현되어 있다.
set은 원소를 삽입할때 유일한 멤버 함수 insert( )를 제공한다.

 

균형 이진 트리: 모든 노드가 부모보다 왼쪽이 작고 오른쪽이 큰 형태. (반대라면 반대로)

 

연관 컨테이너는 균형 이진 트리를 사용하므로 찾기연산( find(), lower_bound(), upper_bound(), equal_range(), count())에 뛰어난 성능(로그 시간)을 보이며 insert 또한 로그 시간 복잡도를 보인다.

 

중복을 허용하는 multiset 컨테이너

템플릿 형식, 인터페이스, 멤버의 형식 모두 set과 같고, key가 중복으로 저장되는 컨테이너

 

multiset의 insert는 key(원소)가 중복으로 저장될 수 있기 때문에 set처럼 저장 위치와 삽입 성공의 bool 값을 반환하는 pair 객체가 아닌 저장된 위치만을 가리키는 반복자를 반환한다.

---

 

set 의 주요 인터페이스

템플릿 형식
template < typename key, typename Pred = less<key>, typename Allocator = allocator<key> > class set	key는 set 컨테이너의 원소의 형식이며, Pred는 set의 정렬 기준인 조건자(함수 객체) 기본 조건자는 less(오름차순)이다.

 

생성자

생성자
set s	s는 빈 컨테이너
set s(pred)	s는 빈 컨테이너로 정렬 기준은 pred 조건자를 사용한다.
set s(s2)	s는 s2의 컨테이너의 복사본이다(복사 생성자호출)
set s(b, e)	s는 반복자 구간 [b, e)로 초기화된 원소를 같는다.
set s(b, e, pred)	s는 반복자 구간 [b, e)로 초기화된 원소를 갖는다,. 정렬 기준은 pred 조건자를 사용한다.

 

멤버함수

멤버함수
p=s.begin()	p는 s의 첫 원소를 가리키는 반복자(const, 비 const 버전이 있음.)
s.clear()	s의 모든 원소를 제거한다.
n = s.count(k)	원소 k의 개수를 반환한다.
s.empty()	s가 비어있는지 확인
p=s.end()	p는 s의 끝을 표시하는 반복자 (const, 비 const 버전이 있음.)
pr=s.equal.range(k)	pr은 k 원소의 반복자 구간인 pair 객체다. (const, 비 const 버전이 있음.)
q=s.erase(p)	s의 p가 가리키는 원소를 제거하고 q에는 다음 원소를 넣는다.
q=s.erase(b,e)	s의 반복자 b부터 e 까지의 시퀀스 구간을 제거하고 q는 다음 원소를 가리킨다.
n=s.erase(k)	k 원소를 제거한다. n은 제거한 개수
pr=s.insert(k)	s 컨테이너에 k를 삽입한다. pr은 삽입한 원소의 가리키는 반복자와 성공 여부의 bool 값인 pair객체
q=s.insert(p,x)	p가 가리키는 위치에 x를 삽입한다. q는 삽입한 원소를 가리키는 반복자.
s.insert(b,e)	p가 가리키는 위치에 반복자 b부터 e까지의 시퀀스 구간원소를 삽입한다.
pred = s.key_comp()	pred는 s의 key 정렬 기준인 조건자다(key_compare 타입)
p=s.lower_bound(k)	p는 k의 시작 구간을 가리키는 반복자다 (const, 비 const 버전이 있음)
n=s.max_size()	n은 s가 담을 수 있는 최대 메모리 크기이다.
p=s.rbegin()	p는 s의 역 순차열의 첫번째 원소를 가리키는 반복자(reverse begin의 줄임말로 end()와 같다)
p=s.rend()	p는 s의 역 순차열의 마지막 원소를 가리키는 반복자(reverse end의 줄임말로 begin()와 같다)
s.size( )	원소의 갯수
s.swap(s2)	s와 s2를 swap한다.
p=s.upper_bound(k)	p는 k의 끝 구간을 가리키는 반복자(const, 비 const 버전이 있음)
pred=s.value_comp()	pred는 s의 value 정렬 기준인 조건자다(value_compare 타입)

 

연산자

연산자
s1 == s2	s1과 s2의 모든 원소가 같은가 (bool 형식)
s1 != s2	s1과 s2의 모든 원소 중 하나라도 다른 원소가 있는가? (bool 형식)
s1 < s2	s2가 s1보다 하나라도 큰 원소가 있는가? (bool 형식)
s1 <= s2	s2가 s1보다 하나라도 같거나 큰 원소가 있는가? (bool 형식)
s1 > s2	s1이 s2보다 하나라도 큰 원소가 있는가? (bool 형식)
s1 >= s2	s1이 s2보다 하나라도 같거나 큰 원소가 있는가? (bool 형식)

 

멤버형식

멤버형식
allocator_type	메모리 관리자 형식
const_iterator	const 반복자 형식
const_pointer	const value_type *형식
const_reference	const value_type& 형식
const_reverse_iterator	const 역 반복자 형식
difference_type	두 반복자 차이의 형식
iterator	반복자 형식
key_compare	키(key) 조건자(비교) 형식
key_type	키(key)의 형식
pointer	value_type* 형식
reference	value_type& 형식
reverse_iterator	역 반복자 형식
size_type	첨자(index)나 원소의 개수 등의 형식
value_compare	원소 조건자(비교) 형식
value_type	원소의 형식