[C++] set과 unorderd_set

alsry._.112·2023년 10월 23일

cpp 자료구조

자료구조

목록 보기

2/3

이번에 알아볼 것은
set 과
unorderd_set 이다.

set

C++의 set은
노드 기반 컨테이너로써 균형 이진 트리(레드블렉트리)로 구현 되어있으며,
Key라 불리는 원소들의 집합으로 이루어진 컨테이너 이다. (원소 = key)

set은 균형 이진 트리를 이용해 중복 요소가 허용되지 않는 컨테이너이다. 즉, 같은 값을 여러 번 저장할 수 없다.
또한 key에 따라 정렬된다는 특징이 있다.

노드기반?

처음들어보면 생소 할 수 있지만 말 그대로
빨간색으로 동그라미 쳐진
노드들로 이루어져 있다고 생각하면 편하다.

사용방법

#include <iostream>
#include <set> //set을 사용하기 위해 추가해주어야 한다.
using namespace std;

int main()
{
    set<int> mySet; // set<자료형> 이름으로 선언한다.
    mySet.insert(1); // insert로 값을 추가한다.
    mySet.insert(2); // insert로 값을 추가한다.
    mySet.insert(3); // insert로 값을 추가한다.

    // 중복된 값을 추가하려고 하면 무시된다.
    mySet.insert(3);

    // Set 내부 요소는 자동으로 정렬된다.
    cout << "Set의 내용: ";
    for (auto element : mySet)
    {
        cout << element << " ";
    }

    cout << endl;

    // Set에서 요소를 검색
    int key = 2;
    if (mySet.find(key) != mySet.end()) // find를 통해 찾지 못하면 set.end()를 반환한다.
    {
        cout << key << "을(를) 찾았습니다." << endl;
    }
    else
    {
        cout << key << "을(를) 찾지 못했습니다." << endl;
    }

    // 요소를 제거
    int remove = 8;
    mySet.erase(remove); // set에서 remove를 제거한다.

    // set 내용을 출력
    cout << "제거 후: ";

    for (auto element : mySet)
    {
        cout << element << " ";
    }

    cout << endl;

}

unorderd_set

unorderd_set은 이름에서도 알 수 있듯이 원소들이 정렬되어 있지 않다.

set의 경우 원소들이 순서대로 정렬되어서 내부에 저장되지만, unordered_set의 경우 반복문으로 원소들을 하나씩 출력해보면 거의 랜덤한 순서로 나오는 것을 볼 수 있다.

또한 unordered_set은 set과는 달리 해시테이블로 구현 되어있다.

그럼 왜 쓰는데

정렬도 되지 않는 unordered_set을 쓰는 이유는
실행 시간 차이 때문이다.

unordered_set은 insert, erase, find 모두가
O(1).
으로 수행된다!

set의 경우 O(logn). 이었지만
unordered_set의 경우 상수 시간에 원소를 삽입하고, 검색할 수 있다.

수행시간이 다른 이유는
set은 레드블랙트리.,
unordered_set은 해시테이블.로 구현되었기 때문이다.

따라서 딱히 정렬을 하지 않아도 될 상황에서는 unordered_set을 사용하는 것이 더 좋다고 할 수 있다.

unordered_set도 중복된 값은 허용하지 않는다.

사용방법

#include <iostream>
#include <unordered_set> //unordered_set을 사용하기 위해 추가해주어야 한다.
using namespace std;

int main()
{
    unordered_set<int> mySet; // unordered_set<자료형> 이름으로 선언한다.
    mySet.insert(1); // insert로 값을 추가한다.
    mySet.insert(2); // insert로 값을 추가한다.
    mySet.insert(3); // insert로 값을 추가한다.

    // 중복된 값을 추가하려고 하면 무시된다.
    mySet.insert(3);

    // Set 내부 요소는 정렬되지 않음.
    cout << "Set의 내용: ";
    for (auto element : mySet)
    {
        cout << element << " ";
    }

    cout << endl;

    // Set에서 요소를 검색
    int key = 2;
    if (mySet.find(key) != mySet.end())
    {
        cout << key << "을(를) 찾았습니다." << endl;
    }
    else {
        cout << key << "을(를) 찾지 못했습니다." << endl;
    }

    // 요소를 제거
    int toRemove = 3;
    mySet.erase(toRemove); // unordered_set에서 요소를 제거한다.

    // Set 내용을 출력
    cout << "제거 후: ";
    for (const auto& element : mySet)
    {
        cout << element << " ";
    }

    cout << endl;
}