[C++] STL set

C++ STL의 set은 중복되지 않는 원소들을 정렬된 상태로 저장하는 자료구조이다.

주요 특징

• 중복된 원소는 저장되지 않는다. 예를 들어, 같은 값을 두 번 넣으려고 하면 두 번째 삽입은 무시된다.
• 원소들은 자동으로 오름차순 정렬된다. (기본 비교 함수: std::less)
• 내부는 Red-Black Tree로 구현되어 있다.
• 삽입, 삭제, 탐색 모두 평균 O(logn)
• 인덱스 접근이 불가능하며 반복자(iterator)로만 접근 가능

주요 멤버 함수

함수명	설명
insert(val)	val 삽입 (중복일 경우 무시)
erase(val)	val 삭제
find(val)	val의 iterator 반환 (없으면 end() 반환)
count(val)	val의 존재 여부 반환 (0 또는 1)
size()	원소 개수 반환
empty()	집합이 비어 있는지 확인
clear()	모든 원소 제거

사용 예시

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;

    s.insert(5);
    s.insert(2);
    s.insert(3);
    s.insert(2); // 중복되므로 무시됨
    s.insert(1);

    for (int v : s) {
        cout << v << " ";
    }

    cout << endl;

    if (s.find(1) != s.end()) {
        cout << "1 존재" << endl;
    }

    if (s.find(4) == s.end()) {
        cout << "4 존재하지 않음";
    }

    return 0;
}

🔽 출력 :

1 2 3 5
1 존재
4 존재하지 않음

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<string> s;

    s.insert("apple");
    s.insert("banana");
    s.insert("cherry");
    s.insert("mango");

    s.erase("banana"); // 원소 삭제

    for (auto it = s.begin(); it != s.end(); it++) {
        cout << *it << " ";
    }

    return 0;
}

🔽 출력 :

apple cherry mango

set<int, greater<int>> s; 와 같이 선언하여 원소들을 내림차순으로 정렬하도록 할 수도 있다.

또는 정렬 규칙을 따로 정의하여 원하는 정렬 기준을 부여할 수도 있다.

정리

set은 중복을 제외해야 하거나 정렬이 필요할 때 사용하면 좋다. 다만 임의 접근(random access)이 불가능하고, O(logn)이라 해시 기반 unordered_set보다 느릴 수 있다.

multiset

한편, <set> 헤더 파일에는 set 이외에 multiset이라는 컨테이너도 포함되어 있다. set과 매우 유사하지만 동일한 값을 여러 개 저장할 수 있다는 점이 다르다.

주요 특징

• set과 달리 동일한 값을 여러 개 저장할 수 있다. 즉, 중복을 허용한다.
• 원소들은 자동으로 오름차순 정렬된다. (기본 비교 함수: std::less)
• 내부는 Red-Black Tree로 구현되어 있다.
• 삽입, 삭제, 탐색 모두 평균 O(logn)
• 인덱스 접근이 불가능하며 반복자(iterator)로만 접근 가능

주요 멤버 함수

함수명	설명
insert(val)	val 삽입
erase(val)	모든 val 삭제
erase(ms.find(val))	val 1개만 삭제
find(val)	val의 첫 iterator 반환 (없으면 end() 반환)
count(val)	val의 개수 반환
lower_bound(val)	val 이상인 첫 원소의 iterator 반환
upper_bound(val)	val 초과인 첫 원소의 iterator 반환

참고로, lower_bound(val)은 val이 처음 나타나는 위치, upper_bound(val)은 val보다 큰 값이 처음 나타나는 위치이다.

사용 예시

#include <iostream>
#include <set>
using namespace std;

int main() {
    multiset<int> ms;

    ms.insert(1);
    ms.insert(3);
    ms.insert(5);
    ms.insert(5); // 중복 허용

    for (int v : ms) {
        cout << v << " ";
    }

    return 0;
}

🔽 출력 :

1 3 5 5

#include <iostream>
#include <set>
using namespace std;

int main() {
    multiset<int> ms = {1, 2, 2, 3, 3, 3};

    // 값이 3인 원소 하나만 삭제
    auto it = ms.find(3);
    if (it != ms.end()) {
        ms.erase(it);
    }

    for (int v : ms) {
        cout << v << " ";
    }

    cout << "\n3 개수: " << ms.count(3);

    return 0;
}

🔽 출력 :

1 2 2 3 3
3 개수: 2

사용 팁

multiset은 값의 개수를 쉽게 셀 수 있기 때문에, 빈도 기반 문제에서 유용하다. 다만 단순 빈도 관리만 한다면 unordered_map이 더 빠를 수 있다.