std::set

 

#include <iostream>
#include <set>
 
struct customFn
{
    bool operator() (const int lhs, const int rhs) const
    {
        return (lhs > rhs);
    }
};
 
int main()
{
    std::set<int, customFn> nums{ 1, 2, 3, 4, 5 };
 
    nums.emplace(11);
    nums.emplace(111);
    nums.emplace(1111);
    nums.emplace(-1111);
    for (const auto e : nums)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
    return 0;
}

 

set은

find, insert, delete 모두 logN의 시간 복잡도를 가지고 있다.

 

set은 정렬이 이미 되어 있다. 그래서 평균적인 소모 시간은 크지만 전체적인 시간은 적게 든다는 기대값을 가지게 된다.

 

예를 들면 트리의 경우 한쪽으로만 노드가 삽입되면 결국 연결리스트와 동일하기 때문에 그렇다.

 

set의 경우 RB트리(Red Black) Tree로 구현이 되어 있다.

 

set의 주요 기능중 하나는 중복의 제거에 있다. 중복 허용하는 것은 multiset이 있다.

 

 보통 알고리즘 풀이를 할떄 set의 연산자를 재정의하지 않고 많이 사용했는데

 

operator를 재정의해서 큰값이 루트로 오게 할 수 있다.

 

key-value를 원하면 map, key-value를 중복하길 원하면 multi-map이 있다.

 

RB tree는 삽입되거나 삭제될때 

 

ReStructing , Recoloring을 통해 BBST(Balanced Binary Search Tree)를 유지하게 된다.