[STL] set 정리 및 예제

[STL] set 정리 및 예제

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

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

템플릿 형식
template<typename Key , typename Pred=less<Key> , typename Allocator=allocator<key>> class set	Key는 set 컨테이너 원소의 형식이며, Pred는 set의 정렬 기준인 조건자이다. 기본 조건자는 less 이다.

생성자
set s;	s는 빈 컨테이너이다.
set s(pred)	s는 빈 컨테이너로 정렬 기준은 pred 조건자를 사용한다
set s(s2)	s는 s2 컨테이너의 복사본이다.
set s(b,e)	s는 반복자 구간 [b,e)로 초기화된 원소를 갖는다.
set s(b,e, pred)	s는 반복자 구간 [b,e)로 초기화된 원소를 갖는다. 정렬 기준은 pred 조건자를 이용한다

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

연산자
s1 == s2	s1과 s2의 모든 원소가 같은가? (bool)
s1 != s2	s1과 s2의 모든 원소 중 하나라도 다른 원소가 있는가
s1 < s2	문자열 비교처럼 s2가 s1보다 큰가?
s1 > s2	문자열 비교처럼 s2가 s1 보다 작은가?

멤버 형식
allocator_type	메모리 관리자 형식
const_iterator	const 반복자 형식
const_pointer	const value_type* 형식
const_reference	const value_type& 형식
const_reverse_iterator	const의 역 반복자 형식
difference_type	두 반복자 차이의 형식
iterator	반복자 형식
key_compare	키 (key) 조건자(비교) 형식 (set은 key 가 value이므로 value_compare와 같다
key_type	키(key)의 형식
pointer	value_type* 형식
reference	value_type& 형식
reverse_iterator	역 반복자 형식
size_type	첨자(index)나 원소의 개수 등의 형식
value_compare	원소 조건자 형식
value_type	원소의 형식

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

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

set은 모든 원소가 유일하다. 원소의 중복을 허용해야 한다면 multiset 을 사용해야 한다.

정렬 기준은 템플릿 매개변수에 지정할 수 있으며, 기본 정렬 기준은 less 조건자이다.

연관 컨테이너는 시퀀스 컨테이너가 제공하는 순서와 관련된 함수류인 push_back(), push_front(), pop_back(), pop_front()와 시작, 끝 원소의 참조 멤버 함수 fron(), back()을 제공하지 않는다.

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

연관 컨테이너는 양방향 반복자를 지원하며 멤버 변수 begin(), end(), rbegin(), rend()는 순차열의 시작과 끝을 가리키는 반복자를 반환한다.

#include <iostream> #include <set> #include <functional> using namespace std; int main(){     set<int> s;     pair<set<int>::iterator, bool> pr;     pr = s.insert(50);    // insert 결과 pair 반환     s.insert(40);     s.insert(80);     if (true == pr.second)         cout << *pr.first << " 삽입 성공!" << endl;     else         cout << *pr.first << "가 이미 있습니다. 삽입 실패! " << endl;     set<int>::iterator iter;     for (iter = s.begin(); iter != s.end(); ++iter){         cout << *iter << " ";     }     cout << endl;     pr = s.insert(50);        // 중복 값 insert     if (true == pr.second)         cout << *pr.first << " 삽입 성공!" << endl;     else         cout << *pr.first << "가 이미 있습니다. 삽입 실패!" << endl;     for (iter = s.begin(); iter != s.end(); ++iter){         cout << *iter << " ";     }     cout << endl;     s.insert(pr.first, 60);        // 50 위치에 값 50 바로 삽입     for (iter = s.begin(); iter != s.end(); ++iter){         cout << *iter << " ";     }     cout << endl;     set<int, greater<int>> s2;        // 내림차순 정렬     s2.insert(50);     s2.insert(30);     s2.insert(80);     s2.insert(40);     s2.insert(10);     s2.insert(70);     s2.insert(90);     for (iter = s2.begin(); iter != s2.end(); ++iter){         cout << *iter << " ";     }     cout << endl;     // key_compare, value_compare 확인     cout << "key_compare less : " << typeid(s.key_comp()).name() << endl;     cout << "key_compare greater : " << typeid(s2.key_comp()).name() << endl;     cout << "value_compare less : " << typeid(s.value_comp()).name() << endl;     cout << "value_compare greater : " << typeid(s2.value_comp()).name() << endl;     return 0; }

결과 : 50 삽입 성공! 40 50 80 50가 이미 있습니다. 삽입 실패! 40 50 80 40 50 60 80 90 80 70 50 40 30 10 key_compare less : struct std::less<int> key_compare greater : struct std::greater<int> value_compare less : struct std::less<int> value_compare greater : struct std::greater<int>

set 에는 원소를 insert() 하면 정렬 기준에 따라 정렬된 위치에 insert가 된다.

insert() 결과로 삽입 성공 여부 pair를 반환한다.

pair.first 는 값 위치의 iterator 이며, pair.second 는 삽입 성공 여부 bool 형이 지정된다.

set은 중복을 허용하지 않기 때문에 존재하는 값을 insert 하면 실패하게 된다.

key_comp()는 컨테이너의 key의 정렬 기준을 반환하고, value_comp()는 원소 값의 정렬 기준을 반환한다.

set 에서는 key가 value 이므로 같은 값을 반환함을 볼 수 있다.

#include <iostream> #include <set> #include <functional> using namespace std; int main(){     set<int> s;     s.insert(40);     s.insert(30);     s.insert(50);     s.insert(80);     s.insert(10);     s.insert(90);      s.insert(70);     set<int>::iterator iter;     for (iter = s.begin(); iter != s.end(); ++iter)         cout << *iter << " ";     cout << endl;     // count는 해당 원소의 개수를 반환한다. set은 중복을 허용하지 않으므로 1 또는 0이다.     cout << "원소 50의 개수 : " << s.count(50) << endl;     cout << "원소 100의 개수 : " << s.count(100) << endl;     // find는 해당 원소를 찾는다. 원소가 없으면 end() 를 반환한다.     iter = s.find(30);     if (iter != s.end())         cout << *iter << "가 s에 있다" << endl;     else         cout << "30이 s에 없다." << endl;          set<int>::iterator iter_lower;     set<int>::iterator iter_upper;     iter_lower = s.lower_bound(30);        // 30 원소의 첫번째     iter_upper = s.upper_bound(30);        // 30 원소 마지막의 다음 원소     cout << *iter_lower << endl;     cout << *iter_upper << endl;     iter_lower = s.lower_bound(55);     iter_upper = s.upper_bound(55);          // 55의 첫번째 원소와 다음원소를 가리키는 iter가 같으면 값이 없다     if (iter_lower != iter_upper)                 cout << "55가 s에 있다" << endl;     else         cout << "55가 s에 없다" << endl;     // equal_range는 해당 원소의 범위를 pair로 반환한다.     pair<set<int>::iterator, set<int>::iterator> iter_pair;          iter_pair = s.equal_range(30);     cout << *iter_pair.first << endl;     cout << *iter_pair.second << endl;     iter_pair = s.equal_range(55);     if (iter_pair.first != iter_pair.second)         cout << "55가 s에 있다 " << endl;     else         cout << "55가 s에 없다 " << endl;     return 0; }

결과 : 10 30 40 70 80 90 원소 50의 개수 : 1 원소 100의 개수 : 0 30가 s에 있다 30 40 55가 s에 없다 30 40 55가 s에 없다

count() 함수는 컨테이너의 해당 원소 갯수를 반환한다. set은 중복을 허용하지 않으므로 1 또는 0 이 반환된다.

find() 함수는 해당 원소의 iter 를 찾아서 반환한다. 해당 원소가 컨테이너에 없다면 end()에 해당하는 끝표시 위치를 반환한다.

연관 컨테이너는 key를 이용하여 노드를 찾을 때 == 연산을 사용하지 않는다. 연관 컨테이너는 정렬 기준에 의해 key가 정렬되어 있으므로 컨테이너의 정렬 기준 조건자를 이용해 찾기 연산을 수행한다.

ex > (!s.key_comp()(a,b) && !s.key_comp()(b,a)) 로 원소와 노드 값을 비교한다.

lower_bound()는 해당 원소 중 첫번째 위치를 반환하고 upper_bound()는 해당 원소 마지막 위치 다음 위치를 반환 한다

따라서 해당 원소의 구간은 [lower_bound(), upper_bound()) 가 된다

이 구간 pair 를 찾아주는 함수가 equal_range() 이다.

출처: https://hyeonstorage.tistory.com/327?category=614599 [개발이 하고 싶어요]