좀비처럼

std::set / <set>

<set>은 C++의 표준 라이브러리인 STL(Standard Template Library)의 컨테이너 중 하나다. 

주요 특징은 다음과 같다. 

• 중복을 허용하지 않는 고유한 요소들로 구성됨
• 요소들이 오름차순으로 자동 정렬됨
• 이진 탐색 트리 중 하나인 Red-Black Tree(자가 균형 이진 탐색 트리)를 기반으로 함
• 삽입/검색/삭제 시 탐색 속도 O(log n)을 보장함
• 요소들이 논리적으로 연결되어 있지만 물리적으로 연결되지 않음 (연속된 메모리 블록 X)

1. Set 선언

+) std::greater<> 활용하여 내림차순으로 정렬 순서 변경 가능

#include <iostream>
#include <set>

int main() {
    std::set<int> s = {5, 2, 8, 1, 3};
    
    // 내림차순 정렬
    // std::set<int, std::greater<int>> s = {5, 2, 8, 1, 3}; → {8, 5, 3, 2, 1}

    for (int x : s) {
        std::cout << x << " "; // 1 2 3 5 8
    }
}

2. 주요 함수 및 연산

• 삽입 / insert() : 특정 요소 추가, 중복 요소 추가 불가능
• 삭제 / erase() : 특정 요소 삭제, 해당 요소 없으면 변화 없음
• 탐색 / find() : 특정 요소를 가리키는 iterator를 반환, 없으면 end()에 해당하는 iterator 반환
• 범위 삭제 / erase(a, b) : 요소 [a, b) 범위에 해당하는 모든 요소 삭제
• 크기 확인 / size() : 총 요소의 개수 반환

#include <iostream>
#include <set>

int main() {
    std::set<int> s = {5, 2, 8, 1, 3}; // → {1, 2, 3, 5, 8}

    s.insert(4);  // 4 삽입 → {1, 2, 3, 4, 5, 8}
    s.insert(2);  // 이미 존재 → 삽입되지 않음
    
    s.erase(3);  // 값 3 삭제 → {1, 2, 4, 5, 8}
    
    if (s.find(5) != s.end()) {		// 값 5 탐색
    	std::cout << "5 exists in the set.";
    } else {
    	std::cout << "5 does not exists in the set.";
    }
    
    auto it1 = s.find(2); // 값 2의 iterator
    auto it2 = s.find(5); // 값 5의 iterator
    s.erase(it1, it2); // 값 [2, 5) 범위 삭제 (2, 4 삭제)
    
    std::cout << s.size();  // 현재 원소 개수 출력 → 3

    for (int x : s) {
        std::cout << x << " "; // 1 5 8
    }
}

3. 파생 라이브러리

• <multiset> : <set>은 중복 요소를 허용하지 않지만, <multiset>은 중복을 허용함
• <unordered_set> : <set>과 달리 정렬하지 않음, Hash table을 사용하여 탐색 속도 O(1)을 보장함

#include <iostream>
#include <set>
#include <unordered_set>

int main() {
    std::multiset<int> ms = {2, 1, 2, 3, 4, 3};		// 중복 허용
    std::unordered_set<int> us = {3, 1, 2, 4};		// 정렬 X
    
    for (int x : ms) {
        std::cout << x << " ";  // 1 2 2 3 3 4
    }
    
    for (int y : us) {
        std::cout << y << " ";  // 3 1 2 4
    }
}

4. 활용 예제

추가로 <random> 라이브러리를 사용한 로또 번호 무작위 추첨

#include <iostream>
#include <random>
#include <set>

void cal() {
	std::set<int> numbers;
	std::random_device rd;
	std::mt19937 gen(rd());
	std::uniform_int_distribution<int> dis(1, 45);

	while (numbers.size() < 6) {
		numbers.insert(dis(gen));
	}

	for (int num : numbers) {
		std::cout << num << " ";
	}
	std::cout << std::endl << std::endl;
}

int main() {
	int count;

	std::cout << "[로또 번호 자동 추첨기]" << std::endl << std::endl;
	std::cout << "추첨할 총 횟수를 입력하세요 : ";
	std::cin >> count;
	std::cout << std::endl;

	for (int i = 0; i < count; i++) {
		cal();
	}

	return 0;
}