Set

Set은 고유한 값을 저장하는 데이터 구조로, 중복된 요소를 허용하지 않습니다. 수학에서의 집합과 유사한 개념으로, 특정 값이 집합에 존재하는지 확인하거나, 두 집합 간의 연산을 수행하는 데 사용됩니다. Set은 보통 해시 테이블이나 이진 검색 트리를 사용하여 구현됩니다.

 

STL에는 이진 검색 트리를 활용한 std::set과, Hash를 활용한 std::unordered_set이 구현되어 있습니다.

---

 

std::set은 C++표준 라이브러리 (STL)에서 제공하는 연관 컨테이너로, 고유한 값을 자동으로 정렬하여 저장하는 데이터 구조입니다. 중복된 값을 허용하지 않으며, 값의 삽입, 삭제, 검색 연산이 효율적으로 수행됩니다.

 

std::set의 주요 특징과 기능은 다음과 같습니다:

1. 고유한 값 저장
   • 정의: std::set은 중복된 값을 허용하지 않습니다. 삽입하려는 값이 이미 존재하면 삽입되지 않습니다.
   • 설명: 이로 인해 std::set에 저장된 모든 값은 유일합니다.
2. 자동 정렬
   • 정의: std::set에 저장된 값은 자동으로 정렬됩니다.
   • 설명: 기본적으로 오름차순으로 정렬되며, 커스텀 비교 함수(comparator)를 사용하여 정렬 순서를 변경할 수 있습니다.
3. 효율적인 연산
   • 정의: 삽입, 삭제, 검색 연산의 평균 시간 복잡도는 O(log n)입니다.
   • 설명: 이는 std::set이 내부적으로 이진 검색 트리(주로 레드-블랙 트리)를 사용하여 구현되기 때문입니다.

---

 

 

std::unordered_set은 C++ 표준 라이브러리(STL)에서 제공하는 연관 컨테이너로, 고유한 값을 저장하는 해시 기반 데이터 구조입니다. 중복된 값을 허용하지 않으며, 값의 삽입, 삭제, 검색 연산이 평균적으로 매우 빠르게 수행됩니다.

 

std::unordered_set의 주요 특징과 기능은 다음과 같습니다:

1. 고유한 값 저장
   • 정의: std::unordered_set은 중복된 값을 허용하지 않습니다. 삽입하려는 값이 이미 존재하면 삽입되지 않습니다.
   • 설명: 이로 인해 std::unordered_set에 저장된 모든 값은 유일합니다.
2. 자동 정렬
   • 정의: std::unordered_set에 저장된 값은 특정 순서로 정렬되지 않습니다.
   • 설명: 요소들은 해시 값에 따라 저장되며, 삽입된 순서나 값의 크기에 관계없이 무작위 순서로 저장됩니다.
3. 효율적인 연산
   • 정의: 삽입, 삭제, 검색 연산의 평균 시간 복잡도는 O(1)입니다.
   • 설명: 이는 std::unordered_set이 내부적으로 해시 테이블을 사용하여 구현되기 때문입니다.