실행 가능한 C++ 문서: set

Q: C++에서 set이란 무엇인가요?

std::set은 고유한 값을 정렬된 순서로 저장하는 연관 컨테이너입니다. 이미 존재하는 값을 삽입하면 아무 일도 일어나지 않으며, 순회는 요소를 작은 값에서 큰 값 순으로 훑습니다. 내부가 균형 이진 탐색 트리로 구현되어 있어 조회·삽입·삭제가 모두 O(log n)입니다.

Q: C++ set에 요소가 있는지 어떻게 확인하나요?

x가 있으면 1, 없으면 0을 반환하는 s.count(x)를 사용하거나, C++20에서는 bool을 반환하는 s.contains(x)를 사용하세요. 이터레이터가 정말로 필요한 경우가 아니라면 s.find(x) != s.end()는 피하세요. 비용은 같지만 더 장황합니다.

Q: C++에서 set과 unordered_set의 차이는 무엇인가요?

std::set은 요소를 정렬된 상태로 유지하며 O(log n) 연산을 제공합니다. std::unorderedset은 해시 테이블을 사용해 특정 순서 없이 유지하며 평균 O(1) 연산을 제공합니다. 정렬된 순회나 범위 질의가 필요할 때는 set을, 빠른 멤버십 검사만 필요하고 순서는 상관없을 때는 unorderedset을 사용하세요.

고유하고 정렬된 값들의 모음

unordered_map이 해시 기반의 빠른 조회로 키-값 쌍을 저장하는 것을 보았습니다. std::set은 그보다 단순한 사촌으로, 오직 값만 저장하며(연관된 데이터는 없습니다) 두 가지 규칙을 자동으로 강제합니다. 모든 요소는 고유하고(중복은 조용히 버려집니다), 요소는 항상 정렬된 순서로 유지됩니다.

그래서 set은 "이걸 전에 본 적이 있나?"나 "서로 다른 항목을 정렬된 순서로 줘" 같은 질문에 자연스러운 선택입니다. 중복을 걱정하지 않고 삽입할 수 있고, 먼저 정렬하지 않아도 순회할 수 있습니다.

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

int main() {
    set<int> s;
    s.insert(40);
    s.insert(10);
    s.insert(30);
    s.insert(10);   // 중복 - 무시됨

    for (int x : s) cout << x << " ";   // 10 30 40 (정렬됨, 반복 없음)
}

10을 두 번, 게다가 순서 없이 삽입했는데도 출력은 정렬되어 있고 10은 한 번만 나타나는 것에 주목하세요. set이 여러분을 대신해 정리해 준 것입니다.

삽입과 삭제

insert는 값이 아직 없을 때 그것을 추가합니다. .second가 bool인 pair를 반환하는데, 이는 삽입이 실제로 일어났는지 알려줍니다. 값이 새로운 것이었는지 알고 싶을 때 유용합니다.

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

int main() {
    set<string> seen;

    for (string word : {"go", "rust", "go", "cpp"}) {
        auto [it, inserted] = seen.insert(word);
        if (inserted)
            cout << "First time seeing: " << word << "\n";
        else
            cout << "Already saw: " << word << "\n";
    }
}

값을 삭제하려면 값 자체를 넘겨 erase를 호출하세요. 삭제된 요소의 개수(set의 경우 0 또는 1)를 반환합니다. 없는 것을 삭제하는 것은 무해하며 오류가 아닙니다.

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

int main() {
    set<int> s = {1, 2, 3, 4};

    s.erase(3);          // 3을 삭제한다
    s.erase(99);         // 아무것도 하지 않고 0을 반환한다

    for (int x : s) cout << x << " ";   // 1 2 4
}

멤버십 확인

set의 핵심 목적은 "이게 여기 있나?"라는 빠른 검사입니다. 가장 명확한 방법은 1 또는 0을 반환하는 count입니다.

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

int main() {
    set<int> primes = {2, 3, 5, 7, 11};

    if (primes.count(7))
        cout << "7 is prime\n";

    if (!primes.count(9))
        cout << "9 is not in the set\n";
}

C++20부터는 bool을 직접 반환하는, 더욱 읽기 쉬운 선택지인 contains가 있습니다.

if (primes.contains(7)) { /* ... */ }   // C++20

흔한 실수는 map에서 하듯 operator[]에 손을 뻗는 것입니다. set에는 operator[]가 없습니다. 가져올 값이 없고, 존재 여부만 확인할 수 있기 때문입니다. s[7]이 아니라 count나 contains를 사용하세요.

실제 위치가 필요하다면(삭제하거나 이웃 요소를 살펴보기 위해) 이터레이터 또는 end()를 반환하는 find를 사용하세요.

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

int main() {
    set<int> s = {10, 20, 30};

    auto it = s.find(20);
    if (it != s.end()) {
        cout << "found " << *it << "\n";
        s.erase(it);   // 이터레이터로 삭제 - 두 번째 조회 불필요
    }
    cout << "size now " << s.size() << "\n";
}

정렬된 순회와 범위 질의

set은 정렬되어 있으므로 순회는 항상 요소를 작은 값에서 큰 값 순으로 내놓으며, 정렬된 컨테이너만의 기법을 공짜로 얻습니다. lower_bound(x)는 x보다 작지 않은 첫 요소를, upper_bound(x)는 x보다 엄격히 큰 첫 요소를 줍니다. 둘을 함께 쓰면 모든 요소를 확인하지 않고도 숫자 범위를 훑을 수 있습니다.

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

int main() {
    set<int> s = {5, 12, 18, 23, 31, 47};

    // [12, 31] 범위에 있는 모든 것을 출력한다
    auto begin = s.lower_bound(12);
    auto end = s.upper_bound(31);
    for (auto it = begin; it != end; ++it)
        cout << *it << " ";   // 12 18 23 31
}

미묘하지만 중요한 규칙이 있습니다. set 요소는 변경할 수 없습니다. 이터레이터는 const 참조를 건네주므로 요소를 제자리에서 바꿀 수 없습니다. 그렇게 하면 컨테이너가 의존하는 정렬 순서가 깨질 수 있기 때문입니다. 값을 "바꾸려면" 기존 값을 삭제하고 새 값을 삽입하세요.

기본 순서는 오름차순(std::less)입니다. 내림차순으로 하려면 두 번째 템플릿 인자로 다른 비교자를 제공하세요.

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

int main() {
    set<int, greater<int>> s = {5, 12, 18, 23};

    for (int x : s) cout << x << " ";   // 23 18 12 5
}

set vs multiset vs unordered_set

std::set은 가까운 친척 셋 중 하나이며, 알맞은 것을 고르는 일이 중요합니다.

set<int>            // 고유한 값, 정렬됨, O(log n)
multiset<int>       // 중복 허용, 정렬됨, O(log n)
unordered_set<int>  // 고유한 값, 순서 없음, 평균 O(1)

멤버십 검사만 필요하고 순서는 상관없다면 unordered_set을 택하세요. 해시 기반 조회는 평균적으로 set의 트리 기반 O(log n)보다 빠릅니다. 요소가 정렬된 순서로 필요하거나, lower_bound/upper_bound로 범위 질의를 하거나, 안정적인 이터레이터 동작이 필요할 때는 set을 고르세요. multiset은 중복이 의미가 있을 때만(예: 반복 값의 히스토그램) 사용하세요. multiset에서는 count(x)가 1보다 큰 값을 반환할 수 있고, erase(x)는 단일 이터레이터로 삭제하지 않는 한 모든 사본을 제거합니다.

set의 고전적인 활용 하나는 vector의 중복 제거와 정렬을 한 번에 처리하는 것입니다.

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

int main() {
    vector<int> data = {4, 1, 4, 2, 1, 3};
    set<int> unique(data.begin(), data.end());

    for (int x : unique) cout << x << " ";   // 1 2 3 4
}

vector의 이터레이터로 set을 생성하면 모든 중복이 버려지고 나머지가 정렬됩니다. 수동 루프도, std::sort에 std::unique를 더하는 번거로운 절차도 필요 없습니다.

다음: pair와 tuple

이제 insert가 반환하는 pair에 .first와 .second가 나타나고, 구조적 바인딩(auto [it, inserted])이 그것을 깔끔하게 푸는 것을 보았습니다. "몇 개의 값을 한데 묶는" 이런 가벼운 타입들은 STL 곳곳에 있습니다. 다음에는 pair와 tuple을 직접 살펴보며, 어떻게 만들고, 풀고, 구조체를 통째로 정의하지 않고도 함수에서 여러 값을 반환하는지 알아봅니다.

자주 묻는 질문

C++에서 set이란 무엇인가요?

std::set은 고유한 값을 정렬된 순서로 저장하는 연관 컨테이너입니다. 이미 존재하는 값을 삽입하면 아무 일도 일어나지 않으며, 순회는 요소를 작은 값에서 큰 값 순으로 훑습니다. 내부가 균형 이진 탐색 트리로 구현되어 있어 조회·삽입·삭제가 모두 O(log n)입니다.

C++ set에 요소가 있는지 어떻게 확인하나요?

x가 있으면 1, 없으면 0을 반환하는 s.count(x)를 사용하거나, C++20에서는 bool을 반환하는 s.contains(x)를 사용하세요. 이터레이터가 정말로 필요한 경우가 아니라면 s.find(x) != s.end()는 피하세요. 비용은 같지만 더 장황합니다.

C++에서 set과 unordered_set의 차이는 무엇인가요?

std::set은 요소를 정렬된 상태로 유지하며 O(log n) 연산을 제공합니다. std::unordered_set은 해시 테이블을 사용해 특정 순서 없이 유지하며 평균 O(1) 연산을 제공합니다. 정렬된 순회나 범위 질의가 필요할 때는 set을, 빠른 멤버십 검사만 필요하고 순서는 상관없을 때는 unordered_set을 사용하세요.