[Algorithm] STL Set과 MultiSet

Set과 MultiSet은 자신의 요소를 특정 정렬 기준에 따라 정렬한다.

Set과 MultiSet의 큰 차이는 Set은 요소의 중복을 허용하지 않고 MultiSet은 중복을 허용한다는 것이다.

 

Set과 MultiSet을 사용하기 위해서는 <set>을 인클루드 해야한다.

또한 namespace std에 존재한다.

 

셋과 멀티셋은 정렬 기준에 부합하는 자료형만 넣을 수 있다.

두 번째 템플릿 파라미터에 정렬 기준을 넣을 수 있다.

기본으로는 less이다.

less는 연산자 < 에 따라 요소를 정렬한다.

연산자는 여러 종류가 있다.

표현식	설명
less<type>()	param1 < param2
less_equal<type>()	param1 <= param2
greater<type>()	param1 > param2
greater_equal<type>()	param1 >= param2

 

이 밖에도 많이 있다.

 

정렬기준은 4가지 속성을 만족해야 한다.

1. 대칭적이지 않아야 한다.

x < y 이 참이면 x > y는 거짓이어야 한다.

2. 전이관계가 성립해야 한다.

x < y가 참이고 y < z도 참이면 x < z는 참이다.

3. 비반사적이어야 한다.

x < x는 거짓이다.

4. 동등성의 전이도 가져야 한다.

a==b가 참이고 b==c가 참이면 a==c는 참이다.

 

그런데 <= 연산자는 위의 4가지 속성을 만족할 수 없다. ( >= 또한 마찬가지 )

 

기능 

셋과 멀티셋은 항상 균형 이진 트리로 구현된다.

균형 이진 트리를 사용했을 때 셋과 멀티셋 연산의 복잡도가 만족된다.

 

사진 출처 : http://warmz.tistory.com/619

 

셋과 멀티셋은 자동으로 정렬되기 때문에 특정 요소를 빠르게 찾을 수 있다.

이는 검색에서 매우 유리한 위치를 가지지만 요소의 값을 직접 바꿀 수 없다는 문제가 단점이 발생한다.

요소의 값을 수정하기 위해서는 예전 값을 제거하고 새로운 값을 삽입해야 한다.

 

셋과 멀티셋은 직접 요소 접근을 위한 연산을 제공하지 않는다.

반복자를 통한 간접 접근에서도 반복자의 관점에서 요소의 값이 상수로 제약되어 있다

 

연산 

생성자와 소멸자

연산	설명
set c	기본 생성자
set c(op)	op을 정렬 기준으로 사용하는 셋/멀티셋을 만든다
set c(c2)	복사 생성자, 모든 요소를 복사한다
set c = c2	복사 생성자, 모든 요소를 복사한다
set c(rv)	이동 생성자, rv의 내용을 갖는 새로운 셋/멀티셋을 만든다.
set c = rv	이동 생성자, rv의 내용을 갖는 새로운 셋/멀티셋을 만든다.
set c(beg, end)	범위 [beg,end) 내의 요소를 갖는 셋/멀티셋을 만든다.
set c(beg, end, op)	범위 [beg,end) 내의 요소를 가지며 정렬 기준이 op인 셋/멀티셋을 만든다
set c(initlist)	초기화자 목록 내의 요소로 초기화된 셋/멀티셋을 만든다 ( C++11 이후 지원 )
set c = initlist	초기화자 목록 내의 요소로 초기화된 셋/멀티셋을 만든다 ( C++11 이후 지원 )
c.~set()	소멸자, 모든 요소를 삭제하고 메모리를 해제한다.

 

 

위의 set은 다음 중 하나로 변경해야한다.

집합	설명
set<Elem>	기본적으로 less<>에 따라 정렬되는 셋
set<Elem, op>	기본적으로 op에 따라 정렬되는 셋
multiset<Elem>	기본적으로 less<>에 따라 정렬되는 멀티셋
multiset<Elem, op>	기본적으로 op에 따라 정렬되는 멀티셋

 

 

수정하지 않는 연산

연산	설명
c.key_comp()	비교 기준 반환
c.value_comp()	값을 비교하는 기준 반환
c.empty()	컨테이너가 비었는지 여부를 바노한
c.size()	현재 요소의 수를 반환
c.max_size()	최대 저장 가능한 요소의 수를 반환
c1 == c2	c1이 c2와 같은지 반환
c1 != c2	c1이 c2와 다른지 반환
c1 < c2	c1이 c2보다 작은지 반환
c1 > c2	c1이 c2보다 큰지 반환
c1 <= c2	c1이 c2보다 작거나 같은지 반환
c1 <= c2	c1이 c2보다 크거나 같은지 반환

 

 

특별 검색 연산

연산	설명
c.count(val)	값이 val인 요소의 수를 반환
c.find(val)	값이 val인 요소의 첫 번째 요소의 위치를 반환, 없는 경우 end() 반환
c.lower_bound(val)	val이 삽입될 첫 번째 위치 반환
c.upper_bound(val)	val이 삽입될 마지막 위치 반환
c.equal_range(val)	val과 같은 값을 갖는 모든 요소의 범위

 

 

할당

할당 연산에서 두 컨테이너는 같은 자료형을 가져야 한다.

또한 비교 기준은 다르더라도 비교 기준의 자료형은 같아야 한다.

연산	설명
c = c2	c2의 모든 요소를 c에 할당
c = rv	rv의 모든 요소를 c에 할당
c = initlist	초기화자 목록의 모든 내용을 c에 할당
c1.swap(c2)	c1과 c2의 데이터를 교환
swap(c1,c2)	c1과 c2의 데이터를 교환

 

 

반복자

연산	설명
c.begin()	첫 번째 요소에 대한 양방향 반복자 반환
c.end()	마지막 요소의 다음 위치에 대한 양방향 반복자 반환
c.cbegin()	첫 번째 요소에 대한 양방향 상수 반복자 반환 ( C++11 이후 지원 )
c.cend()	마지막 요소의 다음 위치에 대한 양방향 상수 반복자 반환 ( C++11 이후 지원 )
c.rbegin()	역방향 반복에서의 첫 번째 요소에 대한 역방향 반복자 반환
c.rend()	역방향 반복에서의 마지막 요소의 다음 위치에 대한 역방향 반복자 반환
c.crbegin()	역방향 반복에서의 첫 번째 요소에 대한 역방향 상수 반복자 반환 ( C++11 이후 지원 )
c.crend()	역방향 반복에서의 마지막 요소의 다음 위치에 대한 역방향 상수 반복자 반환 ( C++11 이후 지원 )

 

 

요소 삽입과 제거

연산	설명
c.insert(val)	val의 복사본 삽입 후 새 요소의 위치를 반환,  셋의 경우 삽입 성공 여부 반환
c.insert(pos,val)	val의 복사본 삽입 후 새 요소의 위치 반환, pos는 삽입 연산 시 검색을 시작할 위치에 대한 힌트
c.insert(beg,end)	범위 [beg,end) 내의 모든 요소의 복사본 삽입, 반환값 없음
c.insert(initlist)	초기화자 목록의 모든 요소의 복사본 삽입, 반환값 없음 ( C++11 이후 지원 )
c.emplace(args...)	args로 초기화된 요소의 복사본 삽입 후 새 요소의 위치 반환, 셋의 경우 삽입 성공 여부 반환 ( C++11 이후 지원 )
c.emplace_hint(pos,args...)	args로 초기화된 요소의 복사본 삽입 후 새 요소의 위치 반환, pos는 삽입 연산시 검색을 시작할 위치에 대한 힌트
c.erase(val)	val과 같은 요소를 모두 제거한 뒤 제거한 요소의 수 반환
c.erase(pos)	반복자 위치 pos에 있는 요소를 제거한 후 다음 위치 반환 ( C++11 이전은 반환값 없음 )
c.erase(beg,end)	범위 [beg, end)내 요소를 모두 제거한 후 다음 위치 반환 ( C++11 이전은 반환값 없음 )
c.clear()	모든 요소를 제거한다