[Set, Map / Hash] std::set

 

 

 

1. Set이란?

이 글에서는 C++ STL에서 자주 사용하는 std::set에 대해 알아보겠습니다.

Set은 쉽게 말해 데이터를 저장하는 집합(Container)이라고 생각하시면 됩니다.

가장 큰 특징은 다음과 같습니다.

• 중복을 허용하지 않습니다.
• 항상 정렬된 상태를 유지합니다.

 

 

2. std::set

std::set은 <set> 헤더에 정의되어 있으며,

유일한(Unique) 객체들을 정렬된 상태로 저장하는 컨테이너

입니다.

원소의 정렬은 비교 연산자(Compare)를 통해 이루어집니다.

또한

• 탐색(Search)
• 삽입(Insert)
• 삭제(Erase)

모두 O(log N)의 시간 복잡도를 가집니다.

 

 

 

3. 내부 구현

일반적으로 std::set이 Red-Black Tree를 기반으로 구현된다고 합니다.

다만 실제 구현은 STL 라이브러리마다 조금씩 다를 수 있습니다.

이번 강의에서는 이해를 돕기 위해 균형 이진 탐색 트리(Balanced Binary Search Tree)를 기준으로 설명하겠습니다.

 

 

4. Binary Search Tree

Binary Search Tree(BST)는 다음과 같은 규칙을 가집니다.

• 부모 노드보다 작은 값은 왼쪽 자식
• 부모 노드보다 큰 값은 오른쪽 자식

예를 들어

1 2 3 4 5

를 삽입하면 하나의 Binary Search Tree가 만들어집니다.

예를 들어 가운데 값인 3을 루트로 생각하면

        3
      /   \
     2     5
    /     /
   1     4

와 같이 표현할 수 있습니다.

이 구조에서는

• 3의 왼쪽에는 3보다 작은 값만 존재하고,
• 3의 오른쪽에는 3보다 큰 값만 존재합니다.

마찬가지로

• 5의 왼쪽에는 4만 존재하며,
• 4 역시 5보다 작은 값입니다.

즉, 모든 노드가 이러한 규칙을 만족하도록 구성됩니다.

 

 

 

5. 시간 복잡도

std::set의 탐색은 루트부터 시작합니다.

찾고자 하는 값이 현재 노드보다

• 작으면 왼쪽으로,
• 크면 오른쪽으로

이동하는 과정을 반복합니다.

즉, 이진 탐색(Binary Search)과 유사한 방식으로 탐색하기 때문에

• find()
• insert()
• erase()

모두 O(log N)의 시간 복잡도를 가집니다.

삽입이나 삭제 이후에는 트리의 균형을 유지하기 위한 재구성(Rebalancing)이 수행되므로 역시 O(log N)이 필요합니다.

 

 

6. Set의 가장 큰 특징 - 중복 제거

Set은 중복 데이터를 허용하지 않습니다.

예를 들어

set.insert(1);
set.insert(2);
set.insert(3);
set.insert(3);
set.insert(3);
set.insert(4);

를 수행하면

1 2 3 4

만 저장됩니다.

이미 존재하는 값은 새로 삽입되지 않습니다.

반면

set.insert(6);

을 수행하면

1 2 3 4 6

이 됩니다.

새로운 값은 적절한 위치에 삽입되며 트리 역시 자동으로 재구성됩니다.

 

 

7. 자동 정렬

Set의 또 다른 중요한 특징은 항상 정렬된 상태를 유지한다는 것입니다.

예를 들어

100
-1
30
4000
5
-500

처럼 아무 순서로나 삽입해도

출력하면

-500
-1
5
30
100
4000

처럼 항상 오름차순으로 정렬되어 있습니다.

이는 내부적으로 Balanced Binary Search Tree가 계속 균형을 유지하며 정렬 상태를 관리하기 때문입니다.

 

 

8. MultiSet

Set와 매우 비슷하지만

중복을 허용하는 컨테이너도 있습니다.

바로 std::multiset입니다.

multiset은

• 내부적으로 트리 구조를 사용하며
• 같은 값을 여러 개 저장할 수 있습니다.

다음에는 multiset을 조금 더 자세히 살펴보겠습니다.

 

 

9. Unordered Set

Set와 비슷하지만

정렬 기능이 없는 컨테이너도 있습니다.

바로 std::unordered_set입니다.

unordered_set은

• Binary Search Tree가 아니라
• Hash Table을 사용합니다.

따라서 정렬은 지원하지 않지만 평균적으로 O(1)의 탐색 성능을 제공합니다.

Hash Table에 대해서는 다음 챕터에서 자세히 알아보겠습니다.

 

 

10. 다음 글

• 사용자 정의 타입에서 비교 연산자(Comparison Operator)를 구현하는 방법
• std::set을 사용하는 방법
• std::multiset의 활용

에 대해 예제와 함께 알아보겠습니다.

 

 

참고 자료

이 글에서는 Red-Black Tree의 세부 구현까지는 다루지 않았습니다.

만약

• Red-Black Tree
• Balanced Binary Search Tree

가 아직 익숙하지 않다면, YouTube에서 관련 애니메이션 영상을 찾아보시는 것을 추천드립니다.

동작 과정을 시각적으로 보면 트리의 균형 유지와 탐색 원리를 훨씬 쉽게 이해할 수 있습니다.