[C++] About STL Set Container in PS Algorithm

* PS 알고리즘 풀이에서 사용되는 STL Set Container 사용법에 관하여 간략하게 정리해 둔 포스팅 입니다. 

*잘못된 내용을 포함하고 있을 수 있으며, 수정할 내용이 있다면 댓글로 남겨주세요

---

#1 About STL Set 

- Set은 수학의 집합 개념을 본따서 설계된 자료구조 이기에 중복을 허용하지 않으며, 다양한 집합 관련 연산 (교집합 _ set_intersection , 합집합 set_union , 차집합 set_difference) 을 제공한다.

 

- STL Associative Container [연관 컨테이너] 에 속하는 set, multiset과 STL Unordered Associative Container [비정렬 연관 컨테이너] 에 속하는 unordered_set , unordered_multiset 으로 구분한다. 

 

set & multiset

1. 원소를 자동으로 정렬된 상태로 유지한다.

2. 이진 탐색 트리 (BST) 구조로 설계되어 있다.

3. 요소의 삽입, 삭제, 검색 연산이 O(LogN) 만큼의 시간 복잡도를 가진다.

4. multiset은 원소의 중복을 허용한다.

 

unordered_set & unordered_multiset

1. 원소가 정렬되어 있지 않다.

2. Hash Table 기반으로 구현되어 있다.

3. 요소의 삽입, 삭제, 검색 연산이 O(1) 만큼의 시간 복잡도를 가지지만 최악의 경우 (해시 충돌이 발생하는 상황에서) O(N) 만큼 성능이 저하될 수 있다.

4. unordered_multiset은 원소의 중복을 허용한다.

 

https://novlog.tistory.com/264

[DataStructure] Hash 자료구조 개념 정리

 

따라서 어떠한 컨테이너에 속한 set을 선택하는 지에 따라서 연산에 소모되는 시간 복잡도가 달라지기에, 문제 풀이 상황에 걸맞는 Set Contaienr를 선택해야 한다. 

Category	Container	원소 중복	원소 정렬 상태	시간 복잡도
Associative Container	set	x	o	O(LogN)
	multiset	o	o	O(LogN)
Unordered Associative Container	unordered_set	x	x	O(1)
	unordered_multiset	o	x	O(1)

 

* 참고로 Associative Container는 set, mulitset을 제외하고 2가지 컨테이너 (map, multimap) 를 추가로 제공한다. 

Associative Container는 동일한 인터페이스 (생성자, 멤버함수, 연산자) 를 제공하기에 한 가지 컨테이너의 사용 방법만 숙달하면 나머지 컨테이너는 별도의 러닝커브 없이 사용 가능하다.  

---

#2 Set Usage

* 알고리즘 문제 풀이에 필요한 정말 최소한의 사용방법만 다루었습니다. 

* Set Container의 자세한 내용은 공식 문서를 참고해 주세요.

* 다음 예제는 set 자료구조를 기반으로 작성되었으며, multiset, unordered_set, unordered_multiset의 경우 각 특성에 따라 출력 결과가 달라집니다. (중복 제거, 자동 정렬)

https://cplusplus.com/reference/set/

 

2.1 Declare Set

#include <set> 헤더파일을 추가한다.

using namespace std; 네임스페이스를 선언한다.

set<DataType> setName; 형태로 선언한다.

    set<int> intSetV1; // 1. int type set 선언
    set<int> intSetV2 = {1, 2, 3, 4, 5}; // 2. 선언과 동시에 초기화
    set<string> stringSetV1; // 3. string type set 선언
    set<string> stringSetV2 = {"nov", "dev"}; //4. 선언과 동시에 초기화

 

2.2 Insert

setName.insert(value);

set에 value를 추가한다.

    
    set<int> ordered_set;
    ordered_set.insert(10);
    ordered_set.insert(30);
    ordered_set.insert(20);
    ordered_set.insert(20); // 중복 원소 제거

    for (set<int>::iterator it = ordered_set.begin(); it != ordered_set.end(); it++) {
        cout << *it << " ";
    }

[Output} 10 20 30

 

2.3 Delete

setName.delete(value);

set에서 value를 제거한다.

    set<int> ordered_set = {10, 20, 30}
    ordered_set.erase(30); // 원소 30 제거

    for (set<int>::iterator it = ordered_set.begin(); it != ordered_set.end(); it++) {
        cout << *it << " ";
    }

[Output] 10 20

 

2.4 Find

setName.find(value);

set에서 value를 탐색한다.

원소가 존재하는 경우 해당 원소의 Iterator를 반환한다.

원소가 존재하지 않는 경우 setName.end()를 반환한다.

    set<int> ordered_set = {10, 20};

    // ordered_set.end()를 반환하지 않는 경우,
    // 즉 원소가 존재하는 경우
    if (ordered_set.find(20) != ordered_set.end()) {
        cout << "set 내부에 20이 존재합니다." << endl;
    }

[output] set 내부에 20이 존재합니다.

 

2.5 순회

1. iterator를 사용한 순회

    set<int> ordered_set = {10, 20, 30};

    // 1. iterator를 사용한 순회
    for (set<int>::iterator it = ordered_set.begin(); it != ordered_set.end(); it++) {
        cout << *it << " ";
    }

 

2. auto keyword를 사용한 축약

    set<int> ordered_set = {10, 20, 30};

    // 2. auto keyword 를 사용한 축약
    for (auto it = ordered_set.begin(); it != ordered_set.end(); it++) {
        cout << *it << " ";
    }

 

3. C++11 Range-Based-For

    set<int> ordered_set = {10, 20, 30};

    // 3. C++11 Range-Based-For
    for (const auto& element : ordered_set) {
        cout << element << " ";
    }

---

#참고문헌

https://cplusplus.com/reference/set/