포스트

set

C++ STL의 set에 대해서 정리했습니다.

게시 업데이트
Preview Image
By 김종민
13 분읽는 시간
set

set은 연관 컨테이너 중에서 가장 단순한 컨테이너다.

모든 연관 컨테이너는 노드 기반 컨테이너며, 균형 이진 트리를 사용한다.
모든 연관 컨테이너는 또한 양방향 반복자를 지원한다.


인터페이스

모든 연관 컨테이너는 같은 인터페이스를 제공한다.
연관 컨테이너에서 집중해야 할 인터페이스는 탐색 연산이다.


생성자

set의 생성자는 다음과 같다.

1
2
3
4
5

set();              // 정렬 기준이 less<>인 빈 set을 생성한다.
set(pred);          // 정렬 기준이 pred인 빈 set을 생성한다.
set(s1);            // s1으로부터 set을 복사 생성한다.
set(b, e);          // 순차열 구간 [b, e)를 정렬 기준 less<>로 생성한다.
set(b, e, pred);    // 순차열 구간 [b, e)를 정렬 기준 pred로 생성한다.


원소의 삽입

set과 같은 연관 컨테이너는 시퀀스 컨테이너와 달리 삽입된 원소의 순서에 영향을 받지 않는다.
내부적으로 연관 컨테이너의 정렬 기준에 의해 자동 정렬된다.

따라서 시퀀스 컨테이너의 push_back(), pop_back(), push_front(), pop_front(), front(), back() 등의 인터페이스들은 지원하지 않는다.

연관 컨테이너들은 오직 insert()만을 지원한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
#include <set>

using namespace std;

int main(void)
{
    // 기존 조건자는 less<>이므로, 오름차순 정렬된다.
    set<int> s;

    s.insert(10);
    s.insert(30);
    s.insert(40);
    s.insert(50);
    s.insert(20);

    // 반복자는 set을 순회하는 방법으로 중위 순회를 택한다.
    for(set<int>::iterator iter = s.begin(); iter != s.end(); iter++)
        cout << *iter << ' ';
    cout << endl;
}

set의 특징은 중복된 원소를 허용하지 않는다는 점이다.
중복된 원소가 삽입되는 과정에서 자연스럽게 무시된다.

그래서 insert()의 반환 값으로는 삽입한 원소의 set::iterator와 성공 여부의 bool의 쌍인 std::pair<set::iterator, bool>을 반환한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <iostream>
#include <set>

using namespace std;

int main(void)
{
    set<int> s;

    s.insert(30);

    // 삽입된 원소 30을 가리키는 반복자, 성공 여부를 반환한다.
    pair<set<int>::iterator, bool> pr = s.insert(30);
    if(pr.second)
        cout << *pr.first << "를 set에 삽입하는 데 성공했습니다." << endl;
    else
        cout << "삽입 과정에서 중복 원소를 발견했습니다." << endl;
}

또한 임의 위치부터 탐색하여 삽입하거나 순차열 구간을 이용하여 삽입하는 오버라이딩된 insert()도 지원한다.

1
2

insert(p, k);   // 반복자 p가 가리키는 위치부터 탐색하여 k를 삽입한다.
insert(b, e);   // set에 [b, e] 순차열 구간을 삽입한다.

예시를 보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>
#include <set>

using namespace std;

int main(void)
{
    set<int> s1;
    s1.insert(10);
    s1.insert(20);
    s1.insert(30);
    s1.insert(40);
    pair<set<int>::iterator, bool> pr = s1.insert(50);

    set<int> s2;
    s2.insert(35);
    s2.insert(45);

    // 50의 위치부터 탐색하여 55를 삽입한다.
    s1.insert(pr.first, 55);

    // 10 20 30 40 50 55가 출력된다.
    for(set<int>::iterator iter = s1.begin(); iter != s1.end(); iter++)
        cout << *iter << ' ';
    cout << endl;

    // s2의 [b, e) 구간을 s1에 삽입한다.
    s1.insert(s2.begin(), s2.end());

    // 10 20 30 35 40 45 50 55가 출력된다.
    for(set<int>::iterator iter = s1.begin(); iter != s1.end(); iter++)
        cout << *iter << ' ';
    cout << endl;
}


정렬 조건자 지정과 확인

set의 생성자를 살펴보면 커스텀 조건자를 지정하는 생성자가 존재한다.
실제로 커스텀 조건자를 지정하면 그 조건자의 정렬 방식에 따라 원소가 정렬된다.

커스텀 조건자는 함수 객체를 이용한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
#include <set>

using namespace std;

int main(void)
{
    // 내림차순 정렬 기준을 가지는 set을 설정한다.
    set<int, greater<int>> lset;

    lset.insert(10);
    lset.insert(20);
    lset.insert(30);
    lset.insert(40);
    lset.insert(50);

    // 50 40 30 20 10이 출력된다.
    for(set<int, greater<int>>::iterator iter = lset.begin(); iter != lset.end(); iter++)
        cout << *iter << ' ';
    cout << endl;
}

모든 연관 컨테이너에는 Key의 정렬 조건과 Value의 정렬 조건을 확인할 수 있는 인터페이스가 존재한다.
key_comp()와 value_comp()가 그 역할을 맡는다.

또한 set에서는 key_compare과 value_compare이 typedef로 정의되어 있다.

사실 set에서는 key와 value가 동일하기 때문에 둘의 차이가 무의미하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
#include <set>

using namespace std;

int main(void)
{
    set<int, less<int>> lset;
    set<int, greater<int>> gset;

    lset.insert(50);
    lset.insert(40);
    lset.insert(90);

    gset.insert(50);
    gset.insert(40);
    gset.insert(90);

    set<int, less<int>>::key_compare lcmp = lset.key_comp();
    // 10 < 20의 연산 결과를 출력한다.
    cout << lcmp(10, 20) << endl;

    set<int, greater<int>>::key_compare gcmp = gset.key_comp();
    // 10 > 20의 연산 결과를 출력한다.
    cout << gcmp(10, 20) << endl;


    cout << "key_compare (less): " << typeid(lcmp).name() << endl;
    cout << "key_compare (greater): " << typeid(gcmp).name() << endl;
    cout << "value_compare (less): " << typeid(lset.value_comp()).name() << endl;
    cout << "value_compare (greater): " << typeid(gset.value_comp()).name() << endl;
}


clear() 및 empty()

시퀀스 컨테이너와 마찬가지로 연관 컨테이너도 clear()와 empty()를 지원한다.
clear()는 전체 원소를 삭제하며, empty()는 컨테이너가 비어있는지를 bool로 반환한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
#include <set>

using namespace std;

int main(void)
{
    set<int> s;

    s.insert(10);
    s.insert(20);
    s.insert(30);

    // 3이 출력된다.
    cout << s.size() << endl;

    // 컨테이너의 모든 원소를 삭제한다. 
    s.clear();
    cout << s.size() << endl;

    if(s.empty())
        cout << "컨테이너가 모두 비었습니다." << endl;
}


count()와 find()를 이용한 탐색

연관 컨테이너에서 가장 중요한 연산은 탐색이다.
균형 이진 트리를 기반으로 구현되어 O(log n)의 시간 복잡도를 보인다.

count()는 컨테이너에 포함된 특정 원소의 개수를 반환한다.
중복을 허용하지 않는 set에서는 잘 사용되지 않는다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <iostream>
#include <set>

using namespace std;

int main(void)
{
    set<int> s;

    s.insert(10);
    s.insert(20);
    s.insert(30);
    s.insert(40);

    cout << s.count(30) << endl;

    if(s.count(55) <= 0)
        cout << "55가 set 내부에 존재하지 않습니다." << endl;
}

find()는 특정 원소를 탐색하며 특정 원소를 가리키는 반복자를 반환한다.
만약 원소가 존재하지 않는다면 end()를 반환한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
#include <set>

using namespace std;

int main(void)
{
    set<int> s;

    s.insert(10);
    s.insert(20);
    s.insert(30);
    s.insert(40);

    set<int>::iterator iter = s.find(30);
    cout << *iter << endl;

    iter = s.find(50);
    if(iter != s.end())
        cout << "50이 set 내부에 존재합니다." << endl;
    else
        cout << "50이 set 내부에 존재하지 않습니다." << endl;
}


탐색의 내부 원리

시퀀스 컨테이너와 달리 연관 컨테이너의 탐색은 ==를 사용하지 않는다.
컨테이너의 내부 정렬 조건자를 이용하여 원소를 비교한다.

아래는 less<> 조건자를 예시로 든 경우다. less<>이므로 <로 비교한다.

1
2

// a가 b보다 크지도 작지도 않다면 같다고 취급한다.
!(a < b) && !(b < a)

1
2
3
4
5
6
7
8
9
10
11
12
13

#include <iostream>
#include <set>

using namespace std;

int main(void)
{
    set<int> s;
    set<int>::value_compare vcmp = s.value_comp();

    cout << (!vcmp(10, 20) && !vcmp(20, 10)) << endl;
    cout << (!vcmp(30, 30) && !vcmp(30, 30)) << endl;
}


중복 원소의 순차열 반환

연관 컨테이너는 중복 원소들의 순차열을 알아낼 수 있는 인터페이스를 제공한다.

lower_bound()는 중복 원소 순차열의 시작 위치 반복자를 반환한다.
upper_bound()는 중복 원ㅅ 순차열의 끝 위치 + 1 반복자를 반환한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <iostream>
#include <set>

using namespace std;

int main(void)
{
    set<int> s;

    s.insert(10);
    s.insert(20);
    s.insert(30);
    s.insert(40);
    s.insert(50);

    set<int>::iter lower_iter = s.lower_bound(30);
    set<int>::iter upper_iter = s.upper_bound(30);

    cout << *lower_iter << endl;
    cout << *upper_iter << endl;

    lower_iter = s.lower_bound(60);
    upper_iter = s.upper_bound(60);

    if(lower_iter == upper_iter)
        cout << "set에 내부에 60은 존재하지 않습니다." << endl;
    else
        cout << "set에 내부에서 60을 발견했습니다." << endl;
}

equal_range()는 lower_bound()와 upper_bound()를 결합한 형태로 중복 원소의 순차열 반복자 쌍을 반환한다.

위의 예제를 equal_range()로 변경해보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>
#include <set>

using namespace std;

int main(void)
{
    set<int> s;

    s.insert(10);
    s.insert(20);
    s.insert(30);
    s.insert(40);
    s.insert(50);

    pair<set<int>::iterator, set<int>::iterator> pr = s.equal_range(30);

    cout << *pr.first << endl;
    cout << *pr.second << endl;

    pr = s.equal_range(60);

    if(pr.first == pr.second)
        cout << "set에 내부에 60은 존재하지 않습니다." << endl;
    else
        cout << "set에 내부에서 60을 발견했습니다." << endl;
}


정리

  • 모든 연관 컨테이너는 모두 같은 인터페이스를 사용한다.
  • 모든 연관 컨테이너는 양방향 반복자를 지원한다.
  • 모든 연관 컨테이너는 균형 이진 트리를 기반으로 만들어졌다.
  • 균형 이진 트리의 특징으로 삽입, 삭제, 탐색 연산은 O(log n)의 시간 복잡도를 보인다.
  • set은 연관 컨테이너이자, 노드 기반 컨테이너다.
  • set은 중복된 원소의 삽입을 허용하지 않는다.
C++, STL
C++ STL
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.