set

이 장에서는 연관 컨테이너에 대해서 살펴본다.

연관 컨테이너가 시퀀스 컨테이너와 다른 점은 연관 컨테이너는 특정 정렬 규칙에 따라 저장 원소가 컨테이너에 정렬된다.

STL의 표준 연관 컨테이너는 set, map, multiset, multimap 네 가지가 있으며 균형 이진 트리로 구현된다.

시퀀스 컨테이너와 달리 모든 연관컨테이너(set, multiset, map, multimap)은 같은 인터페이스를 제공한다.

 

set컨테이너는 연관 컨테이너 중 단순한 컨테이너로, key라고 불리는 원소(value)의 집합으로 이루어진 컨테이너다.

모든 연관 컨테이너는 노드 기반 컨테이너이며 균형 이진 트리로 구현되므로 균형 이진 트리의 모든 특징을 가진다.

 

set의 주요 인터페이스와 특징

 

생성자

• set s: set은 빈 컨테이너.
• set s(pred): s는 빈 컨테이너. 정렬 기준은 pred 사용
• set s(s2): 복사생성자 호출
• set s(b,e): 반복자 구간 [b, e)에서 초기화
• set s(b,e, pred): 위와 같은데 정렬기준 pred 사용

멤버 함수

• p = s.begin() : p는 s의 첫 원소를 가리킴(const, 비 const 버전 있음)
• s.clear(): s의 모든 원소 제거
• n = s.count(k): 원소 k 개수 반환
• s.empty(): s가 비었는지 조사
• p = s.end(): s의 끝을 표시하는 반복자
• pr = s.equal_range(k): pr은 k 원소의 반복자 구간인 pair 객체
• q = s.erase(p) : p가 가리키는 원소를 제거한다. q는 다음 원소를 가리킨다.
• q = s.erase(b,e) : 반복자 구간 [b, e)의 모든 원소를 제거한다. q는 다음 원소다.
• n = s.erase(k) : k와 데이터가 같은 원소를 모두 제거한다. 제거한 개수를 반환한다
• p = s.find(k) : k와 데이터가 같은 원소의 반복자를 반환한다.
• pr = s.insert(k) :  s 컨테이너에 k를 삽입한다. pr은 삽입한 원소를 가리키는 반복자와 성공 여부의 bool 값인 pair 객체다.
• q= s.insert(p,k): p가 가리키는 위치부터 빠르게 k를 삽입한다. 삽입한 원소를 가리키는 반복자를 반환한다.
• s.insert(b,e) : 반복자 구간 [b,e)의 원소를 삽입한다.
• pred = s.key_comp() : pred는 s의 key 정렬 기준인 조건자다(key_compare 타입)
• p = s.lower_bound(k) : p는 k의 시작 구간을 가리키는 반복자다(const, 비 const 버전이 있음)
• n = s.max_size() : s가 담을 수 있는 최대 원소의 개수를 반환한다.
• p = s.rbegin() : p는 s의 역 순차열의 첫 원소를 가리키는 반복자다(const, 비 const 버전이 있음)
• p = s.rend() : p는 s의 역 순차열의 끝을 표식하는 반복자다(const, 비 const 버전이 있음)
• s.size() : s원소의 개수다
• s.swap(s2) : s와 s2를 swap한다.
• p = s.upper_bound(k) : k의 끝 구간을 가리키는 반복자를 반환한다.(const, 비 const 버전이 있음)
• pred = s.value_comp() : pred는 s의 value 정렬 기준인 조건자다(value_compare 타입)

멤버 형식

• allocator_type : 메모리 관리자 형식
• const_iterator : const 반복자 형식
• const_pointer : const value_type* 형식
• const_reference : const value_type& 형식
• const_reverse_iterator : const 역 반복자 형식
• difference_type : 두 반복자 차이의 형식
• iterator : 반복자 형식
• key_compare : 키 조건자(비교) 형식(set에서는 value_compare과 같음)
• key_type : value_type* 형식
• pointer : value_type * 형식
• reference : value_type& 형식
• reverse_iterator : 역 반복자 형식
• size_type : 인덱스나 원소의 개수 등의 형식
• value_compare : 원소 조건자(비교) 형식
• value_type : 원소의 형식

set은 컨테이너에 원소(key)를 저장(삽입)하는 유일한 멤버 함수 insert()를 제공한다

연관 컨테이너는 정렬 기준이 있으므로 insert()에 의해 삽입된 원소는 자동 정렬된다.

set에서 원소를 key라 하며 이 키를 비교하여 내부 원소를 정렬한다.

set에서 모든 원소는 유일하다. 원소의 중복을 허용해야 한다면 multiset을 이용한다.

 

연관 컨테이너는 균형 이진 트리를 사용하므로 찾기 연산(find(), lower_bound(), upper_bound(), equal_range(), count())에 뛰어난 성능(로그 시간)을 보이며 insert() 멤버 함수를 이용한 삽입도 로그 시간 복잡도를 보인다.

 

다음은 예제

#include <iostream>
#include <set>
 
int main()
{
    std::set<int> s;
    s.insert(50);
    s.insert(30);
    s.insert(80);
    s.insert(40);
    s.insert(10);
    s.insert(70);
    s.insert(90);
 
    for (auto elem : s)
    {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
 
    s.insert(50); //중복된 원소 삽입은 실패
    s.insert(50);
 
    for (auto elem : s)
    {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
 
    return 0;
}

set은 원소(key)를 중복 저장할 수 없다.

insert()의 반환값으로 실패를 확인할 수 있다.

반환값은 pair이며 first와 second는 각각 삽입되는 원소(key)의 위치를 가리키는 반복자와 성공여부를 나타내는 bool값이다.

 

다음 예제는 insert() 멤버함수의 실패 시 반환값에 대한 예제이다.

#include <iostream>
#include <set>
 
void Print_isSuccess(std::pair<std::set<int>::iterator, bool> &pair)
{
    std::cout << *pair.first;
    if (pair.second == true)
    {
        std::cout << " 삽입 성공!" << std::endl;
    }
    else
    {
        std::cout << "가 이미 있습니다. 삽입 실패!" << std::endl;
    }
}
int main()
{
    std::set<int> set;
    std::pair<std::set<int>::iterator, bool> pair;
 
    pair = set.insert(50);
    set.insert(40);
    set.insert(80);
 
    Print_isSuccess(pair);
 
    for (auto elem : set)
    {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
 
    pair = set.insert(50);
 
    Print_isSuccess(pair);
 
    for (auto elem : set)
    {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
}

 

연관 컨테이너는 시퀀스 컨테이너처럼 삽입할 위치를 지정하는 버전과 삽입할 구간을 지정하는 버전의 insert()도 제공한다

단, 원소의 삽입 위치를 지정하는 버전은 삽입 위치가 정렬 순서와 맞는다면 바로 삽입되지만 아니라면 인자로 넘긴 반복자부터 탐색하여 로그 시간이 걸린다.

 

연관 컨테이너의 기본 정렬 기준은 조건자 less를 사용한다. 기본 정렬 기준은 템플릿 매개변수를 사용해 바꿀 수 있다.

set은 사용 중인 정렬 기준 조건자를 반환하는 멤버 함수 key_comp()와 value_comp()를 제공한다.

이 때 정렬 기준 형식은 typedef 내장 멤버 형식 key_compare와 value_compare로 제공한다. set은 저장 원소인 값이 곧 비교로 사용되는 키가 되며 그래서 set은 value와 key 타입이 같다.

key_compare와 value_compare는 functor(함수 객체)이다.

 

count() 멤버함수는 원소의 개수를 반환한다.

find() 멤버함수는 원소를 검색해서 해당 인덱스의 반복자를 반환한다.

 

여기서 주의할 점이 있다. 연관 컨테이너의 찾기 관련 멤버 함수는 key를 찾을 때 == 연산을 사용하지 않는다.

연관 컨테이너는 정렬 기준에 의해 key가 정렬되어 있으므로 컨테이너의 정렬 기준 조건자를 이용해 찾기 연산을 수행한다.

예로 set의 정렬 기준이 less라면 less는 < 연산을 수행하므로 비교하는 두 원소 a와 b가 !(a < b) && !(b < a)라면 두 원소는 같다고 판단한다.

s 컨테이너의 정렬 기준을 반환하는 멤버 함수가 key_com()이므로 비교하는 두 원소 a와 b가 !s.key_comp()(a,b) && !s.key_comp()(b,a) 이면 두 원소는 같다(equivalence)고 판단한다.

 

즉 정렬 기준으로 a가 b보다 앞서 있지 않고 b도 a보다 앞서 있지 않다면 a와 b는 같다고 판단한다. 

다음은 예제

lude <iostream>
#include <set>
int main()
{
    std::set<int> set;
    std::cout << ((!set.key_comp()(30, 50) && !set.key_comp()(50, 30)) ? "equal" : "differ");
    std::cout << std::endl;
    std::cout << ((!set.key_comp()(30, 30) && !set.key_comp()(30, 30)) ? "equal" : "differ");
}

 

set의 멤버 함수 lower_bound()와 upper_bound()는 찾은 key를 반복자로 반환하는 멤버함수다.

lower_bound()는 찾은 원소의 시작 반복자를 반환하며 upper_bound()는 찾은 원소의 다음 원소를 가리키는 반복자를 반환한다.

그래서 찾은 원소는 구간 [lower_bound(), upper_bound())로 표현할 수 있으며, lower_bound()와 upper_bound()가 같다면 찾은 원소는 없다. 사실 중복 key를 갖지 않는 set에서 두 멤버 함수는 큰 의미가 있지 않지만 중복 원소를 갖는 multiset이나 multimap에서는 유용하게 쓰인다.

 

equal_range()는 lower_bound()와 upper_bound()의 반복자 쌍을 pair 객체로 반환한다.