[C++ STL] '연관 컨테이너 - set'

'set 컨테이너'는 key값 1개를 저장하는 형태의 노드 집합으로 이루어져 있습니다. 또한, key값은 중복이 될 수 없습니다. 만약 중복을 허용하고싶다면 'multiset 컨테이너'를 사용하셔야 합니다. 'set 컨테이너'뿐만 아니라 모든 연관 컨테이너(set, multiset, map, multimap)는 '균형 이진 트리'로 구현되어 있습니다. 'set 컨테이너' 내부의 모습은 다음과 같습니다.

 

다음으로 'set 컨테이너'가 제공하는 인터페이스를 알아보겠습니다. 모든 연관 컨테이너는 같은 인터페이스를 제공하기 때문에 하나만 제대로 익혀두면 나머지 것들에도 적용시킬 수 있습니다.

생성자(Constructor)
set s	s는 빈 컨테이너입니다.
set s{ pred }	s는 빈 컨테이너이고, 정렬 기준은 pred 조건자를 사용합니다.
set s{ s2 }	s는 s2 컨테이너의 복사본입니다.(복사 생성자 호출)
set s{ b, e }	s는 순차열 [b, e)로 초기화된 원소를 갖습니다.
sest s{ b, e, pred }	위와 동일하며, 추가로 정렬 기준은 pred 조건자로 설정됩니다.

멤버 함수
s.begin()	s의 첫 원소를 가리키는 반복자를 반환합니다.
s.end()	s의 끝을 가리키는 반복자를 반환합니다.
s.clear()	s의 모든 원소를 제거합니다.
s.empty()	s가 비었는지 확인합니다.
s.erase(p)	p가 가리키는 원소를 제거합니다.
s.erase(b, e)	순차열 [b, e)의 모든 원소를 제거합니다.
s.erase(k)	k 원소를 모두 제거합니다.
s.insert(k)	s 컨테이너에 k를 삽입합니다. pair 객체를 반환합니다.
s.insert(p, k)	p가 가리키는 위치부터 k를 삽입합니다.
s.insert(b, e)	순차열 [b, e)의 원소를 삽입합니다.
s.size()	s 컨테이너의 원소의 개수를 반환합니다.
s.max_size()	s가 담을 수 있는 최대 원소의 개수를 반환합니다.
s.swap(s2)	s와 s2를 스왑합니다.
s.key_comp()	s의 key 정렬 기준인 조건자를 반환합니다.(key_compare 타입)
s.value_comp()	s의 value 정렬 기준인 조건자를 반환합니다.(value_compare 타입)
s.lower_bound(k)	k의 시작 구간을 가리키는 반복자를 반환합니다.
s.upper_bound(k)	k의 끝 구간을 가리키는 반복자를 반환합니다.
s.find(k)	k 원소의 위치를 가리키는 반복자를 반환합니다.
s.equal_range(k)	k 원소의 반복자 구간인 pair 객체를 반환합니다.
s.count(k)	원소 k의 개수를 반환합니다.

 

set 컨테이너는 원소(key)를 저장(삽입)하는 단 하나의 멤버 함수 insert()를 제공합니다. 이때, 삽입된 원소는 자동으로 정렬됩니다. 모든 연관 컨테이너는 그에 따른 정렬 기준(pred 조건자)이 존재하며, default는 less 조건자(오름차순)입니다. 그리고 위에 보시면 'pair 객체'를 반환하는 멤버 함수들이 있습니다. 'pair 객체'는 이름에서 알 수 있듯이 2개의 값(객체)을 하나로 묶어주는 객체입니다. 원형은 아래와 같습니다.

template<class T1, class T2> 
struct pair {
    T1 first;
    T2 second;
}

 

다음은 insert()를 통한 pair 객체의 활용에 대한 예제입니다.

#include <iostream>
#include <set>
using namespace std;

void main() {
    set<int> s;
    pair<set<int>::iterator, bool> pr; // pair 객체를 생성합니다.
    
    pr = s.insert(50);
    if (pr.second == true)
        cout << *pr.first << " Success" << endl;
    else
        cout << *pr.first << " Fail"  << endl;
        
    pr = s.insert(50); // 50 원소가 이미 있기 때문에 이번에는 삽입이 실패합니다.
    if (pr.second == true)
        cout << *pr.first << " Success" << endl;
    else
        cout << *pr.first << " Fail"  << endl;
}

 

마지막으로, key_compare 타입에 대해서 알아보겠습니다. 'key_compare'은 이름에서 알 수 있듯이 같은 기준의 조건자를 가진 두 객체를 비교하기 위해 사용됩니다. 다음은 cpp reference(http://www.cplusplus.com/reference/set/set/key_comp/)에서 발췌한 예제입니다.

#include <iostream>
#include <set>
using namespace std;

void main() {
    set<int> s;
    int highest;
    
    set<int>::key_compare myComp = s.key_comp();
    
    for (int i = 0; i <= 5; ++i)
        s.insert(i);
        
    highest = *s.rbegin(); // 끝 원소를 저장합니다.
    set<int>::iterator iter = s.begin();
    do {
        cout << *iter << " ";
    } while (myComp(*(++iter), highest));
}