c++ set & multiset

- set이란?

set은 insert시 원소들이 자동적으로 정렬된다는 특징을 갖는다.

value값은 중복을 허용하지 안는다..

 

set은 value를 노드로 갖는 red black tree(binary search tree의 일종)로 구현 돼있다.

binary search tree의 경우  트리 최악의 높이는 n이다 반면

red black tree는 o(logn)을 갖는다.

 

*multiset은 value값의 중복을 허용하는거 이외에는 set과 동일하다.( value를 갖고 erase시 해당되는 value원소들 모두 삭제)

-해더 파일

#include<set>

 

-생성

set< value_type , compare , allocator>

(multiset은 set대시 multiset으로 바꾸면 된다.)

 

1) value_type: value의 type 지정

2) compare: set의 정렬 기준 (default= 오름 차순)  생략가능

3) allocator: map의 메모리 할당 취소 되는 개체를 나타내는 형식 (defalut= allocator<value>) 생략가능

 

사용 예시)

set<int> s;

set<pair<int,string>> s;

* set<int> s = a와 같이 a set을 s에 복사할 수 있다.

 

 

-함수

 

1)begin():

시작 요소(이진트리의 루트)를 가리키는 정방향 iterator 반환

 

2)end():

마지막 요소 다음 위치(맨 마지막 요소 다음)를 가리키는 정방향iterator 반환

 

3)rbegin():

끝 요소를 가리키는 역방향 iterator 반환

 

4)rend():

시작 요소 전 위치를 가리키는 역방향 iterator 반환

5)empty():

map이 비어있으면 1을 리턴 아니면 0을 리턴

 

6)size():

map에 저장된 요소의 갯수 리턴

 

7)clear():

map에 있는 모든 요소 삭제

 

8)max_size():

    저장 가능한 최대 요소 갯수 리턴

 

 

10) find:

     iterator find (value) value값의 위치를 가리키는 iterator 반환 O(log n)의 시간복잡도

 

11) insert(3가지 유형):

      ->첫번째= pair<iterator,bool> insert (value)  o(log n)의 시간 복잡도를 갖는다.

          ps.가장 많이 쓰인다 사실 이것만 알아도 됨....

   

       ->두번째= iterator insert (iterator position , value)  이며

          position은 value를 삽입시 빠르게 삽입하기 위해 삽입 위치에 대한 힌트를 주는 것이다.  상수 시간(대신 힌트를

          가까운 곳에 줘야 함)

       

       ->세번째= void insert( 다른set의 삽입 할 요소들의 시작 iterator , 다른 set의 삽입 할 요소들의 끝 iterator)

          로 다른 set의 원하는 범위 요소들을 삽입하는 것

          즉 다른 set의 원하는 요소 범위를 현재 set에 복사하는것   요소갯수*o(logn)의 시간 복잡도를 갖는다.

       

 

12)erase:

  *3가지 유형

    ->첫번째= void erase(iterator)    iterator가 가리키는 위치 원속 삭제  시간복잡도:상수시간

    ->두번째= void erase(iterator first , iterator last)   first~last직전원속들 삭제 시간복잡도: 상수시간*원소수

    ->세번째= size_type erase(value)  value값에 해당하는 원소 삭제 시간복잡도:O(log n)

 

13)lower_bound & upper_bound:  

    iterator lower_bound(value) , iterator upper_bound(value) 

    O(log n)의 시간 복잡도

     

    m.lower_bound(value)는 value값 보다 (가장 가까운)작거나 같은 iterator 반환 

    m.upper_bound(value)는 value보다 큰(가장 가까운)  iterator 반화

 

14) equal_range

pair<iterator,iterator> equal_range (value)

O(log n)의 시간 복잡도

 

pair의 첫번째 요소는 lower_bound 결과의 iterator

두번째 요소는 upper_bound 결과의 iterator 이다.

 

15) count

int count (value)

O(log n)의 시간 복잡도

 

set에 value 값을 갖는 요소를 찾는 함수로 없다면 0 있다면 1을 return한다.

(multiset은 존재하면 갯수를 존재하지 않다면 0을)