[STL] set, multiset 정리

 

이전 포스팅까지는 시퀀스 컨테이너에 대해 정리해 보았습니다.

이번 포스팅부터는 연관 컨테이너에 관한 내용을 다룰 계획입니다.

 

---

01. 연관 컨테이너

연관 컨테이너의 정의

시퀀스 컨테이너와 달리 컨테이너의 원소들을 순차적으로 삽입하지 않고, 원소 추가시 특정 정렬 기준(디폴트 less)에 의해 자동 정렬되는 컨테이너입니다.

 

연관 컨테이너의 종류

• set
• multiset
• map
• multimap

 

연관 컨테이너의 특징

• 모든 연관 컨테이너는 인터페이스(생성자, 멤버 함수, 연산자)를 동일하게 사용하고 있습니다. 
• 연관 컨테이너는 균형 이진 트리를 사용하므로, 원소를 빠르게 찾을 수 있습니다.(로그 시간 복잡도)
• key를 정렬 기준에 맞춰 균형 이진 트리에 저장하며, 이 key는 삽입, 검색, 제거 등에 모두 이용하고 변경할 수 없습니다. 
• 양방향 반복자를 지원합니다.
• 순차적으로 원소가 추가되지 않기 때문에 다음 함수들은 지원하지 않습니다.
  • push_back()
  • push_front()
  • pop_back()
  • pop_front()
  • front()
  • back()

 

02. set

set의 구조

• set에서 원소(10, 20, 30, 40, 50, 60, 70)을 key라고 하고, 이 키를 비교하여 원소를 정렬합니다.
• 원소의 중복은 허용하지 않습니다.
• 따로 정렬기준을 정해주지 않았을 때, 정렬 기준으로 less를 이용합니다.
• 정렬 기준이 less일 때 원소를 삽입하면, 삽입된 원소는 이진탐색트리와 같이 부모노드의 왼쪽 자식노드는 부모노드보다 크기가 작고, 부모노드의 오른쪽 자식노드는 부모노드보다 크기가 크도록 배치됩니다.
• 반복자의 탐색 순서는 inorder(중위순회) 이진 트리 탐색을 사용합니다.
• 따라서 정렬 기준이 less일 경우 오름차순으로 출력됩니다.

 

템플릿 형식

Key는 set 컨테이너의 원소 형식이며, Pred는 set의 정렬 기준인 조건자입니다.

 

 

생성자

<초기화>

set<데이터 타입, 조건자> s;	s는 빈 컨테이너
set<데이터 타입, 조건자> s(s2);	s는 s2 컨테이너의 복사본
set<데이터 타입, 조건자> s(b,e);	s는 반복자 구간 [b, e)로 초기화된 원소를 갖는다.

 

멤버함수

<요소 삽입 및 삭제>

insert(k)	k를 삽입하며, 원소를 가리키는 반복자와 성공 여부의 bool 값인 pair 객체를 반환한다.
insert(p,k)	p가 가리키는 위치부터 빠르게 k를 삽입하며, 삽입한 원소를 가리키는 반복자를 반환한다.
insert(b.e)	반복자 구간 [b,e)의 원소를 삽입한다.
erase(p)	p가 가리키는 원소를 제거하며, 다음 원소를 가리키는 반복자를 반환한다.
erase(b,e)	반복자 구간 [b, e)의 모든 원소를 제거하며, 다음 원소를 가리키는 반복자를 반환한다.
clear()	모든 원소를 제거한다.

 

<요소 접근>

begin()	첫 원소를 가리키는 반복자를 반환한다
end()	끝을 가리키는 반복자를 반환한다.
rbegin()	역 순차열의 첫 원소를 가리키는 반복자를 반환한다.
rend()	역 순차열의 끝을 표시하는 반복자를 반환한다.

 

<요소 검색>

find(k)	k의 원소의 위치를 가리키는 반복자를 반환한다.
lower_bound(k)	k의 시작 구간을 가리키는 반복자를 반환한다.
upper_bound(k)	k의 끝 구간을 가리키는 반복자를 반환한다.
equal_range(k)	k 원소의 반복자 구간인 pair 객체를 반환한다.

 

<기타>

size()	원소의 개수를 반환한다.
count(k)	원소 k의 개수를 반환한다.
max_size()	set 컨테이너가 담을 수 있는 최대 원소의 개수를 반환한다.
empty()	비었는지 조사한다.
key_comp()	key 정렬 기준인 조건자를 반환한다.
value_comp()	value 정렬 기준인 조건자를 반환한다.
swap(s2)	s2와 swap한다.

 

연산자

s1==s2	s1과 s2의 모든 원소가 같다면 참
s1!=s2	s1과 s2의 모든 원소 중 하나라도 다른 원소가 있다면 참
s1<s2	s2가 s1보다 크면 참
s1<=s2	s2가 s1보다 크거나 같으면 참
s1>s2	s1이 s2보다 크면 참
s1>=s2	s1이 s2보다 크거나 같으면 참

 

set 예제

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

int main()
{
    // int형의 원소를 가진 빈 set 컨테이너 생성
    set<int> s1;				
    
    s1.insert(30);
    s1.insert(40);
    s1.insert(10);
    s1.insert(50);
    s1.insert(20);
    
    // greater 조건자는 모든 노드의 부모노드가 왼쪽 자식 노드보다 작고 
    // 오른쪽 자식 노드보다 큰 노드가 되도록 정렬해줍니다.
    set<int, greater<int>> s2;			
    s2.insert(30);
    s2.insert(40);
    s2.insert(10);
    s2.insert(50);
    s2.insert(20);
    
    set<int>::iterator iter;
    iter=s1.begin();
    cout<<"s1에서 30의 개수: "<<s1.count(30)<<endl;
    
    int num=70;
    iter=s1.find(num);
    // 원소를 찾지 못하면 끝 표시 반복자를 반환합니다.
    if(iter!=s1.end())      
        cout<<"s1에 "<<num<<"이 존재합니다."<<endl;
    else
        cout<<"s1에 "<<num<<"이 존재하지 않습니다."<<endl;
    
    pair<set<int>::iterator, bool> pr;
    pr=s1.insert(60);
    cout<<"s1에 "<<*pr.first<<" 삽입 성공 여부: "<<pr.second<<endl;
    pr=s1.insert(30);
    cout<<"s1에 "<<*pr.first<<" 삽입 성공 여부: "<<pr.second<<endl;
   
    // 출력
    cout<<"s1의 원소들: ";
    for(iter=s1.begin(); iter!=s1.end(); iter++)
        cout<<*iter<<" ";
    cout<<endl;
    
    cout<<"s2의 원소들: ";
    for(iter=s2.begin(); iter!=s2.end(); iter++)
        cout<<*iter<<" ";
    cout<<endl;
    
    return 0;
}

 

03. multiset

• multiset은 set과 다르게 중복 원소를 컨테이너에 저장할 수 있습니다.
• 따라서 lower_bound(), upper_bound(), equal_range() 함수를 유용하게 사용할 수 있습니다.

 

multiset 예제

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

int main()
{
    multiset<int> s={10, 20, 30, 40, 50};
	
    multiset<int>::iterator iter;
    s.insert(30);
    iter=s.lower_bound(30);
    cout<<"lower_iter: "<<*iter<<endl;
    iter=s.upper_bound(30);
    cout<<"upper_iter: "<<*iter<<endl;
	
    pair<set<int>::iterator, set<int>::iterator> pr;
    pr=s.equal_range(30);
    cout<<"구간 [lower_iter, upper_iter)의 순차열: ";
    for(iter=pr.first; iter!=pr.second; ++iter)
	    cout<<*iter<<" ";
    cout<<endl;
    
    return 0;
}