set 클래스

중복되지 않은 요소들을 자동으로 정렬하여 저장하는 연관 컨테이너이다.

특징

• 각 요소는 유일하며, 중복된 값은 허용하지 않는다.
• 요소는 자동으로 정렬(기본적으로 오름차순)
• Red-Black Tree(이진 탐색 트리) 구현
• 삽입, 삭제, 검색 연산은 O(log n)의 시간 복잡도

주요 멤버함수

1. 생성자 / 초기화

#include <iostream>
#include <string>
#include <set>

// 1. 비교 로직을 정의하는 일반 함수 (내림차순)
bool comp(const int& _a, const int& _b)
{
    return _a > _b;
}

// 2. 비교 로직을 정의하는 함수 객체(Functor) (오름차순)
class Compare
{
public:
    // operator()를 오버로딩하여 객체를 함수처럼 호출할 수 있게 합니다.
    bool operator()(int _a, int _b) const { return _a < _b; }
};

int main()
{
    // 기본 생성자 : 비어있는 set을 생성합니다. 기본 정렬 기준은 오름차순(std::less)입니다.
    std::set<int> s1;

    // 초기화 리스트 생성자 : 중괄호 {} 안의 원소들로 set을 초기화합니다.
    // set은 자동으로 중복된 원소(4)를 제거하고 오름차순으로 정렬합니다. {2, 3, 4, 12}
    std::set<int> s2 = { 2, 4, 12, 3, 4 };

    // 복사 생성자 : s2의 모든 원소를 복사하여 새로운 set s3를 생성합니다.
    std::set<int> s3 = s2;

    // 이동 생성자 : s3의 소유권을 s4로 이전합니다. 복사보다 효율적입니다.
    // 이동 후 s3는 비어있는 상태가 됩니다.
    std::set<int> s4 = std::move(s3);

    // 반복자 범위(iterator range)로 set 생성 : 다른 컨테이너의 특정 범위의 원소들로 set을 생성합니다.
    // s2의 시작(begin)부터 끝(end)까지의 원소로 s5를 생성합니다.
    std::set<int> s5(s2.begin(), s2.end());

    // --- 사용자 정의 비교 함수를 사용한 set 생성 ---
    // set의 두 번째 템플릿 인자로 비교 함수의 타입을 지정해야 합니다.

    // 1. 함수 포인터 사용 (내림차순)
    // decltype(&comp)으로 comp 함수의 포인터 타입을 추론하여 템플릿 인자로 전달합니다.
    // 생성자에는 실제 함수 포인터(comp)를 인자로 전달합니다.
    std::set<int, decltype(&comp)> s6(comp);

    // 2. 함수 객체(Functor) 사용 (오름차순)
    // 템플릿 인자로 함수 객체의 타입(Compare)을 전달합니다.
    // 별도의 생성자 인자는 필요 없습니다.
    std::set<int, Compare> s7;

    // 3. 람다(Lambda) 함수 사용 (내림차순)
    // 비교 로직을 람다 표현식으로 정의합니다.
    auto comp2 = [](int _a, int _b) { return _a > _b; };
    // decltype(comp2)으로 람다 함수의 타입을 추론하여 템플릿 인자로 전달합니다.
    // 생성자에는 람다 객체(comp2)를 전달합니다.
    std::set<int, decltype(comp2)> s8(comp2);

    // 4. 표준 라이브러리 함수 객체 사용 (내림차순)
    // C++ 표준 라이브러리에서 제공하는 std::greater를 사용하여 내림차순으로 정렬합니다.
    std::set<int, std::greater<int>> s9;


    // --- 대입 연산자 ---

    // 복사 대입 연산자
    std::set<int> s10;
    s10 = s2; // s10에 s2의 모든 원소를 복사합니다.

    // 이동 대입 연산자
    std::set<int> s11;
    s11 = std::move(s2); // s11이 s2의 자원을 가져옵니다. s2는 비게 됩니다.

    // 초기화 리스트 대입
    std::set<int> s12;
    s12 = { 10, 2, 54, 1, 421, 521 }; // s12의 기존 내용을 지우고 새 원소들을 할당합니다.

    return 0;
}

2. 조작(삽입)

#include <iostream>
#include <set>

int main()
{
    std::set<int> s1;
    std::set<int> s2;

    // insert(const Type& value) : 요소 삽입
    // 반환 타입 : std::pair<iterator, bool>
    // second 에서 성공여부 확인 가능
    std::pair<std::set<int>::iterator, bool> pair = s1.insert(1);
    if (!pair.second)
    {
        std::cout << "요소 삽입 실패" << std::endl;
    }

    // insert(iterator hint, const Type& value) : 힌트를 사용한 요소 삽입
    // iterator hint : 이 매개변수는 삽입할 위치에 대한 힌트를 제공
    // 삽입 위치를 미리 알고 있다면, 탐색 시간을 줄여 성능을 향상

    // 힌트가 정확하면 -> 상수 시간 O(1) (amortized)
    // 힌트가 부정확하면 -> 로그 시간 O(log n) (일반 insert와 동일)

    // 힌트가 유효한 경우란? 힌트가 유효하려면, 삽입될 요소가 힌트 위치 바로 앞이나 뒤에 들어가야 합니다.

    // 반환 타입 : std::set<T>::iterator
    for (int i = 0; i < 10; i++)
    {
        s1.insert(s1.end(), i);
    }

    // void insert(first, last) : 범위 삽입
    s2.insert(s1.begin(), s1.end());

    // 직접 객체 생성 (복사, 이동x)
    // 반환 타입 : std::pair<iterator, bool>
    std::pair<std::set<int>::iterator, bool> pair2 = s1.emplace(54);

    // 힌트를 사용한 직접 객체 생성 (복사, 이동x)
    // 반환 타입 : std::set<T>::iterator
    std::set<int>::iterator it2 = s2.emplace_hint(s2.end(), 11);


    std::cout << "s1" << std::endl;
    for (const auto& val : s1)
    {
        std::cout << val << " ";
    }
    std::cout << std::endl;
    std::cout << "s2" << std::endl;
    for (const auto& val : s2)
    {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

3. 조작(삭제)

#include <iostream>
#include <set>

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

    for (int i = 0; i < 10; i++)
    {
        s1.insert(s1.end(), i);
    }

    // erase(iterator pos) : 반복자 위치의 요소 삭제
    // 반환 타입 : iterator
    std::set<int>::iterator it = s1.erase(s1.begin());

    // erase(const Type & value) : 특정 값 삭제
    // 반환 타입 : size_type
    // 삭제한 요소의 개수를 반환
    size_t size = s1.erase(1);

    // erase(iterator first, iterator last) : 반복자 위치의 요소 삭제
    // 반환 타입 : iterator
    // 삭제된 다음 위치의 반복자(iterator)를 반환
    std::set<int>::iterator it2 = s1.erase(s1.begin(), s1.end());

    // clear() : 모든 요소 삭제
    s1.clear();

    return 0;
}

4. 검색

#include <iostream>
#include <set>

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

    for (int i = 0; i < 10; i++)
    {
        s1.insert(s1.end(), i);
    }

    // find(const Type& value) : 요소 검색
    // 반환 타입 : iterator
    // 찾은 요소를 가리키는 반복자를 반환한다
    // 요소가 없을시 마지막 요소의 다음을 가리킨다 == end()
    std::set<int>::iterator it = s1.find(1);

    if (it != s1.end())
    {
        std::cout << *it << std::endl;
    }

    // count(const Type& value) const : 요소 개수 반환
    // 반환 타입 : size_type
    // 찾은 요소의 개수를 반환 없으면 0
    size_t size = s1.count(2);
    std::cout << "2 요소 개수 : " << size << std::endl;

    // lower_bound(const Type& value) : value 이상인 첫 번째 요소
    // 반환 타입 : iterator
    // 찾은 요소를 가리키는 반복자를 반환한다
    // 요소가 없을시 마지막 요소의 다음을 가리킨다 == end()
    std::set<int>::iterator it2 = s1.lower_bound(5);
    std::cout << "5 이상인 첫 번째 요소 : " << *it2 << std::endl;

    // upper_bound(const Type& value) : value 초과인 첫 번째 요소
    // 반환 타입 : iterator
    // 찾은 요소를 가리키는 반복자를 반환한다
    // 요소가 없을시 마지막 요소의 다음을 가리킨다 == end()
    std::set<int>::iterator it3 = s1.upper_bound(5);
    std::cout << "5 초과인 첫 번째 요소 : " << *it3 << std::endl;

    // equal_range(const Type&) : 특정 값과 일치하는 요소의 범위를 나타내는 반복자 쌍을 반환
    // 반환타입 : std::pair<iterator, iterator>
    // first : 찾는 값 이상인 첫 번째 요소를 가리키는 반복자
    // second : 찾는 값보다 큰 첫 번째 요소를 가리키는 반복자
    // 단일로 사용하면 같은 값이 유일하기때문에 하나
    // 동일한 값을 가진 여러 요소의 범위를 반환할때 사용함 유용 - std::multiset
    std::pair<std::set<int>::iterator, std::set<int>::iterator> pair = s1.equal_range(7);

    return 0;
}

// 값 삭제 erase(const Type & value): 삭제한 요소 개수 반환
// 범위 삭제 erase(iterator first, iterator last): 삭제 후 다음 위치 반복자 반환
// 단일 반복자 삭제 erase(iterator pos): 삭제 후 다음 위치 반복자 반환

5. 용량

#include <iostream>
#include <set>

int main()
{
    std::set<int> s1 = { 1,2,3,4,5,6,7,8,9,10 };

    // empty() const : 비어있는지 확인
    // 반환 타입 : bool
    // 비어있으면 true 아니면 false
    bool isempty = s1.empty();

    // size() const : 요소의 개수 반환
    // 반환 타입 : size_type
    size_t size = s1.size();

    // max_size() const : 최대 저장 가능한 요소의 개수
    // 반환 타입 : size_type
    size_t size2 = s1.max_size();

    return 0;
}

6. 반복자

#include <iostream>
#include <set>

int main()
{
    std::set<int> s1 = { 1,2,3,4,5,6,7,8,9,10 };

    // begin() : 첫 번째 요소를 가리키는 반복자
    std::set<int>::iterator it1 = s1.begin();

    // end() : 마지막 요소 다음을 가리키는 반복자
    std::set<int>::iterator it2 = s1.end();

    // rbegin() : 역방향 첫 번째 요소
    std::set<int>::reverse_iterator it3 = s1.rbegin();

    // rend() : 역방향 마지막 요소 다음
    std::set<int>::reverse_iterator it4 = s1.rend();

    // cbegin() : 상수 반복자 begin()
    std::set<int>::const_iterator it5 = s1.cbegin();

    // cend() : 상수 반복자 end()
    std::set<int>::const_iterator it6 = s1.cend();

    // crbegin() : 역방향 상수 반복자 rbegin()
    std::set<int>::const_reverse_iterator it7 = s1.crbegin();

    // crend() : 역방향 상수 반복자 rend()
    std::set<int>::const_reverse_iterator it8 = s1.crend();

    return 0;
}

7. 연산자

#include <iostream>
#include <string>
#include <set>

int main()
{
    std::set<int> s1 = { 1,2,3,4,5,6,7,8,9,10 };
    std::set<int> s2 = { 1,2,3,4,5,6,7,8,9,10 };
    std::set<int> s3 = { 5,6,7,8,9,10,11,12,13,14 };

    // == (같음) 연산자
    // 두 set의 크기가 같고, 모든 원소가 순서대로 일치하면 true를 반환합니다.
    if (s1 == s2)
    {
        std::cout << "s1 == s2" << std::endl;
    }

    // != (같지 않음) 연산자
    // 두 set의 원소가 하나라도 다르면 true를 반환합니다.
    if (s1 != s3) // s1과 s3는 원소가 다르므로 이 조건은 참이 됩니다.
    {
        std::cout << "s1 != s3" << std::endl;
    }

    // < (작음) 연산자
    // 사전 순서로 비교했을 때, 왼쪽 set이 작으면 true를 반환합니다.
    // s3의 첫 원소(5)가 s2의 첫 원소(1)보다 크므로, s3 < s2는 false입니다.
    if (s3 < s2)
    {
        std::cout << "s3 < s2" << std::endl;
    }

    // > (큼) 연산자
    // 사전 순서로 비교했을 때, 왼쪽 set이 크면 true를 반환합니다.
    // s3의 첫 원소(5)가 s2의 첫 원소(1)보다 크므로, s3 > s2는 true입니다.
    if (s3 > s2)
    {
        std::cout << "s3 > s2" << std::endl;
    }

    // <= (작거나 같음) 연산자
    // 사전 순서로 비교했을 때, 왼쪽 set이 작거나 같으면 true를 반환합니다.
    // s3가 s2보다 크므로, s3 <= s2는 false입니다.
    if (s3 <= s2)
    {
        std::cout << "s3 <= s2" << std::endl;
    }

    // >= (크거나 같음) 연산자
    // 사전 순서로 비교했을 때, 왼쪽 set이 크거나 같으면 true를 반환합니다.
    // s3가 s2보다 크므로, s3 >= s2는 true입니다.
    if (s3 >= s2)
    {
        std::cout << "s3 >= s2" << std::endl;
    }

    return 0;
}

8. 기타

#include <iostream>
#include <string>
#include <set>

// set에 저장할 사용자 정의 클래스
class Person
{
public:
    std::string name;
    int age;
};

// Person 객체를 'age' 기준으로 비교하기 위한 함수 객체(Functor)
class CompareByAge
{
public:
    // operator()를 오버로딩하여 나이를 기준으로 오름차순 정렬 규칙을 정의합니다.
    bool operator()(const Person& _a, const Person& _b) const
    {
        return _a.age < _b.age;
    }
};

int main()
{
    std::set<int> s1 = { 1,2,3,4,5,6 };
    std::set<int> s2 = { 7,8,9,10,11,12 };

    // 사용자 정의 클래스(Person)와 비교 함수(CompareByAge)를 사용하는 set 생성
    std::set<Person, CompareByAge> p1;
    p1.insert({ "Alice", 25 });
    p1.insert({ "Bob", 30 });

    Person p2 = { "CC", 20 };
    Person p3 = { "BB", 35 };

    // key_comp() : set의 키 비교 함수 객체를 반환합니다.
    // value_comp() : set의 값 비교 함수 객체를 반환합니다.
    // std::set에서는 키와 값이 동일하므로 두 함수는 같은 것을 반환합니다.
    auto comp1 = s1.key_comp(); // s1은 기본 비교(std::less)를 사용하므로 comp1은 std::less<int> 객체입니다.
    int a = 10;
    int b = 20;

    // 수동으로 요소 비교: set의 정렬 기준을 외부에서도 동일하게 사용할 수 있습니다.
    if (comp1(a, b)) // comp1(10, 20)은 10 < 20 이므로 true입니다.
    {
        std::cout << a << "가 " << b << "보다 작음" << std::endl;
    }

    auto comp2 = p1.key_comp(); // p1의 비교 객체인 CompareByAge 객체를 가져옵니다.
    // set과 동일한 비교 기준으로 외부 로직 구현
    if (comp2(p2, p3)) // p2.age(20) < p3.age(35) 이므로 true입니다.
    {
        std::cout << "CC 가 BB보다 어림" << std::endl;
    }

    // 범위 내 요소 순회하며 비교 로직 사용
    int target = 4;
    // s1의 모든 요소를 순회합니다.
    for (auto it = s1.begin(); it != s1.end(); it++)
    {
        // !comp1(4, *it)는 !(4 < *it)와 같고, 이는 4 >= *it 와 동일합니다.
        // 즉, 4보다 작거나 같은 요소들을 출력합니다.
        if (!comp1(4, *it))
        {
            std::cout << *it << std::endl;
        }
    }

    // get_allocator() : 메모리 할당자를 반환하는 함수
    // 이 함수는 메모리 관리와 관련된 고급 작업에 사용됩니다. (일반적으로는 잘 사용하지 않습니다.)
    auto alloc = p1.get_allocator();
    // Person 객체 10개를 저장할 메모리를 할당합니다.
    auto pp = alloc.allocate(10);
    // 할당받은 메모리를 해제합니다.
    alloc.deallocate(pp, 10);

    // swap() : 두 set의 요소들을 교환합니다.
    // 컨테이너 내부의 포인터만 교환하므로 매우 효율적인(O(1)) 연산입니다.
    s1.swap(s2);

    return 0;
}