C++ STL Set

 
 

set Class

 
 
C++ 표준 라이브러리 컨테이너 클래스 set는
컬렉션에서 데이터를 저장하고 검색하는 데 사용됩니다.

 

Set은 이진 탐색 트리 기반이고 오름차순이다 O(logn)의 속도를 가진다.
 
요소의 set 값은 고유하며 데이터가 자동으로 정렬되는 키값으로 사용됩니다.
요소의 set 값은 직접 변경되지 않을 수 있습니다.
대신, 이전 값을 삭제하고 새 값의 요소를 삽입해야 합니다.
 
 
즉, set은 중복없이 저장하는 자료구조입니다.
일종의 집합이라고 생각하시면 됩니다.
 
set의 특징으로는
 
1. 숫자든 문자든 중복을 없엔다.
2. 삽입하는 순서에 상관없이 정렬되서 입력이 된다.
 
이 특징을 모두 만족시킬 수 있는 자료구조는 이진트리 입니다.
 
즉, set은 벨런스 트리로 Red-Black 트리로 만들어져 있습니다.

출저 - https://hwan-shell.tistory.com/130

 
이진트리 특성상 삽입과 삭제가 용이합니다.
 
 
set을 사용하려면 #include<set>으로 <set> 헤더파일을 포함시켜야 합니다.

int main(void)
{
    int arr[13] = { 1,1,2,2,2,3,3,3,4,4,5,6,7 };
    set<int> s;
    for (int i = 0; i < 13; i++)
    {
        s.insert(arr[i]);
    }
    cout << "set s의 크기" << s.size() << endl;


    return 0;
}

 

 
해당 코드의 실행 결과는 위와 같습니다.
 
배열 arr의 원소 13개를 set에 집어넣었지만, set에는 7개의 원소 밖에 없습니다.
중복된 원소는 집어넣지 않기 때문입니다.
 
set은 배열처럼 s[3] 이런 식의 임의 접근(인덱스 접근)이 불가능합니다.
set을 순회하고 싶다면 다음과 iterator를 써서 접근해야 합니다.
 
 

    for (set<int>::iterator iter = s.begin(); iter != s.end(); iter++)
        cout << *iter << " ";

 

 
 

template <class Key,
	class Traits = less<Key>,
	class Allocator = allocator<Key>>
class set

 
매개 변수
 
Key
set에 저장되는 요소로, 데이터 형식입니다.
 
Traits
두 요소 값을 정렬 키로 비교하여 set에서
상대적인 순서를 결정할 수 있는 함수 개체를 제공하는 형식입니다.
이 인수는 선택 사항이며 이진 조건자는 less<Key> 기본 값입니다.
 
C++ 14 에서는 형식 매개 변수가 없는 조건자를 지정하여
std::less<>, std::greater<> 다른 유형의 조회를 사용하도록 설정할 수 있습니다.
자세한 내용은 결합 컨테이너에서 다른 유형의 조회를 참조해보자.
 
Allocator
set의 메모리 할당 및 할당 취소에 대한 세부 정보를 캡슐화하는
저장된 할당자 개체를 나타내는 형식입니다.
이 인수는 선택 사항이며 기본값은 allocator<Key>입니다.
 
 
그럼 이제 set의 구성 요소를 알아보았으니,
C++ 표준 라이브러리 set의 특성을 알아보자.
 

Set의 특성

C++ 표준 라이브러리 set의 특성은 다음과 같습니다.
 

• 연관된 키 값을 기준으로 하며 요소 값의 효율적인 검색을 지원하는
• 가변 크기 컨테이너인 연관 컨테이너 입니다.
• 또한 요소 값이 키 값이기 때문에 간단한 결합 컨테이너입니다.
• 이는 해당 요소에 액세스 할 수 있는
• 양방향 반복기를 제공하기 때문에 되돌릴 수 있습니다.
• 해당 요소가 컨테이너 내에서 지정된 비교 함수에 따라 키 값을 기준으로 정렬됩니다.
• 각각의 요소가 반드시 고유한 키를 가지고 있어야 한다는 점에서
• 고유성을 갖고 있습니다. set는 도한 간단한 연관 컨테이너이므로 해당 요소도 고유합니다.

 
set이 제공하는 기능은 제네릭이며, 요소로 포함된 특정 데이터 형식과
독립적이므로 클래스 템플릿으로도 설명합니다.
사용될 데이터 형식은 대신
비교 함수 및 할당자와 함께 클래스 템플릿에서 매개 변수로 지정됩니다.
 
++ Plus ++ 
set은 연관 컨테이너로
연관 컨테이너는 key와 value를 통해 관계있는 값을 묶어 저장하는 컨테이너입니다.
따라서 key와 value를 통해 요소에 빠른 접근은 가능하지만 연관 컨테이너는 자체적인 기준을 가지고
요소를 정렬하기 때문에 삽입되는 요소의 위치를 지정할 수 없습니다.
주로 균형 이진트리 혹은 해시 함수를 사용해 구현됩니다.
+++++++++
 
set의 컨테이너 형식은 일반적으로
애플리케이션에서 필요한 검색과 삽입의 형식을 기준으로 선택해야 합니다.
연관 컨테이너는 조회,삽입 및 제거 작업에 최적화되어 있습니다.
이러한 작업을 명시적으로 지원하는 멤버 함수는 효율적이며,
컨테이너의 요소 수 로그에 평균 비례하는 시간이 수행합니다.
요소를 삽입하면 반복기가 무효화되고
요소를 제거하면 제거된 요소를 가리키는 반복기만 무효화됩니다.
 
즉, 애플리케이션에서 값과 해당 키를 연결하는 조건을 만족할 경우
적절한 연관 컨테이너는 set입니다.
set의 요소는 고유하며 자체 정렬 키로 사용됩니다.
 
이 형식의 구조에 대한 모델은 정렬된 목록입니다.
예를 들어, 단어 내의 단어는 한 번만 나타날 수 있습니다.
단어의 여러 번 중복이 허용된 경우는 multiset이 적절한 컨테이너 구조입니다.
 
- 고유 키 단어 목록에 연결된 경우 이 데이터를 포함하기 위한 적절한 구조는 map
- 키가 고유하지 않으면 multimap이 선택한 컨테이너가 된다.
 
 
 
 
 
 
참고 사이트
cppreference.com

std::set<Key,Compare,Allocator>::emplace_hint - cppreference.com

learn_microsoft_cpp_set

set 클래스