[C++] set container 정리 및 사용법

• 안녕하세요. BlockDMask 입니다 !

• 오늘은 연관 컨테이너 set, multiset, map, multimap 중 set에 대해 학습해보겠습니다.

• 순서는 set container -> set의 사용법 -> set의 생성자와 연산자 -> set의 멤버 함수 -> 다양한 듯 다양하지 않은 예제 순으로 정리 해보겠습니다.

• 우선 연관컨테이너들의 공통적인 특징은 아래와 같습니다.
  1. 노드 기반 컨테이너
  2. 균형 이진트리로 구현
  3. 멤버 변수, 생성자 등이 99프로 같습니다. 

1) set container

• 연관 컨테이너(associative container) 중 하나입니다.
  
  
• 노드 기반 컨테이너 이며 균형 이진트리로 구현되어있습니다.
  
  
• Key라 불리는 원소들의 집합으로 이루어진 컨테이너 입니다. (원소 = key)
  
  
• key값은 중복이 허용 되지않습니다.
  
  
• 원소가 insert 멤버 함수에 의해 삽입이 되면, 원소는 자동으로 정렬 됩니다.
  
  
• default 정렬기준은 less(오름차순) 입니다.
  
  
• 그림으로 보겠습니다.
• 
  
  
• 그림에서 보면 알듯이 inorder traversal (중위순회) 를 통하여 순서대로 출력이 가능합니다.
  (iterator는 자동으로 inorder traversal 순서대로 출력해줍니다.)

2) set의 사용법

• <set> 헤더 파일에 들어있습니다.
  
• using namespace std; 를 선언해주면 편리합니다.
  
• 기본 선언 방법은 : set< [Data Type] > [변수 이름]; 입니다.
  ex1) set<int> s;
  ex2) set<pair<int, string> > s;

3) set의 생성자와 연산자

• set<int> s;
  - 기본 선언 방법.
  
  
• set<int> s(pred);
  - pred를 통해 정렬기준을 세웁니다.
  
  
• set<int> s2(s1);
  - s1 을 복사한 s2

• 연산자 ( "==", "!=", "<", ">", "<=", ">=" ) 사용 가능합니다.

4) set의 멤버 함수

1. set<int> s; 기준으로 작성하겠습니다.
2. set<int>::iterator iter, start, end; 로 반복자 세개 선언하겠습니다.
3. int k 는 원소입니다.

• s.begin();
  - 맨 첫번째 원소를 가리키는 반복자를 리턴(참조)합니다.
  - iter = s.begin(); 으로 사용합니다.

• s.end();
  - 맨 마지막 원소(의 다음)를 가리키는 원소의 끝부분을 알 때 사용합니다.
  - 반복자를 리턴(참조)합니다.
  - iter = s.end();
  
  
• s.rbegin();
  

• s.rend();
  - begin(), end() 와 반대로 작동하는 멤버함수들입니다.
  - 역으로 출력하고 싶을때 사용합니다.
  - 이런 식으로 사용합니다.
  

  for(iter = s.rbegin(); iter != s.rend(); iter++){
      cout << * iter << endl;
  }

  
  
  
• s.clear();
  - 모든 원소를 제거합니다.
  
  
• s.count(k);
  - 원소 k 의 갯수를 반환합니다
  - set에서는 무조건  0,1 개 겠죠 ? -> multiset은 키값이 중복이 가능하기때문에 거기서 쓰입니다.
  
  
• s.empty();
  - set s가 비어있는지 확인합니다.
  

• s.insert(k);
  - 원소 k를 삽입합니다.
  - 삽입시에 자동으로 정렬된 위치에 삽입됩니다.
  - 삽입이 성공 실패에 대한 여부는 리턴값 (pair<iterator, bool>) 으로 나오게됩니다.
  - pair<iterator, bool>에서 pair.first는 삽입한 원소를 가리키는 반복자 이고, pair.second는 성공(true), 실패(false)를 나타냅니다.
  
  
• s.insert(iter, k);
  - iter가 가리키는 위치 부터 k를 삽입할 위치를 탐색하여 삽입합니다.

• s.erase(iter);
  - iter가 가리키는 원소를 제거합니다.
  - 제거 한다음 제거 한 원소 다음 원소를 가리키는 반복자를 리턴합니다.
  
  
• s.erase(start, end);
  - [start, end) 범위의 원소를 모두 제거합니다.
  
  
• s.find(k);
  - 원소 k를 가리키는 반복자를 반환합니다.
  - 원소 k가 없다면 s.end() 와 같은 반복자를 반환합니다.

• s2.swap(s1);
  - s1과 s2를 바꿔줍니다.
  
  
• s.upper_bound(k);
  - 원소 k가 끝나는 구간의 반복자 입니다.
  
  
• s.lower_bound(k);
  - 원소 k가 시작하는 구간의 반복자 입니다.

• s.equal_range(k);    
  - 원소 k가 시작하는 구간과 끝나는 구간의 반복자 pair 객체를 반환합니다.
  - upper_bound(k), lower_bound(k) 가 합쳐진 멤버함수
  
  

• s.value_comp();
  
• s.key_comp();
  - 정렬 기준 조건자를 반환합니다.
  - set 컨테이너에서는 두개의 함수 반환형이 같습니다.
  
  

• s.size();
  - 사이즈(원소의 갯수)를 반환합니다.
  
  
• s.max_size();
  - 최대 사이즈(남은 메모리 크기)를 반환합니다.

5) 다양한 듯 다양하지 않은 예제

test) insert, insert(중복값), find(존재하는 값), find(존재하지 않는 값)

#include<iostream>
#include<set>
using namespace std;
 
int main(void){
    set<int> s;
 
    s.insert(40);    
    s.insert(10);
    s.insert(80);
    s.insert(30);
    s.insert(70);
    s.insert(60);
    s.insert(20);
    s.insert(50);
 
    set<int>::iterator iter;
    for(iter = s.begin(); iter != s.end(); iter++){
        cout << *iter << " " ;
    }
    cout << endl;
    
     
    //중복 값 넣어보기. 
    s.insert(20); 
    for(iter = s.begin(); iter != s.end(); iter++){
        cout << *iter << " " ;
    }    
    cout << endl;    
    
    //존재 하는 원소 찾기
    iter = s.find(30);
    if(iter != s.end()){
        cout << *iter << " : 존재 " << endl; 
    }else{
        cout << "존재하지 않음 " << endl; 
    }
 
    //존재 하지 않는 원소 찾기    
    iter = s.find(333);
    if(iter != s.end()){
        cout << *iter << " : 존재 " << endl; 
    }else{
        cout << "존재하지 않음 " << endl; 
    }
    
    
    return 0;    
}

• 결과
  

<참고> 

http://www.cplusplus.com/reference/set/set/

https://en.wikipedia.org/wiki/Associative_containers