C++ set 사용법과 설명...

set에 대해 설명하고자 합니다. 사용법도요.

 

아마 set을 사용하려고 검색하셔서 오시게 된 분이시라면,

 

set의 특징을 잘 아시는 분일겁니다.

 

네, set의 특징은 다음과 같습니다.

 

1. 숫자든 문자든 중복을 없엔다.

2. 삽입하는 순서에 상관없이 정렬되서 입력이 된다.

 

이 특징을 모두 만족시킬 수 있는 자료구조는 이진 트리 입니다.

 

즉, set은 벨런스 트리로 Red-Black 트리로 만들어져 있습니다.

 

 

이런식으로 말이죠...

 

이진트리 특성상 삽입과 삭제가 용이합니다. 자료 찾는것도 준수하고요.

 

그럼 사용법을 알아보겠습니다.

 

 

 

 

Set의 초기화

set<자료형> 변수	기본적인 선언방법
set<자료형> 변수(복사할 변수)	선언 후 복사한 값으로 초기화
set<자료형> 변수 = 복사할 변수	서언 후 복사한 값으로 초기화

 

 

#include <iostream>
#include <set>

using namespace std;

int main(void) {

    set<int> s;

    s.insert(1);
    s.insert(200);
    s.insert(-1);
    s.insert(3);

    int arr[] = { 1, 2, 3, 4, 5, 6 };
    set<int> s1(s.begin(), s.end());    //output : s1 = -1, 1, 3, 200
    
    set<int> s2(arr, arr + 6);        //output : s2 = 1, 2, 3, 4, 5, 6
    
    set<int> s3(s1);        //output : s3 = -1, 1, 3, 200
    
    set<int> s4 = s2;        //output : s4 = 1, 2, 3, 4, 5, 6
    

    return 0;
}
​

 

 

 

 

 

 

Set의 반복자(iterator)

s.begin()	set의 시작이 되는 주소 값 반환
s.end()	set의 마지막 부분에 대한 주소 값 반환(정확히는 마지막 뒤 공백구간)
s.rbegin()	set의 마지막 부분을 시작점으로 지정
s.rend()	set의 첫번 째 부분을 마지막점으로 지정
s.cbegin()	begin()과 동일하지만 const로 설정.
s.cend()	end()와 동일하지만 const로 설정
s.crbegin()	rbegin()과 동일하지만 const로 설정
s.crend()	rend()와 동일하지만 const로 설정

 

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int main(void) {

    set<int> s;

    s.insert(1);
    s.insert(200);
    s.insert(-1);
    s.insert(3);

    for_each(s.begin(), s.end(), [](int n) {
        cout << n << endl;        //output : -1, 1, 3, 200
        });

    for_each(s.rbegin(), s.rend(), [](int n) {
        cout << n << endl;        //output : 200, 3, 1, -1
        });
    

    return 0;
}​

 

 

출처 : https://en.cppreference.com/w/cpp/container/vector/rend

 

 

 

 

 

 

Set의 용량(Capacity)

s.empty()	s가 비어있다면 true, 아니면 false
s.size()	s에 저장되어 있는 크기
s.max_size()	s가 가질 수 있는 최대 크기

 

#include <iostream>
#include <set>

using namespace std;

int main(void) {

    set<int> s;

    s.insert(1);
    s.insert(200);
    s.insert(-1);
    s.insert(3);

    cout << s.empty() << endl;        //output : 0(false)

    cout << s.size() << endl;        //output : 4

    cout << s.max_size() << endl;        //output : 214748364

    return 0;
}​

 

 

 

 

 

 

Set의 삽입, 삭제(Modifiers)

s.insert()	s에 값 삽입
s.erase()	s에 저장된 요소 삭제
s.swap()	s1과 s2를 서로 교환
s.clear()	s의 요소들 전부 삭제
s.emplace()	move()를 사용해 객체를 저장
s.emplace_hint()	삽입될 위치에 대한 힌트를 토대로 삽입

 

 

#include <set>

using namespace std;

int main(void){

    set<int> s;

    s.insert(5);
    s.insert(2);
    s.insert(10);
    s.insert(1);
    
    //output : 1, 2, 5, 10
    //////////////////////

    set<int> s1;
    
    s1.emplace(100);
    s1.emplace(50);
    s1.emplace(1);
    s1.emplace(4);

    set<int>::iterator itr = s1.emplace_hint(s1.end(), 101); //삽입속도 빠름
    s1.emplace_hint(itr, 1);    //삽입 속도 느림
    
    //output : 1, 4, 50, 100
    ////////////////////////
    
    set<int> s2;
    s2.insert(10);
    s2.insert(5);
    pair<set<int>::iterator, bool> check = s2.insert(10);

    if (check.second)
        cout << "삽입 완료" << endl;
    else
        cout << "삽입 실패(중복 값)" << endl;
    //output : 삽입 완료


    auto check_2 = s2.emplace(12);

    if (check_2.second)
        cout << "삽입 완료" << endl;
    else
        cout << "삽입 실패(중복 값)" << endl;

    //output : 삽입 실패(중복 값)
    ///////////////////////////////////////////////////

    set<pair<int, int>> s3;

    s3.insert(make_pair(1, 2));    //ok!!
    s3.insert(3, 4);    //error!!
    
    s3.emplace(3, 4);     //ok!!
    s3.emplace(1, 2);   //ok!! put overlap!!

    for(auto itr = s3.begin(); itr != s3.end(); itr++)
        cout << (*itr).first << " " << (*itr).second << endl;
    //output : (1 2) (3 4)

    ////////////////////////////////
    s1.swap(s2);    //s1 and s2 swap

    s3.clear();        //s3 element remove....
    ////////////////////////////////

    set<int> s4 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    s4.erase(s4.find(1));    //output : 2, 3, 4, 5, 6, 7, 8, 9, 10

    s4.erase(s4.begin(), s4.find(7));    //output : 7, 8, 9, 10

    return 0;
}

 

 

insert와 emplace는 기본적인 반환 값이 pair<iterator, bool> 입니다.

즉, pair로 반환이 됩니다.

여기서 pair.first에는 삽입한 위치에 대한 iterator를 반환하고 

pair.second에는 삽입 성공여부에 대한 bool 값이 들어가게 됩니다.

 

insert와 emplace의 차이는 53행과 55행을 보면 알 수 있는데, 

insert는 rvalue에 대한 삽입은 안되지만 emplace는 가능한걸 볼 수 있습니다.

 

이는 emplace의 move연선자로 인한 불필요한 복사생성자의 호출을 제한하기 때문인데,

insert는 main에서 복사생성자 호출로 값이 삽입되지만

emplace는 set객체 내부에서 그 값이 생성되어 복사생성자 호출이 줄어들게됩니다.

(insert는 복사생성자를 2번 호출, emplace는 1번만 호출)

 

이는 c++의 containers library에 있는 모든 자료구조 객체에 있는 기능입니다.

 

 

emplace_hint()에 대한 기능은 21행과 22행에 있는데,

솔직히 속도에 차이는 얼마나지 않습니다.

 

하지만 분명한것은 emplace_hint()에 들어가는 위치에 따라 삽입의 속도는 차이가 있음이 분명합니다.

(https://en.cppreference.com/w/cpp/container/set/emplace_hint 를 참조하시길 바랍니다.)

 

 

 

 

 

 

Set의 기능(operations)

s.find()	찾는 값이 있으면 해당 위치의 iterator 반환, 아니면 s.end()반환
s.count()	set에 저장된 요소들의 갯수 반환
s.lower_bound()	set의 요소의 위치에 대한 iterator 반환
s.upper_bound()	set의 요소의 위치에 대한 iterator 반환
s.equal_range()	해당 요소에 대한 범위(iterator) 반환

 

#include <set>
#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {

    set<int> s = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    pair<set<int>::iterator, set<int>::iterator> itr = s.equal_range(4);

    cout <<*itr.first << " " << *itr.second << endl;    //output : 4, 5



    set<int>::iterator low_itr, up_itr;

    low_itr = s.lower_bound(3);
    up_itr = s.upper_bound(7);

    s.erase(low_itr, up_itr);

    for_each(s.begin(), s.end(), [](int n) {
        cout << n << endl;        //output : 1, 2, 8, 9, 10
        });

    return 0;
}​

 

 

 

lower_bound()와 upper_bound()는 set에 있는 요소를 삭제할 때 좋습니다.

 

s.erase(s.begin(), s.find(7)); 로 할 경우 1, 2, 7, 8, 9, 10 이 되므로 7은 유지되지만

s.erase(low_itr, up_itr);로 할 경우 1, 2, 8, 9, 10이 됩니다.

 

때문에 가독성이나 결과값 예측에도 lower, upper가 좋습니다.