C++의 세트 대 해시 세트

1. C++에서 Set 대 Hashset
2. C++로 설정
3. C++의 해시셋
4. C++에서 집합과 해시 집합의 주요 차이점
5. 결론

C++의 set은 데이터 요소를 저장하고 필요할 때마다 검색하는 컨테이너 역할을 합니다. 유사하게, 해시 세트, 보다 정확하게는 C++의 unordered_set은 데이터 요소를 저장하는 세트와 유사한 목적을 수행합니다.

이 기사에서는 set과 unordered_set에 대해 자세히 설명합니다.

C++에서 Set 대 Hashset

set은 데이터 요소를 저장하는 데 사용되는 연관 컨테이너인 반면 unordered_set은 미래의 요구 사항을 위해 데이터 요소를 저장하는 데 사용되는 연관 컨테이너이기도 합니다. 그렇다면 이 두 데이터 구조는 벡터, 지도 및 기타 컨테이너 객체와 어떻게 다릅니까?

답은 간단합니다. set 및 unordered_set은 고유한 데이터 요소를 저장합니다.

따라서 중복 요소를 허용하지 않습니다. 그러나 벡터 및 맵과 같은 다른 데이터 구조에서도 중복 요소를 저장할 수 있습니다.

이 두 데이터 구조는 모두 C++ 표준 템플릿 라이브러리에 있습니다.

이제 C++에서 set과 unordered_set을 언제 사용해야 하는지에 대해 간략하게 설명했으니 이제 자세히 알아보도록 하겠습니다.

C++로 설정

앞서 논의한 바와 같이 set은 고유한 데이터 요소를 정렬된 방식으로 저장하는 연관 컨테이너입니다. 그러나 임의의 순서로 저장할 수 있지만 set에서 검색하는 즉시 정렬된 방식으로만 요소를 반환합니다.

따라서 set에는 사용자로부터 숨겨진 데이터 요소를 정렬하기 위한 정의가 포함됩니다.

C++의 sets는 이진 검색 트리로 구현됩니다. 따라서 그들은 주문됩니다. 또한 요소를 검색하는 데 O(log n) 시간이 걸립니다.

C++에서 set을 구현하는 방법을 살펴보겠습니다.

#include <iostream>
#include <set>
using namespace std;

int main() {
  int a[] = {4, 8, 3, 6, 9, 8, 1, 3, 3};
  int size = sizeof(a) / sizeof(a[0]);
  set<int> s;
  for (int i = 0; i < size; i++) {
    s.insert(a[i]);
  }
  set<int>::iterator i;
  for (i = s.begin(); i != s.end(); i++) {
    cout << *i << " ";
  }
}

출력:

1 3 4 6 8 9

따라서 위의 코드 예제에서 볼 수 있듯이 배열에 저장된 요소는 임의의 순서이며 중복 요소를 포함합니다. 그러나 집합 s에 저장되자마자 내부적으로 정렬되고 중복 요소도 제거됩니다.

따라서 출력은 중복이 없는 정렬된 요소 그룹입니다.

C++의 해시셋

unordered_set 또는 C++의 hashset은 둘 다 같은 의미입니다. 이 unordered_set은 고유한 데이터 요소를 저장하는 데도 사용되지만 set과 unordered_set의 유일한 차이점은 unordered_set에는 set이 저장하는 동안 요소가 저장되는 순서가 없다는 것입니다. 요소를 정렬된 순서로

이 unordered_set도 중복 요소를 저장하지 않습니다. 그러나 해시 테이블을 사용하여 구현됩니다.

키라고도 하는 삽입될 요소는 해시 테이블의 인덱스에 해시되고 해당 특정 인덱스에 저장됩니다.

요소는 임의의 순서로 저장되기 때문에 검색하는 데 O(1) 시간이 걸리므로 검색 작업을 더 빠르게 구현할 수 있습니다.

C++에서 unordered_set을 사용하는 예를 살펴보겠습니다.

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
  int a[] = {4, 8, 3, 6, 9, 8, 1, 3, 3};
  int size = sizeof(a) / sizeof(a[0]);
  unordered_set<int> s;
  for (int i = 0; i < size; i++) {
    s.insert(a[i]);
  }
  unordered_set<int>::iterator i;
  for (i = s.begin(); i != s.end(); i++) {
    cout << *i << " ";
  }
}

출력:

1 9 6 3 8 4

따라서 위의 코드 예제에서 볼 수 있듯이 요소는 집합에서 임의의 순서로 저장됩니다. 그러나 집합에서 반환된 요소도 임의의 순서로 되어 있지만 모든 중복 요소를 제거하고 고유한 요소만 사용자에게 반환합니다.

C++에서 집합과 해시 집합의 주요 차이점

1. sets는 요소를 오름차순으로 저장하는 데 사용되는 반면 unordered_set은 요소를 순서 없이 저장합니다.
2. sets는 이진 검색 트리를 사용하여 구현되는 반면 unordered_set은 해시 테이블을 사용하여 구현됩니다.
3. set의 검색 작업은 요소를 검색하는 데 O(log n) 시간이 걸리는 반면 unordered_set의 요소를 검색하는 데 O(1) 시간이 걸립니다.
4. sets는 #include<set> 헤더 파일에 포함되는 반면 unordered_set은 #include<unordered_set> 헤더 파일을 사용하여 포함됩니다.

결론

이 기사에서 우리는 C++의 set과 hashset에 대해 논의했습니다. 이 두 데이터 구조는 모두 C++ STL에 있으며 고유한 데이터 요소를 저장하는 데 사용됩니다.

그러나 둘 사이의 주요 차이점은 set은 정렬된 요소 집합을 반환하는 반면 unordered_set은 데이터 요소를 순서 없이 반환한다는 것입니다.

둘 중 하나를 사용할 수 있지만 unordered_set에서는 검색 작업이 더 빠르며 요소를 검색하는 데 거의 일정한 시간이 소요되므로 선호됩니다.