STL 컨테이너 - set

set

C++에서 std::set은 **STL(Standard Template Library)**에서 제공하는 컨테이너 중 하나로, 키 값을 기준으로 정렬된 순서로 요소를 저장하는 컨테이너입니다. 특히 집합을 다룰때 적합한 컨테이너입니다. std::set은 다른 순차 컨테이너나 연관 컨테이너와는 따로 분류되는 경향이 있는데 이는 그들의 사용 목적이 특별하기 때문입니다. 이에 대해서는 아래에 적어두겠습니다.

 

혹시 std::unordered_set과 헷갈린다면 아래 글에서 둘의 차이를 확인하세요.

https://coding-potato-record.tistory.com/269

C++/STL 컨테이너STL 컨테이너 - unordered_set

 

1. std::set의 특징

• 중복 없는 원소: std::set은 중복된 요소를 허용하지 않습니다. 동일한 값은 추가되지 않습니다.
• 자동 정렬: 삽입된 요소는 자동으로 정렬됩니다. 기본적으로 오름차순 정렬되며, 사용자가 비교 함수를 제공하여 내림차순으로 정렬할 수도 있습니다.
• 빠른 검색, 삽입, 삭제: 내부적으로 std::set은 이진 탐색 트리(구체적으로는 Red-Black Tree)로 구현되어 있어, 삽입, 삭제, 검색에 대해 평균 O(log N)의 시간 복잡도를 가집니다.

2. 헤더 파일

std::set를 사용하려면 <set> 헤더 파일을 포함해야 합니다.

3. 선언 및 초기화

std::set을 선언하고 초기화하는 방법은 여러 가지가 있습니다.

• 기본 선언:

• 초기화 리스트를 통한 초기화

• 다른 set에서 복사하여 초기화:

• 사용자 정의 비교 함수를 사용하는 선언:

 

4. 주요 멤버 함수

insert(value)	값 value를 set에 삽입합니다. 중복된 값은 삽입되지 않습니다.
find(value)	값 value를 찾아 그 위치를 가리키는 반복자를 반환합니다. 값이 없으면 end()를 반환합니다.
erase(value)	값 value를 삭제합니다. 삭제된 요소가 없으면 아무 작업도 하지 않습니다.
erase(iterator)	지정된 반복자가 가리키는 요소를 삭제합니다.
erase(range)	주어진 범위의 요소들을 삭제합니다.
count(value)	값 value가 set에 존재하는지 확인합니다. 존재하면 1, 없으면 0을 반환합니다.
size()	set에 저장된 요소의 개수를 반환합니다.
empty()	set이 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
begin()	set의 첫 번째 요소를 가리키는 반복자를 반환합니다.
end()	set의 마지막 요소 다음을 가리키는 반복자를 반환합니다.
lower_bound(value)	값 value 이상인 첫 번째 요소를 가리키는 반복자를 반환합니다.
upper_bound(value)	값 value보다 큰 첫 번째 요소를 가리키는 반복자를 반환합니다.
clear()	set의 모든 요소를 삭제합니다.

 

5. 다른 컨테이너와 분류되는 이유

집합 관련 컨테이너가 순차 컨테이너나 연관 컨테이너와 구분되는 이유는 그들의 동작 방식과 목적에 있습니다. 순차 컨테이너나 연관 컨테이너와는 약간 다른 특성을 지니기 때문에 별도로 분류되는 경우가 많습니다.

1. 집합 관련 컨테이너의 목적과 특성

집합 관련 컨테이너는 집합(Set) 자료구조를 구현하기 위한 컨테이너입니다. 집합은 중복을 허용하지 않는 특성이 있으며, 그 자체로 수학적 집합과 유사한 성질을 가집니다. 집합은 원소의 순서보다 원소의 존재 여부에 더 중점을 두고 있으며, 이를 기반으로 집합 연산(교집합, 합집합, 차집합 등)을 효율적으로 처리할 수 있도록 설계되어 있습니다.

집합 관련 컨테이너의 주요 특성:

• 중복 원소 허용 여부: 집합은 중복된 원소를 허용하지 않거나(std::set, std::unordered_set), 중복을 허용할 수 있습니다(std::multiset, std::unordered_multiset).
• 정렬 여부: std::set과 std::multiset은 데이터를 자동으로 정렬하여 저장하며, std::unordered_set과 std::unordered_multiset은 정렬되지 않은 상태로 저장됩니다.
• 수학적 집합 연산 지원: 집합은 교집합, 합집합, 차집합과 같은 연산을 처리하는 데 적합한 구조입니다.

2. 순차 컨테이너와 연관 컨테이너와의 차이점

• 순차 컨테이너는 데이터의 순서를 중요시합니다. 예를 들어, std::vector나 std::list와 같은 순차 컨테이너는 데이터를 저장할 때 순서가 중요한 자료구조로, 인덱스를 통해 데이터를 접근할 수 있습니다. 순차 컨테이너는 삽입 순서가 중요하고, 원소들이 순차적으로 배열되어 있기 때문에 중복을 허용합니다.
• 연관 컨테이너는 키-값 쌍으로 데이터를 저장하고, 데이터를 빠르게 검색할 수 있는 특성이 있습니다. 예를 들어, std::map과 std::unordered_map은 데이터를 키를 기준으로 저장하고 빠른 검색을 지원합니다. 연관 컨테이너는 키에 대한 정렬이나 해시를 사용하여 데이터를 처리합니다.

집합 관련 컨테이너가 다른 이유

1. 집합 연산의 특성: 집합 관련 컨테이너는 수학적 집합의 특성을 반영하여 설계되었습니다. 예를 들어, std::set과 std::unordered_set은 원소의 존재 여부에 중점을 두고 있으며, 중복을 허용하지 않음으로써 집합 연산에 최적화된 구조입니다. 반면에 순차 컨테이너는 순서가 중요하고, 연관 컨테이너는 키와 값에 중점을 둡니다.
2. 구조적 차이점:
   • 순차 컨테이너: 데이터가 순차적으로 저장되고 인덱스를 통한 접근이 가능.
   • 연관 컨테이너: 키-값 쌍을 저장하고 키를 기준으로 빠르게 검색 가능.
   • 집합 관련 컨테이너: 중복을 허용하지 않거나 허용하며, 원소의 존재 여부에 집중하는 자료구조입니다. 정렬된 집합과 정렬되지 않은 집합을 지원하며, 특정한 집합 연산을 지원합니다.

3. 사용 사례

• 순차 컨테이너는 데이터의 순서가 중요할 때 사용됩니다. 예를 들어, 순차적으로 처리해야 하는 작업에서 사용됩니다.
• 연관 컨테이너는 키를 기반으로 빠른 검색, 삽입, 삭제가 필요할 때 사용됩니다. 예를 들어, 키 값이 필요한 데이터베이스나 캐시 시스템에서 사용됩니다.
• 집합 관련 컨테이너는 중복을 허용하지 않거나 중복이 중요한 경우, 또는 집합 연산을 해야 할 때 사용됩니다. 예를 들어, 고유한 값들의 집합을 처리하거나, 특정 집합 연산이 필요한 경우에 사용됩니다.

결론

집합 관련 컨테이너가 순차 컨테이너나 연관 컨테이너와 구분되는 이유는, 그들이 수학적 집합의 특성에 맞춰 설계되었기 때문입니다. 이들은 중복을 허용하지 않거나 허용하며, 데이터의 존재 여부와 집합 연산에 중점을 두고 있기 때문에, 순차적 처리나 키-값 쌍을 저장하는 것과는 다른 목적을 가지고 있습니다. 이를 기반으로 구분하여 사용하는 것이 효율적입니다.