C++ set/unordered_set | "중복 제거" 완벽 가이드

· 17분 읽기 · 수정 초급 튜토리얼
C++ set/unordered_set | "중복 제거" 완벽 가이드

이 글의 핵심

set과 unordered_set의 선택 기준, multiset·해시·반복자 규칙, 집합 연산 실무까지 다룹니다.

set vs unordered_set

특성setunordered_set
정렬O (자동 정렬)X
속도O(log n)O(1)
중복허용 안함허용 안함
순회정렬된 순서랜덤

set vs unordered_set 성능 비교

시간 복잡도(평균/분할) 관점에서 보면 set은 균형 이진 탐색 트리(일반적으로 레드-블랙) 기반이라 삽입·삭제·탐색이 O(log n) 입니다. unordered_set은 해시 테이블이라 평균 O(1) 이지만, 해시 충돌이 많으면 최악 O(n) 에 가까워질 수 있습니다.

실무에서 체감되는 차이는 다음과 같습니다.

  • 작은 n·순서가 필요: 원소 수가 수백~수천 수준이고 정렬된 순회나 lower_bound 같은 범위 탐색이 필요하면 set이 단순합니다.
  • 큰 n·키만 조회: 수백만 건 이상에서 “있는지/없는지”만 빠르게 보면 되고 순서가 중요하지 않으면 unordered_set이 유리한 경우가 많습니다.
  • 메모리: 해시 테이블은 버킷·로드 팩터 때문에 추가 오버헤드가 있을 수 있고, 트리는 노드당 포인터 오버헤드가 있습니다. n과 키 크기에 따라 달라지므로 측정이 안전합니다.
  • 캐시 지역성: 연속 메모리가 아니라 둘 다 건너뛰기 접근이 잦아 캐시 미스는 상황에 따라 큽니다. 반복 순회만으로 “항상 unordered가 빠르다”고 단정하기 어렵습니다.

선택 요약: 순서·구간 검색이 필요하면 set, 해시에 적합한 키(정수, 잘 분포된 문자열 등)이고 조회가 대부분이면 unordered_set을 우선 검토하세요.

multiset과 unordered_multiset

set / unordered_set은 동일한 키를 하나만 저장합니다. 같은 값이 여러 번 필요하면 multiset, unordered_multiset을 씁니다.

특성multisetunordered_multiset
순서정렬 유지(동일 값도 반복 삽입 순서는 구현 정의)순서 없음
조회count, equal_range로 동일 키 구간count, equal_range
삭제erase(key)는 해당 키 전부 삭제, 하나만 지우려면 반복자 사용동일
#include <set>
#include <unordered_set>
#include <iostream>

int main() {
    std::multiset<int> ms{1, 1, 2, 2, 2};
    std::cout << ms.count(2) << '\n';  // 3

    auto [first, last] = ms.equal_range(2);
    for (auto it = first; it != last; ++it) { /* ... */ }

    std::unordered_multiset<std::string> ums;
    ums.insert("a"); ums.insert("a");
    std::cout << ums.count("a") << '\n';  // 2
}

상위 k개만 필요할 때는 multiset이 정렬 상태를 유지해 최댓값/최솟값 끝단을 다루기 쉽습니다. 빈도만 세고 순서가 필요 없으면 unordered_multiset 또는 unordered_map<T, int>가 더 나을 때가 많습니다.

커스텀 비교자와 해시 함수

set: Compare와 operator<

set의 정렬 기준은 엄격 약순서(strict weak ordering) 를 만족해야 합니다. operator< 또는 std::less 커스텀 타입을 넣을 수 있습니다.

struct Person {
    std::string name;
    int id;
};

struct ById {
    bool operator()(const Person& a, const Person& b) const {
        return a.id < b.id;
    }
};

std::set<Person, ById> by_id_set;

unordered_set: Hash와 KeyEqual

unordered_set<Key, Hash, KeyEqual>에서 동일한 키에 대해 항상 같은 해시가 나와야 하고, KeyEqual은 해시 충돌 시 실제 동등성을 판별합니다. 사용자 정의 타입은 보통 다음 둘을 함께 제공합니다.

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const noexcept {
        // 간단한 결합 예시 (프로젝트에 맞게 boost::hash_combine 등 고려)
        return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 1);
    }
};

std::unordered_set<Point, PointHash> pts;

주의: 문자열을 unordered_set에 넣을 때 커스텀 해시가 나쁘면 성능이 급격히 떨어집니다. 키가 std::string이면 기본 해시를 쓰는 것이 일반적입니다.

실전: 중복 제거·교집합·합집합 정리

  • 중복 제거만이고 원래 순서 유지가 필요하면 set으로 넣었다가 벡터로 옮기면 순서가 바뀝니다. 순서 유지가 필요하면 정렬 후 unique 또는 unordered_set + 별도 순서 배열을 고려하세요.
  • 교집합·합집합·차집합은 위의 set_intersection / set_union / set_difference 패턴이 전제로 두 범위가 정렬되어 있어야 합니다. set을 쓰면 반복자가 자동으로 정렬 순서를 만족합니다.
  • unordered_set끼리 집합 연산을 라이브러리 한 방으로 하기 어렵다면, 한쪽을 vector로 모아 정렬하거나, 작은 쪽을 순회하며 다른 쪽에 count/find로 포함 여부를 확인하는 방식이 실용적입니다(크기에 따라 더 좋은 알고리즘 선택).

반복자 무효화

set / multiset

  • insert / emplace: 기존 요소의 반복자와 참조는 무효화되지 않습니다.
  • erase(it): 해당 반복자만 무효. 다른 반복자는 유지.
  • erase(key) / clear: 삭제되는 요소에 대한 반복자는 무효.

unordered_set / unordered_multiset

  • 재해시(rehash) 가 일어나면 버킷 구조가 바뀌어 모든 반복자가 무효일 수 있습니다. insert가 로드 팩터를 넘기면 재해시가 발생할 수 있으므로, 반복 중인 컨테이너에 무분별한 삽입은 위험합니다.
  • reserve(n)(또는 적절한 버킷 수 예약)으로 재해시 횟수를 줄이면 반복자 무효가 덜 자주 일어납니다.
  • erase: 삭제된 위치의 반복자만 무효, 다른 반복자는 C++11 이후 보통 유효하지만, 구현 의존적인 부분이 있으므로 삭제 시 erase의 반환 반복자를 사용하는 패턴이 안전합니다.
for (auto it = s.begin(); it != s.end(); ) {
    if (조건) it = s.erase(it);  // erase는 다음 반복자 반환
    else ++it;
}

set 기본 사용법

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

int main() {
    set<int> s;
    
    // 삽입
    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(1);  // 중복 무시
    
    // 순회 (자동 정렬: 1, 2, 3)
    for (int x : s) {
        cout << x << " ";
    }
    
    // 검색
    if (s.find(2) != s.end()) {
        cout << "\n2 존재" << endl;
    }
    
    // 삭제
    s.erase(2);
    
    // 크기
    cout << "크기: " << s.size() << endl;
    
    return 0;
}

unordered_set 기본

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

int main() {
    unordered_set<string> words;
    
    words.insert("apple");
    words.insert("banana");
    words.insert("apple");  // 중복 무시
    
    // 존재 확인 (빠름)
    if (words.count("apple") > 0) {
        cout << "apple 있음" << endl;
    }
    
    // 순회 (순서 보장 안됨)
    for (const string& word : words) {
        cout << word << " ";
    }
    
    return 0;
}

실전 예시

예시 1: 배열에서 중복 제거

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

vector<int> removeDuplicates(const vector<int>& arr) {
    set<int> s(arr.begin(), arr.end());
    return vector<int>(s.begin(), s.end());
}

int main() {
    vector<int> arr = {5, 2, 8, 2, 9, 5, 1, 8};
    
    cout << "원본: ";
    for (int x : arr) cout << x << " ";
    
    vector<int> unique = removeDuplicates(arr);
    
    cout << "\n중복 제거 (정렬됨): ";
    for (int x : unique) cout << x << " ";
    
    return 0;
}

설명: set의 자동 정렬과 중복 제거 기능을 활용한 가장 기본적인 패턴입니다.

예시 2: 두 배열의 교집합/합집합

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

int main() {
    set<int> a = {1, 2, 3, 4, 5};
    set<int> b = {3, 4, 5, 6, 7};
    
    // 교집합
    set<int> intersection;
    set_intersection(a.begin(), a.end(),
                     b.begin(), b.end(),
                     inserter(intersection, intersection.begin()));
    
    cout << "교집합: ";
    for (int x : intersection) cout << x << " ";  // 3 4 5
    
    // 합집합
    set<int> union_set;
    set_union(a.begin(), a.end(),
              b.begin(), b.end(),
              inserter(union_set, union_set.begin()));
    
    cout << "\n합집합: ";
    for (int x : union_set) cout << x << " ";  // 1 2 3 4 5 6 7
    
    // 차집합
    set<int> difference;
    set_difference(a.begin(), a.end(),
                   b.begin(), b.end(),
                   inserter(difference, difference.begin()));
    
    cout << "\n차집합 (A-B): ";
    for (int x : difference) cout << x << " ";  // 1 2
    
    return 0;
}

설명: 수학의 집합 연산을 그대로 구현할 수 있습니다. 알고리즘 문제에서 자주 사용됩니다.

예시 3: 방문 체크 (그래프 탐색)

#include <iostream>
#include <unordered_set>
#include <queue>
#include <vector>
using namespace std;

void bfs(int start, vector<vector<int>>& graph) {
    unordered_set<int> visited;
    queue<int> q;
    
    q.push(start);
    visited.insert(start);
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        cout << node << " ";
        
        for (int neighbor : graph[node]) {
            if (visited.count(neighbor) == 0) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}

int main() {
    // 그래프: 0-1, 0-2, 1-3, 2-3
    vector<vector<int>> graph = {
        {1, 2},    // 0의 인접 노드
        {0, 3},    // 1의 인접 노드
        {0, 3},    // 2의 인접 노드
        {1, 2}     // 3의 인접 노드
    };
    
    cout << "BFS 순회: ";
    bfs(0, graph);
    
    return 0;
}

설명: unordered_set을 사용하여 O(1) 속도로 방문 여부를 확인합니다. 그래프 알고리즘의 필수 패턴입니다.

자주 발생하는 문제

문제 1: set의 요소 수정 불가

증상: set의 요소를 직접 수정하려고 하면 컴파일 에러

원인: set은 정렬을 유지해야 하므로 요소가 const

해결법:

// ❌ 잘못된 코드
set<int> s = {1, 2, 3};
auto it = s.find(2);
*it = 5;  // 컴파일 에러! const int&

// ✅ 올바른 코드 (삭제 후 재삽입)
set<int> s = {1, 2, 3};
auto it = s.find(2);
if (it != s.end()) {
    s.erase(it);
    s.insert(5);
}

// ✅ 구조체의 경우 (mutable 사용)
struct Item {
    int id;
    mutable int count;  // mutable은 수정 가능
    
    bool operator<(const Item& other) const {
        return id < other.id;
    }
};

set<Item> items;
auto it = items.find(Item{1, 0});
if (it != items.end()) {
    it->count++;  // OK (mutable)
}

문제 2: 커스텀 비교 함수

증상: 커스텀 타입을 set에 넣으면 컴파일 에러

원인: operator< 또는 비교 함수 필요

해결법:

// ❌ 컴파일 에러
struct Point {
    int x, y;
};

set<Point> points;  // 에러! operator< 없음

// ✅ 방법 1: operator< 정의
struct Point {
    int x, y;
    
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

set<Point> points;  // OK

// ✅ 방법 2: 비교 함수 객체
struct PointCompare {
    bool operator()(const Point& a, const Point& b) const {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    }
};

set<Point, PointCompare> points;  // OK

// ✅ 방법 3: 람다 (C++11)
auto cmp = [](const Point& a, const Point& b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
};

set<Point, decltype(cmp)> points(cmp);  // OK

문제 3: multiset과 혼동

증상: 중복을 허용하고 싶은데 set은 안됨

원인: set은 중복 불가, multiset은 중복 가능

해결법:

// ❌ set은 중복 불가
set<int> s;
s.insert(1);
s.insert(1);
s.insert(1);
cout << s.size();  // 1 (중복 무시)

// ✅ multiset 사용
#include <set>
multiset<int> ms;
ms.insert(1);
ms.insert(1);
ms.insert(1);
cout << ms.size();  // 3 (중복 허용)

// 특정 값 개수 세기
cout << ms.count(1);  // 3

// 특정 값 모두 삭제
ms.erase(1);  // 1이 모두 삭제됨

// 하나만 삭제
auto it = ms.find(1);
if (it != ms.end()) {
    ms.erase(it);  // 하나만 삭제
}

성능 최적화

최적화 전략

  1. 효율적인 자료구조 선택

    • 적용 방법: 상황에 맞는 STL 컨테이너 사용
    • 효과: 시간복잡도 개선

  2. 불필요한 복사 방지

    • 적용 방법: 참조 전달 사용
    • 효과: 메모리 사용량 감소

  3. 컴파일러 최적화

    • 적용 방법: -O2, -O3 플래그 사용
    • 효과: 실행 속도 향상

벤치마크 결과

방법실행 시간메모리 사용량비고
기본 구현100ms10MB-
최적화 180ms8MB참조 전달
최적화 250ms5MBSTL 알고리즘

결론: 적절한 최적화로 2배 이상 성능 향상 가능

주의: 위 표의 절대 시간·메모리 수치는 예시입니다. 실제 서비스에서는 같은 입력·같은 컴파일 옵션으로 전후를 재측정하세요.

심화: reserve·rehash·부하 분포

unordered_set은 로드 팩터를 넘기면 재해시가 일어나며, 그 순간 모든 반복자가 무효될 수 있습니다. 삽입 전에 대략적인 원소 수를 알면:

std::unordered_set<int> s;
s.reserve(1'000'000); // 재해시 횟수 감소, 벤치 안정화

set은 reserve가 없지만, 불필요한 복사·임시 객체를 줄이는 편이 체감 성능에 도움이 됩니다.

심화: 이질적 조회 (C++20, unordered_set)

키가 std::string일 때 find("literal")이 임시 std::string을 만들지 않게 하려면 투명 해시·투명 동등성(std::hash<std::string_view>, std::equal_to<>)을 갖춘 커스텀 정책이 필요합니다. 표준 특수화는 구현·버전에 따라 다르니, 프로젝트의 표준 라이브러리 문서를 확인하세요.

// 개념 예: string_view로 조회 (프로젝트 정책·표준 버전 확인 필수)
// std::unordered_set<std::string, SVHash, SVEqual> 등

심화: node_type / extract (C++17)

set/unordered_set은 노드를 뽑아 다른 컨테이너로 옮길 수 있어, 재할당 없이 키를 갱신하는 패턴에 쓰입니다.

std::set<int> a{1, 2, 3};
auto nh = a.extract(2);
if (!nh.empty()) {
    nh.value() = 5;
    a.insert(std::move(nh));
}

unordered_set도 유사하지만 재해시 타이밍에 주의하세요.

심화: 벤치마크 방법 (현실적으로)

  1. 고정: 컴파일러 최적화(-O2/-O3), CPU 고정 주파수(가능하면), 동일 시드.
  2. 워밍업: 캐시·해시 테이블 워밍업 후 타이머 시작.
  3. 지표: 평균뿐 아니라 p95/p99, 특히 unordered_*는 최악 해시 입력을 별도 케이스로 넣습니다.
#include <chrono>

template<typename F>
auto bench(F&& f, int reps) {
    using clock = std::chrono::steady_clock;
    auto t0 = clock::now();
    for (int i = 0; i < reps; ++i) f();
    return clock::now() - t0;
}

심화: 디버깅 가이드

증상점검
unordered_set에서 느림해시 품질, 키 충돌, 로드 팩터, 잘못된 operator==
반복 중 이상 동작재해시로 반복자 무효 — reserve 또는 복사 후 순회
set 정렬이 이상함비교 연산이 엄격 약순서를 만족하는지

심화: 흔한 실수 패턴 (추가)

  • unordered_set에 vector를 키로 넣고 기본 해시만 쓰기 → 해시가 비효율적이거나 정의 누락. 불변 키로 식별자를 쓰거나, 커스텀 해시를 정의합니다.
  • erasewhile 순회 시 잘못된 반복자 증가 → it = container.erase(it) 패턴 사용.
  • 멀티스레드에서 const 멤버만 읽기만으로 안전하다고 가정 → unordered_set은 읽기도 동기화 필요(읽기 전용 스냅샷 또는 shared_mutex 등 설계).

FAQ

Q1: 초보자도 배울 수 있나요?

A: 네, 이 가이드는 초보자를 위해 작성되었습니다. 기본 C++ 문법만 알면 충분합니다.

Q2: 실무에서 자주 사용하나요?

A: 네, 매우 자주 사용됩니다. 실무 프로젝트에서 필수적인 개념입니다.

Q3: 다른 언어와 비교하면?

A: C++의 장점은 성능과 제어력입니다. Python보다 빠르고, Java보다 유연합니다.

Q4: 학습 시간은 얼마나 걸리나요?

A: 기본 개념은 1-2시간, 숙달까지는 1-2주 정도 걸립니다.

Q5: 추천 학습 순서는?

A:

  1. 기본 문법 익히기
  2. 간단한 예제 따라하기
  3. 실전 프로젝트 적용
  4. 고급 기법 학습

Q6: 자주 하는 실수는?

A:

  • 초기화 안 함
  • 메모리 관리 실수
  • 시간복잡도 고려 안 함
  • 예외 처리 누락

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

  • C++ string | “문자열 처리” 완벽 가이드 [실전 함수 총정리]
  • C++ Algorithm Set | “집합 알고리즘” 가이드
  • C++ STL vector | “배열보다 편한” 벡터 완벽 정리 [실전 예제]

관련 글

  • C++ map vs unordered_map (STL 시리즈) |
  • C++ map·set 완벽 가이드 | ordered vs unordered· 커스텀 키