Set Library C++

Set Library

중복 없는 정렬된 데이터를 저장하고 관리하는 데 유용한 자료구조이다.

효율적인 탐색, 삽입, 삭제 작업을 지원하고, 데이터를 자동으로 정렬하여 유지해준다.

 

두 가지 주요 클래스인 Set과 Multiset이 있다.

 

1. set 클래스

중복 허용 안함 : set 은 중복된 원소를 허용하지 않으며, 동일한 값이 두 번 삽입되지 않는다.

 

자동 정렬 : 삽입되 원소는 자동으로 정렬되며, 기본적으로 오름차순으로 정렬된다.

 

탐색, 삽입, 삭제 효율성 : Set 은 내부적으로 균형 이진 트리(BST), 특히 레드-블랙 트리로 구현되며,

평균적으로 O(log n)의 시간 복잡도를 가진다.

 

(레드-블랙 트리 : 자가 균형 이진 탐색 트리) 

 

1 - (1). 주요 멤버 함수

std::set s;

 

insert : 새로운 원소를 삽입하며, 중복된 값이 들어오면 삽입을 무시한다.

사용 : s.insert(10);

 

find : 특정 원소의 존재 여부를 확인한다. 원소가 있다면 해당 위치의 반복자를 반환하고, 없다면 end()를 반환

사용 : auto it = s.find(10); //10 있으면 위치 반환, 없다면 s.end() 반환

 

erase : 특정 원소를 제거한다. 원소가 존재하지 않을 경우 아무 동작도 하지 않는다.

사용 : s.erase(10); 값이 10인 원소 제거

 

begin과 end  : set의 시작과 끝을 나타내는 반복자를 반환. begin은 가장 작은 원소를 end는 마지막 원소를 가리킨다.

사용 :  s.begin();    s.end();

 

size,empty : size는 원소의 개수를 반환하고, empty는 set이 비어 있는지 여부를 반환한다.

사용 : s.size(); s.empty();

 

lower_bound : 주어진 값 이상인 첫 번째 원소의 반복자를 반환

사용 : s.lower_bound();

 

upper_bound : 주어진 값보다 큰 첫 번째 원소의 반복자를 반환한다.

사용 : s.upper_bound();

 

 

2. multiset 

set과 거의 동일하지만, 중복 원소를 허용한다는 점에서 차이가 있다.

다른 특징과 연산은 set과 동일하며, 중복된 값들이 여러 개 필요할 때 유용하게 사용가능하다.

 

 

 

 

3. unordered_set

중복 없는 원소를 저장하며, 정렬되지 않은 집합을 제공한다.

내부적으로 해시 테이블을 사용하여 원소를 관리하기 때문에, 탑색, 삽입, 삭제의 평균 시간 복잡도가

O(1)이며, 정렬이 필요없고, 고속의 탐색과 수정이 요구되는 상황에서 유용하게 사용할 수 있다.

 

3 - (1) 특징

중복 허용 안함 : unordered_set은 중복된 원소를 허용하지 않는다. 동일한 값이 이미 존재하는 경우 상비을 무시한다.

 

정렬되지 않음 : unordered_set의 원소들은 삽입 순서와 무관하게 저장되며, 자동 정렬을 하지 않습니다.

 

해시 테이블 사용 : unordered_set은 해시 테이블을 기반으로 동작하며, 이는 특정 원소에 대한 탐색, 삽입, 삭제가 평균적으로 O(1)의 시간 복잡도를 갖게된다. 하지만 해시 충돌이 발생할 경우, 최악의 경우 O(n) 까지 늘어날 수 있다.

 

해시 함수 커스터마이징 기능 : unordered_set은 기본적으로 std::hash를 사용하여 원소의 해시 값을 생성하지만,

사용자가 해시 함수를 커스터마이징 할 수 있다.

 

3 - (2) 주요 멤버 함수

std::unordered_set<int> us;

 

insert, find, earse, begin,end, size, empty

 

clear() : 모든 원소를 삭제한다.

사용법 : us.clear();

 

count() : 특정 원소의 존재 여부를 확인하는 데 사용되며, 존재하면 1을, 없는 경우 0을 반환한다.

사용법 : us.count(10);

 

버킷 관련 함수 : 해시 테이블의 내부 구조를 제어하기 위한 함수(bucket_count, max_bucket_count, bucket_size, bucket 등)이 제공되며, 이들은 특정 원소가 어떤 버킷에 저장되는지, 그리고 버킷 수를 확인하고 조정하는 데 사용된다.

 

 

3 - (3) 해시 함수 커스터 마이징

unordered_set은 사용자 정의 자료형을 저장할 수 있으며, 이를 위해 해시 함수를 정의해햐 한다.

예를 들어, 구조체를 해시 값으로 다루려면 다음과 같은 형태로 해시 함수를 정의할 수 있다.

 

unordered_set은 원소의 순소가 중요하지 않거나, 중복 없이 빠르게 탐색해야 하는 경우에 유용하게 사용이 가능하다.