[ 혼연 정리 ] 연관 컨테이너 - 2 [ 셋 ]

ㅇ 셋 (set)
 - 셋(set)은 영어 단어 뜻 그대로 집합을 의미한다.
 - 동일한 타입의 데이터를 모아 놓은 것
 - 저장하는 데이터 자체가 키로 사용되고 값은 저장되지 않는다.
 - 셋은 키의 중복을 허용하지 않는다. 멀티셋은 키의 중복 허용

template<class Key, class BinPred = less<Key>, class A = allocator<Key> >
class set { ... }

- class Key : 저장되는 키 타입
- class BinPred : 키를 정렬하기 위한 비교함수, 디폴트 오름차순
- class A = 할당기
- 시퀀스 컨테이너와 마찬가지로 내부에서 사용하는 타입을 정의 하는데 value_type, iterator, const_iterator, reference 등의 같은 이름을 사용한다.
- 이외 다음 세게의 타입을 추가로 정의

 - value_compare : 셋에 꼭 필요치 않은 타입,
 - 생성자

explicit set(const BinPred& comp = BinPred());  // 디폴트 생성자
set(const set& x);      // 복사 생성자
set(InIt first, InIt last, const BinPred& comp = BinPred()); // 반복자 구간 생성자
 
- 세번째 생성자는 반복자 구간의 요소들로 셋을 생성, 반복자 구간은 입력 반복자 이기만 하면 되므로 다른 컨테이너의 구간을 가져 올 수 도 있다.
  만약 중복된 키가 있다면 이때는 한번만 삽입되며 멀티셋이라면 전부 삽입된다. 조건자와 할당기는 원할 경우 변경할 수 있이잠 대개의 경우 디폴트만 해도 무난하다.
 
- 멀티셋은 키의 중복을 허용한다는 것만 빼고는 셋과 동일, 키를 삽입 삭제하는 규칙이 조금 다름

ㅇ 삽입
 - insert 멤버 함수를 사용, 3가지 버전이 제공

pair<iterator, bool> insert(const value_type& val);    //val를 삽입, 위치x
iterator insert(iterator it, const value_type& val);      // val를 삽입, 위치(o)
void insert((iterator first, iterator last);     // 반복자구간 삽입

- 첫번째 버전 : 하나를 셋에 삽입하되 사입 대상이 되는 값 val를 인수로 전달받고 삽입위치는 전달 받지 않음
             키 하나를 삽입하면 삽입된 위치와 성공 여부를 동시에 리턴해야 하므로 pair 구조체가 린턴된다.
  insert를 호출 한 후 성공 여부를 알고 싶다면 리턴된 pair의 second 멤버를 읽어 보고 이 값이 true이면 first멤버에서 삽입된 반복자 위치를 구할 수 있다.
   상입 성공 여부나 삽입된 위치에 관심이 없다면 리턴값은 무시해도 상관없다.
- 첫번째 버젼의 멀티셋 insert의 원형은 조금 다르다. 리턴 타입이 다른데 중복이 허용되므로 val이 셋에 이미 포함되어 있다라도 삽입은 항상 성공한다. 나머지 버젼은 원형 동일

iterator insert(const value_type& val);  // 멀티셋, val를 삽입, 위치x

1 #include <iostream>
2 #include <set>
3
4 using namespace std;
5
6 template<typename C> void dump(const char *desc, C c)
7 {
8     cout.width(12);cout << left << desc << "==> ";
9     copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," "));
10     cout << endl;
11 }
12
13 void main()
14 {
15     int ar[]={1,4,8,1,9,6,3};
16     int i;
17     set<int> s;                            // 디폴트생성자
18     for (i=0;i<sizeof(ar)/sizeof(ar[0]);i++)
19     {
20         s.insert(ar[i]);                // 삽입, 알아서정렬된다.
21     }
22     dump("원본",s);
23
24     set<int> s2=s;                        // 복사생성자
25     dump("사본",s2);
26
27     const char *str="ASDFASDFGHJKL";
28     set<char> sc(&str[0],&str[13]);        // 생성과동시에초기화(일정구간)
29     dump("문자셋",sc);
30 }

- for 루프에 의해 ar배열의 값이 s에 삽입되는 과정

ㅇ 삭제
- 요소를 삭제할때는 erase 함수를 사용

iterator erase(iterator it);     // 반복자가 지정하는 요소 하나 삭제
iterator erase(iterator first, iterator last);    // 구간 삭제
size_type erase(const Key& key);     // 특정키값을 가지는 요소를 찾아서 삭제

ㅇ 검색
- 특정 키를 찾을 때는 find멤버 함수 사용, 상수 버젼과 비상수 버젼이 중복되어 정의 되어 있다.

iterator find(const Key& val);    // 상수 버젼
const_iterator find(const Key& val) const;  // 비상수 버젼

1 #include <iostream>
2 #include <set>
3 #include <algorithm>
4
5 using namespace std;
6
7 void main()
8 {
9      set<int> s;
10      s.insert(1);
11      s.insert(2);
12      s.insert(3);
13
14      set<int>::iterator it;

15      it=s.find(2);
16      if (it != s.end())
17      {
18           cout << *it << endl;
19      }
20      else
21      {
22           cout << "찾는키가없습니다." << endl;
23      }
24 }

 - find 멤버 함수는 정렬되어 있다는 특성을 이용하여 트리 검색을 하므로 훨씬 더 빠르다.
 - 처음부터 순서대로 검색하므로 항상 첫 번째 요소가 검색된다.

 - 중복된 키 중 첫번째 또는 마지막 요소를 찾고 싶으면 lower_bound, upper_bound 함수를 사용해야 하며 둘을 한꺼번에 조사하고 싶으면 equal_range멤버 함수를 사용한다.

iterator lower_bound(const Key& _Key);
iterator upper_bound(const Key& _Key);
pair <iterator, iterator> equal_range (const Key& _Key);

- 예를 들어 다음과 같은 정수 멀티셋에서 7을 찾는다고 해보면 7이 다섯개나 중복되어 있는데 호츌하는 함수에 따라 어떤 7이 검색될지가 달라진다.

-  find 전역 함수와 lower_bound가 찾는 키는 우연히 같지만 이 둘의 검색 속도는 엄청난 차이가 있다.
    upper_bound 함수는 마지막 요소를 찾는 것이 아니라 마지막 요소의 다음을 찾는다는 점을 주의하자

ㅇ 셋의 활용
- 어떤 값의 집합을 관리하는데 중복되어서 안되며 빠른 검색으로 존재 여부를 신속하게 알고 싶을 때 셋을 사용한다.

 1 #include <iostream>
2 #include <string>
3 #include <set>
4
5 using namespace std;
6
7 void main()
8 {
9     set<string> s;
10     string name;
11     char ch;
12     set<string>::iterator it;
13
14     for(;;) {
15         cout << "1:삽입, 2:삭제, 3:보기, 4:검색, 5:종료=> ";
16         cin >> ch;
17         switch (ch) {
18           case '1':
19               cout << "새이름을입력하시오: ";
20               cin >> name;
21               s.insert(name);
22               break;
23           case '2':
24               cout << "삭제할이름을입력하시오: ";
25               cin >> name;
26               s.erase(name);
27               break;
28           case '3':
29               for (it=s.begin();it!=s.end();it++) {
30                   cout << *it << endl;
31               }
32               break;
33           case '4':
34
35               cout << "검색할이름을입력하시오: ";
36               cin >> name;
37               cout << name << "이(가) " << (s.find(name) != s.end() ? "있":"없")
38                   << "습니다." << endl;
39               break;
40           case '5':
41               return;
42         }
43     }
44 }

ps : 출처 및 자세한 내용은  www.WinAPI.co.kr 참고