[C++] set, multiset, unordered_set

1. set (#include <set>)

set의 특징

• 중복 제거
• 노드 기반으로 index 접근 불가
• Red-Black 트리 기반의 균형 이진 트리

 

Search: O(log n)

Insert: O(log n)

Delete: O(log n)

 

 

장점

• 삽입, 삭제, 검색과 같은 기본 작업 속도가 빠르다.
• 균형 이진 트리를 유지하는 방식이 Red-Black 트리 기반이기 때문에 오버헤드가 크진 않다.

 

단점

• Red-Black 트리의 노드 색상을 저장하기 위해 각 노드마다 1 bit의 추가 저장 공간이 요구된다.

 

multiset은 중복 허용인 set이라고 생각하면 된다.

unordered_set은 정렬이 아닌 set이라고 생각하면 된다.

unordered_multiset은 정렬이 아닌 multiset이라고 생각하면 된다.

 

※ unordered를 사용하기 위해선 #include <unordered_set> 추가

 

 

 

 

 

2. set 초기화

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

using namespace std;

int main(void) {

    set<int> s;

    s.insert(1);
    s.insert(3);
    s.insert(-5);
    s.insert(7);

    set<int> s1(s.begin(), s.end());    
    set<int> s2(s);
    set<int> s3 = s;
    
    // s1, s2, s3 = -5, 1, 3, 7
    
    vector<int> nums {1, 2, 3, 4, 5};
    unordered_set<int> s4(nums.begin(), nums.end());
    
    for (auto item = s4.begin(); item != s4.end(); item++)
    {
        cout << *item << "\n";
    }

    return 0;
}

 

 

 

 

 

3. set 관련 함수

begin(): 시작 iterator 반환

end(): 끝 iterator 반환

rbegin(): 끝 iterator를 시작점으로 지정

rend(): 시작 iterator를 끝 부분으로 지정

empty(): 현재 빈 상태인가에 대한 여부를 bool 형태로 반환

size(): 현재 저장되어 있는 요소 개수 반환

insert(): 값 삽입

erase(): 값 삭제

find(): 값 탐색 (찾지 못하면 end iterator 반환)