pkglog
EN

C++ set vs unordered_set: 성능 비교, 커스텀 비교자·해시, 교집합·합집합, 반복자 무효화

작성 · · 22분 읽기 · 수정 초급 튜토리얼

이 글의 핵심

요소를 넣고 찾기만 하는데도 set과 unordered_set 중 무엇을 쓰느냐에 따라 성능과 순회 순서가 크게 달라집니다. 이 글은 트리와 해시 테이블의 차이에서 출발해 multiset이 필요한 경우, set 요소를 직접 수정할 수 없는 이유, C++17 extract와 C++20 이질적 조회까지 실제 코드로 짚습니다.

set vs unordered_set

특성setunordered_set
정렬O (자동 정렬)X
속도O(log n)평균 O(1), 최악 O(n)
중복허용 안함허용 안함
순회정렬된 순서구현·버킷 수에 따라 달라짐

표의 “순회” 항목은 “무작위”라기보다 예측하지 말아야 하는 순서라는 뜻입니다. 같은 프로그램에서도 원소를 넣는 순서나 reserve 여부에 따라 버킷 배치가 달라지고, GCC(libstdc++)와 MSVC처럼 표준 라이브러리 구현이 바뀌면 순서도 바뀝니다. 테스트에서 unordered_set을 순회한 출력을 기대값과 문자열로 비교하면 로컬에서는 통과하다가 다른 컴파일러의 CI에서 깨지는 일이 흔합니다. 결과 순서가 의미를 갖는다면 순회 전에 정렬하거나 처음부터 set을 써야 합니다.

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을 우선 검토하세요.

두 컨테이너 모두 원소마다 노드를 따로 할당한다는 점도 선택에 영향을 줍니다. set은 노드마다 부모·왼쪽·오른쪽 포인터와 색 정보를, unordered_set은 다음 노드 포인터(구현에 따라 캐시된 해시값)를 추가로 들고 있어서, int 하나를 저장하는 데 수십 바이트가 쓰입니다. 원소를 한 번 만들고 나서 조회만 반복하는 경우라면 정렬된 std::vector + std::binary_search/lower_bound 가 메모리는 몇 배 적게 쓰고 연속 메모리 덕분에 캐시 효율도 좋아 두 컨테이너보다 빠른 경우가 많습니다. C++23의 std::flat_set이 바로 이 구조를 표준화한 것입니다. set이나 unordered_set이 확실히 유리한 것은 삽입과 삭제가 조회와 섞여 계속 일어나는 경우입니다.

multiset과 unordered_multiset

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

특성multisetunordered_multiset
순서정렬 유지(C++11부터 같은 값은 기존 범위의 끝에 삽입되어 삽입 순서 유지)순서 없음
조회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;

set은 ==를 쓰지 않고 비교자만으로 동등성을 판단합니다. !comp(a, b) && !comp(b, a)이면 두 원소를 같은 키로 보기 때문에, 위 ById를 쓰면 id가 같은 두 Person은 이름이 달라도 중복으로 취급되어 두 번째 insert가 조용히 무시됩니다. 의도한 동작일 수도 있지만, 모르고 쓰면 “데이터가 사라지는” 버그가 됩니다.

엄격 약순서를 어기는 대표적인 실수는 < 대신 <=를 쓰는 것입니다. comp(a, a)가 참이 되면 트리의 불변식이 깨져 find가 있는 원소를 못 찾거나, 삽입할 때마다 같은 값이 계속 들어갑니다. MSVC 디버그 빌드는 이것을 감지해 invalid comparator 단언 실패로 멈추고, GCC에서는 -D_GLIBCXX_DEBUG를 켜면 비슷한 검사를 받을 수 있습니다. 여러 필드를 비교할 때는 std::tie(a.x, a.y) < std::tie(b.x, b.y)를 쓰면 사전식 비교를 실수 없이 만들 수 있습니다.

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이면 기본 해시를 쓰는 것이 일반적입니다.

위 PointHash의 x ^ (y << 1)은 간단하지만 좋은 해시는 아닙니다. libstdc++와 MSVC의 std::hash<int>는 대개 값을 그대로 돌려주는 항등 함수라서, 격자 좌표처럼 작은 정수 쌍을 넣으면 (2, 1)과 (0, 0)이 모두 0이 되는 것처럼 서로 다른 점의 해시가 쉽게 겹쳐 충돌이 많아집니다. 좌표 범위가 32비트 안이라면 (uint64_t(uint32_t(p.x)) << 32) | uint32_t(p.y)처럼 두 값을 겹치지 않게 합쳐 64비트 해시로 쓰는 편이 충돌이 없고, 일반적인 조합에는 boost::hash_combine 방식처럼 곱셈과 섞기를 넣는 함수를 씁니다. 해시와 operator==는 반드시 같은 필드를 기준으로 해야 합니다. ==가 비교하는 필드 중 일부만 해시에 넣는 것은 괜찮지만(충돌이 늘 뿐), 해시에는 있고 ==에는 없는 필드가 있으면 같은 원소가 다른 버킷에 들어가 중복 저장됩니다.

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

  • 중복 제거만이고 원래 순서 유지가 필요하면 set으로 넣었다가 벡터로 옮기면 순서가 바뀝니다. 정렬 후 unique 도 정렬 단계에서 순서가 바뀌므로 순서가 상관없을 때만 씁니다. 원래 순서를 유지하려면 unordered_set<int> seen;을 두고 원소를 차례로 보면서 if (seen.insert(x).second) out.push_back(x);처럼 처음 본 값만 결과에 넣습니다. insert가 돌려주는 pair의 second가 “새로 들어갔는가”를 알려 주므로 count로 한 번 더 찾을 필요가 없습니다.
  • 교집합·합집합·차집합은 위의 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)으로 n개까지 재해시가 일어나지 않게 해 두면, 그 범위 안의 삽입은 반복자를 무효화하지 않습니다.
  • erase: 표준은 삭제된 원소의 반복자만 무효가 된다고 보장합니다. 다른 반복자는 유효하고, erase는 재해시를 일으키지 않습니다. 순회 중 삭제할 때는 지운 반복자를 다시 증가시키지 않도록 erase의 반환 반복자를 쓰는 패턴이 필요합니다.
for (auto it = s.begin(); it != s.end(); ) {
    if (조건) it = s.erase(it);  // erase는 다음 반복자 반환
    else ++it;
}

이 루프를 for (auto it = s.begin(); it != s.end(); ++it) { if (조건) s.erase(it); }로 쓰면, 지워진 노드의 반복자를 ++it로 증가시키는 미정의 동작이 됩니다. 운 좋게 동작하는 것처럼 보이다가 마지막 원소를 지우는 순간 크래시가 나는 식이라 처음 C++를 쓸 때 흔히 겪는 버그입니다. C++20부터는 std::erase_if(s, [](int x) { return x % 2 == 0; });로 이 루프 자체를 한 줄로 대신할 수 있습니다.

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;
}

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

set_intersection 같은 알고리즘은 두 입력을 한 번씩 동시에 훑는 병합 방식이라 O(n + m)에 끝나지만, 결과를 inserter로 set에 넣으면 원소마다 트리 삽입 비용이 붙습니다. 결과를 다시 집합 연산에 쓸 게 아니라면 std::vector<int> out;과 std::back_inserter(out)를 쓰는 편이 빠르고, 결과도 이미 정렬된 상태로 나옵니다. 두 집합의 크기 차이가 크다면(예: 10개와 100만 개) 작은 쪽을 순회하며 큰 쪽에서 find하는 방식이 O(m log n)으로 더 유리합니다.

예시 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) 속도로 방문 여부를 확인합니다. 노드 번호가 문자열이거나 범위가 넓고 드문드문한 그래프에서 유용한 패턴입니다.

다만 이 예제처럼 노드가 0부터 n-1까지의 정수라면 std::vector<bool> visited(n); 또는 std::vector<char>가 해시 계산도 노드 할당도 없어서 훨씬 빠르고 메모리도 적게 씁니다. 코딩 테스트에서 unordered_set으로 방문 체크를 했다가 시간 초과를 받고 배열로 바꿔 통과하는 경우가 드물지 않습니다. 해시 기반 방문 체크는 좌표 (x, y)나 상태 문자열처럼 인덱스로 바꾸기 어려운 키에 쓰는 것이 맞습니다.

자주 발생하는 문제

문제 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)
}

mutable은 정렬 기준에 쓰이지 않는 필드에만 써야 합니다. 위 Item은 id로만 정렬하므로 count를 바꿔도 트리 순서가 깨지지 않지만, 누군가 나중에 비교 연산자에 count를 추가하면 원소 값이 트리 밖에서 바뀌어 find가 실패하는 버그가 생깁니다. 이런 구조라면 std::map<int, int>(id → count)가 의도를 더 분명히 드러내는 경우가 많습니다. 키 자체를 바꿔야 한다면 아래 심화 절의 extract가 삭제·재삽입보다 효율적입니다.

문제 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
// C++20부터는 캡처 없는 람다가 기본 생성 가능해 set<Point, decltype(cmp)> points; 도 가능

C++17 이하에서 set<Point, decltype(cmp)> points;처럼 생성자에 cmp를 넘기지 않으면, 람다 타입에 기본 생성자가 없어서 use of deleted function 계열의 긴 컴파일 에러가 납니다. 비교자를 여러 곳에서 쓴다면 람다보다 방법 2의 함수 객체가 선언과 재사용 모두 간단합니다.

문제 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);  // 하나만 삭제
}

심화: reserve·rehash·부하 분포

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

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

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

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

키가 std::string일 때 find("literal")이나 find(sv)는 기본적으로 인자를 std::string으로 변환하므로 조회할 때마다 임시 문자열이 만들어집니다(짧은 문자열은 SSO로 할당이 없지만 긴 문자열은 힙 할당이 일어납니다). set은 C++14부터 비교자를 std::less<>로 두기만 하면 이 변환 없이 조회합니다. unordered_set은 C++20부터 가능한데, 해시와 동등 비교 둘 다 is_transparent를 가져야 합니다.

#include <set>
#include <string>
#include <string_view>
#include <unordered_set>

struct SVHash {
    using is_transparent = void;  // 이질적 조회 허용 표시
    std::size_t operator()(std::string_view sv) const noexcept {
        return std::hash<std::string_view>{}(sv);
    }
};

std::set<std::string, std::less<>> ordered;                       // C++14
std::unordered_set<std::string, SVHash, std::equal_to<>> hashed;  // C++20

bool has(std::string_view key) {
    return hashed.find(key) != hashed.end();  // 임시 std::string 없음
}

std::hash<std::string>과 std::hash<std::string_view>는 같은 문자열에 같은 값을 내도록 규정되어 있어서, 위처럼 string_view 해시 하나로 std::string 키와 string_view 조회를 함께 처리할 수 있습니다. 둘 중 하나라도 is_transparent가 없으면 컴파일은 되지만 조용히 임시 std::string을 만드는 쪽으로 동작하므로, 성능 목적이라면 프로파일러로 할당이 사라졌는지 확인하는 편이 좋습니다.

심화: 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));
}

extract는 노드를 컨테이너에서 떼어 내기만 하고 메모리는 해제하지 않으므로, 값을 바꾼 뒤 다시 insert해도 새 할당이 일어나지 않습니다. set의 원소는 원래 const라 수정할 수 없지만 노드 핸들의 value()는 수정 가능한 참조를 돌려주기 때문에 키를 바꾸는 유일한 합법적인 방법이기도 합니다. 같은 방식으로 a.merge(b)를 쓰면 b의 노드를 복사 없이 a로 옮길 수 있고, a에 이미 있는 키의 노드는 b에 남습니다.

unordered_set도 유사하지만 재해시 타이밍에 주의하세요. 노드를 다시 insert하는 순간 로드 팩터를 넘으면 재해시가 일어나 다른 반복자가 무효가 될 수 있습니다.

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

  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를 키로 넣고 기본 해시만 쓰기 → 해시가 비효율적이거나 정의 누락. 불변 키로 식별자를 쓰거나, 커스텀 해시를 정의합니다.
  • 순회 중 erase 후 잘못된 반복자 증가 → it = container.erase(it) 패턴 사용.
  • 멀티스레드: 쓰는 스레드가 없다면 여러 스레드가 find·count 같은 const 멤버를 동시에 호출해도 표준상 안전합니다. 하지만 한 스레드라도 insert/erase를 하면 읽기를 포함한 모든 접근을 동기화해야 합니다(읽기가 대부분이면 std::shared_mutex, 또는 갱신 시 새 컨테이너를 만들어 포인터를 교체하는 스냅샷 방식). “읽기만 하는 스레드는 괜찮겠지”라는 가정이 깨지는 지점은 대개 이 쓰기 스레드의 존재입니다.

같이 보면 좋은 글