[STL] set 정리 및 예제[STL] set 정리 및 예제

Posted at 2014. 12. 28. 19:04 | Posted in C++/STL



facebook에 글올리기



[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* 형식 
 referencevalue_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()는 순차열의 시작과 끝을 가리키는 반복자를 반환한다.



 Colored By Color Scripter

#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 이므로 같은 값을 반환함을 볼 수 있다.



 Colored By Color Scripter

#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() 이다.

 

'C++ > STL' 카테고리의 다른 글

[STL] map 정리 및 예제  (0) 2014.12.28
[STL] multiset 정리 및 예제  (0) 2014.12.28
[STL] set 정리 및 예제  (0) 2014.12.28
[STL] list 정리 및 예제  (0) 2014.12.28
[STL] deque 정리 및 예제  (1) 2014.12.27
[STL] vector 벡터 정리 및 예제  (0) 2014.12.26
이웃추가
facebook에 글올리기
, ,

Name __

Password __

Link (Your Website)

Comment

SECRET | 비밀글로 남기기