C++ Set 사용하기

개념

set은 treeset 자료구조로 되어 있다. treeset은 균형잡힌 이진트리 구조로 데이터를 관리해준다.

삽입, 삭제, 탐색 등 모든 함수의 시간복잡도가 전부$O(logN)$

중복이 허용되지 않음

 

균형잡힌 이진 트리 (Balanced Binary Tree)

: 균형잡힌 이진 트리는 각 노드의 왼쪽 서브트리와 오른쪽 서브트리 높이 차이가 최대 1인 이진 트리

균형잡힌 트리는 항상 높이 균형을 유지하기 때문에 트리의 깊이가 상대적으로 작다 → 탐색, 삽입, 삭제 등의 연산이 빠르게 수행됨

ex) AVL 트리, 레드-블랙 트리 등

 

언제 쓰는가

1. 지금까지 살펴본 숫자들 중 특정 숫자 k보다 같거나 큰 숫자를 빠르게 구하는 경우
2. 지금까지 살펴본 숫자들 중 최댓값을 계속 구하는 경우
3. 지금까지 살펴본 숫자들 중 최댓값을 계속 구해주며, 그 중 원하는 숫자를 지속적으로 제거하는 경우
   • 최댓값만 계속 구해주는 것은 Priority Queue (우선순위 큐)를 이용해도 가능하지만, 우선순위 큐의 경우에는 삭제 연산을 최댓값에 대해서만 진행할 수 있기 때문에 원하는 원소를 직접 골라 자유자재로 삭제하는 것은 불가능
4. 인접한 숫자를 구하는 경우(vector, stack, queue, deque, map, set, unordered_map, unordered_set 등 사용가능)

 

기본 사용법

#include<set>

set<int> s; // 선언
s.insert(1); // 삽입
s.erase(1); // 삭제
s.find(1); // 검색,조회


// 위치(iterator)를 반환. 해당 위치의 값을 사용하고 싶다면 앞에 *을 붙여야 함
// ex) *s.begin(): set시작 위치의 원소 값
s.lower_bound(1); // 1 이상의 숫자(x>=1)의 최초 위치
s.upper_bound(1); // 1 초과 숫자(x>1)의 최초 위치
s.begin(); // set의 시작 위치(첫 번째 원소의 위치)
s.end(); // set의 마지막 원소의 다음 위치
s.rbegin(); // set의 마지막 위치(마지막 원소의 위치)
s.rend(); // set의 시작 위치 이전 위치

 

set<pair<int, int> > s를 사용하는 경우

• lower_bound: pair의 1번째(first)에 적힌 값과 같거나 큰 최초값의 iterator 반환. 1번째 값이 같다면 2번째 값(second)이 가장 작은 경우를 반환. 
• upper_bound: pair의 1번째에 적힌 값보다 큰 최초값의 iterator 반환. 1번째 값이 같다면 2번째 값이 가장 작은 경우를 반환.

 

set 정렬 바꾸기

https://stackoverflow.com/questions/2620862/using-custom-stdset-comparator

기본 자료형

https://chanhuiseok.github.io/posts/algo-46/

// 1. 람다식을 이용
auto cmp = [](int a, int b) { return ... };
std::set<int, decltype(cmp)> s;


// 2. bool 함수를 이용
bool cmp(int a, int b) {
    return ...;
}
std::set<int, decltype(cmp)*> s(cmp);
std::set<int, decltype(&cmp)> s(&cmp);


// 3. struct with () operator (Old solution)
struct cmp {
    bool operator() (int a, int b) const {
        return ...
    }
};

// ...
// later
std::set<int, cmp> s;

 

We use lambda function as comparator. As usual, comparator should return boolean value, indicating whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines.

비교자로 람다 함수를 사용합니다. 평소와 같이 비교기는 첫 번째 인수로 전달된 요소가 정의된 특정 엄격한 약한 순서에서 두 번째 요소보다 먼저 오는 것으로 간주되는지 여부를 나타내는 부울 값을 반환해야 합니다.

 

pair<int, int> 의 경우

// 1. lamda
auto cmp = [](const pair<int, int>& lhs, const pair<int, int>& rhs) {
    if(lhs.second == rhs.second) 
        return lhs.first < rhs.first;
    return lhs.second < rhs.second;
};
set<pair<int, int>, decltype(cmp)> question(cmp);


// 2. bool function
bool cmp (const pair<int, int>& lhs, const pair<int, int>& rhs){
    if(lhs.second==rhs.second) return lhs.first<rhs.first;
    return lhs.second<rhs.second;
}
set<pair<int,int>, decltype(&cmp)> question(cmp);


// 3. old solution
struct Compare{
    bool operator() (const pair<int, int>& lhs, const pair<int, int>& rhs) const{
        if(lhs.second==rhs.second) return lhs.first<rhs.first;
        return lhs.second<rhs.second;
    }
};
set<pair<int,int>, Compare> question;

 

참고

코드트리 intermediate mid 중급 자료구조 TreeSet

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

https://stackoverflow.com/questions/55392781/how-to-use-lower-bound-on-set-of-pairs
https://stackoverflow.com/questions/2620862/using-custom-stdset-comparator