[C++ STL] std::set 개요

※ std::set 요약

std::set은 std::map과 상당히 비슷한 연관 컨테이너이다. 다른 점이 있다면 value 없이 key만으로 이뤄졌다는 것 정도이다.

std::set은 노드 기반 컨테이너이며 균형 이진 트리로 구현 되므로 균형 이진 트리의 모든 특징을 갖는다.

std::set은 std::map과 마찬가지로 중복된 key를 저장할 수 없으므로, 중복 저장하고 싶다면 std::multiset을 사용해야 한다.

동일 타입 집합이라는 점에서는 std::vector와 같지만 요소가 정렬된 위치에 삽입 된다는 점이 다르다.

 

※ std::set 특징

- std::set은 std::map과 상당히 비슷하다. 차이점이라면 std::map과 다르게 value 없이 key만 저장한다는 것 정도다.

- std::set의 key는 중복될 수 없다. 중복 저장해야 한다면 std::multiset을 사용한다.

- 데이터 삽입과 동시에 정렬이 일어난다.

- 정렬은 key를 기준으로 정렬되며 기본 정렬 기준은 less(오름차순) 정렬이다.

- 검색 또한 key를 기준으로 검색(이분검색)한다.

- 검색시 균형 이진 트리를 이용한 로그 시간 검색 복잡도를 보장한다.

 

※ std::set을 사용해야 하는 경우

- 삽입과 동시에 정렬해야 할때

- key가 있는지 없는지 알아야 할때

- 많은 데이터를 보관해야 하고, 동시에 검색이 빨라야 할때

- 많은 데이터가 중복 되어서는 안 되며 빠른 검색으로 존재 여부를 신속하게 알고 싶을때!