set은 꾸러미 안에 데이터들은 넣는 STL이다
#include <iostream>
#include <set>
int main(int argc, char const *argv[]) {
std::set<int> nums{1,2,3,4,5};
return 0;
}위 코드를 메모리에서 보게 되면
스택에 nums 포인터가 힙에 넣은 1~5 객체를 가리킨다.
set의 보통 트리는 red black tree나 binary search tree를 가진다
부모노드보다 작으면 왼쪽 자식노드에, 보다 크면 오른쪽 자식노드에 넣는다
원소를 찾는데는 계속 좌 우 자식원소 두개씩하므로 O(lg n)의 시간복잡도를 가지고
원소가 새로 들어가거나 없어지면 새로 트리를 만들어야하므로 O(lg n)의 시간복잡도가 걸린다.
set의 또 다른 특징은 중복을 잡아준다는 것이다.
#include <iostream>
#include <set>
int main(int argc, char const *argv[]) {
std::set<int> nums{1,2,3,4,5};
nums.emplace_back(3);
nums.emplace_back(3);
nums.emplace_back(6);
nums.emplace_back(3);
return 0;
}을 출력해보면 1,2,3,4,5,6,7이 나온다.
이렇게 정렬되서 출력되는 이유는 새로운 원소가 들어오면 정렬을 하기 때문이다.
set에는 개인이 만든 연산을 넣을 수 있다
원래 set은 오름차순이지만 커스텀 연산으로 내림차순으로 나타난 것을 볼 수 있다.
만약 위와같은 연산이 있다면
이 나오는데 그 이유는 operator()에서 11, 21, 101 모두 1로 연산되기 때문이다.
위와 같이 Cat 객체를 set에 넣고 출력시켜보면 에러가 발생한다.
그 이유는 set은 comparision 연산자로 정렬하게되는데 Cat객체에는 정의되어있지 않기 때문이다.
따라서 comparision 연산자를 정의해주면
제대로 출력이 된다.
만약 위와같이 나이가 겹치는 경우 comparision 연산자에서 겹쳐 nocope는 추가 되지않는다
이는 name도 비교하여 해결할 수 있다.
