Set

정의

정렬된 고유한 요소들의 집합을 저장하는 STL(Standard Template Library) 컨테이너

• 레드-블랙 트리(Red-Black Tree)를 기반으로 정렬된 균형 이진 탐색 트리(BST)
• 기본적으로 오름차순(작은 값 → 큰 값)으로 정렬이 유지되고 중복된 값을 허용하지 않음

시간복잡도

• 삽입(insert), 삭제(erase), 탐색(find)의 시간 복잡도는 O(log N)

템플릿 정의

template <typename T, typename Compare = std::less<T>, typename Allocator = std::allocator<T>>
class set;

• T: 데이터 타입 (int, struct 등)
• Compare: 정렬 기준 (기본 값: std::less<T>)
• Allocator: 메모리 할당 (기본 값: std::allocator<T>)
  • Heap 메모리를 사용하여 node 기반 동적 할당을 수행

사용 방법

오름차순 정렬 (기본)

#include <iostream>
#include <set>

int main() {
  std::set<int> s;

  s.insert(3);
  s.insert(1);
  s.insert(2);

  for (auto i : s) {
    std::cout << i << " ";
  }
  return 0;
}

기본적으로 std::set은 오름차순(작은 값 → 큰 값)으로 정렬됨

1 2 3

내림차순 정렬

std::set 선언할 때 std::greater<> 추가가

#include <iostream>
#include <set>

int main() {
  std::set<int, std::greater<int>> s;

  s.insert(3);
  s.insert(1);
  s.insert(2);

  for (auto i : s) {
    std::cout << i << " ";
  }
  return 0;
}

내림차순(큰 값 → 작은 값)으로 정렬됨

3 2 1

사용자 정의 구조체 적용

특정 기준으로 정렬하고 싶다면, operator를 오버로딩하거나 compare 함수를 지정

operator 오버로딩

#include <iostream>
#include <set>

struct Task {
    int score;
    std::string name;

    // score 낮은 순으로 정렬
    bool operator<(const Task& other) const {
        return score < other.score; 
    }
};

int main() {
    std::set<Task> s;

    s.insert({1, "Low"});
    s.insert({3, "High"});
    s.insert({2, "Medium"});

    for (auto v : s) {
      std::cout << v.name << " ";
    }
    return 0;
}

score 기준 오름차순으로 정렬됨

Low Medium High

compare 함수 이용

#include <iostream>
#include <set>

struct Task {
    int priority;
    std::string name;
};

// priority 숫자 높은순으로 정렬
struct Compare {
    bool operator()(const Task& a, const Task& b) const {
        return a.priority > b.priority;
    }
};

int main() {
    std::set<Task, Compare> s; // compare 함수

    s.insert({ 1, "Low" });
    s.insert({ 3, "High" });
    s.insert({ 2, "Medium" });

    for (auto v : s) {
        std::cout << v.name << " ";
    }
    return 0;
}

priority 기준 내림차순으로 정리됨

High Medium Low