C++ STL의 집합과 해시 집합의 차이점은 무엇입니까?

Question

언제 다른 하나를 선택해야합니까? 올바른 STL 컨테이너를 사용하기 위해 권장할만한 포인터가 있습니까?

Answer 1

hash_set은 C++ 표준의 일부가 아닌 확장입니다. 조회는 set에 대한 O (log n)보다는 O (1)이어야하므로 대부분의 경우 더 빠릅니다.

컨테이너를 반복 할 때 또 다른 차이점이 나타납니다. set은 내용을 정렬 된 순서로 전달하며, hash_set은 기본적으로 무작위입니다 (Lou Franco에게 감사드립니다).

편집 : C++ 표준 업데이트는 hash_set 대신에 unordered_set을 사용해야합니다. 성능은 유사하며 표준에 의해 보장됩니다. 이름에서 "정렬되지 않음"은 특정 순서없이 결과를 생성한다는 점을 강조합니다.

Answer 2

hash_set은 대부분 O (1) 연산을 사용하는 해시 테이블로 구현되지만 집합은 O (log n)을 갖는 일종의 트리 (AVL, 빨강 검정 등) 작업을 수행하지만 정렬 된 순서로 수행됩니다.

편집 : 나는 그 나무가 O (n)라고 썼다. 그건 완전히 잘못되었습니다.

Answer 3

stl::set은 2 진 검색 트리로 구현됩니다. hashset은 해시 테이블로 구현됩니다.

여기서 중요한 문제는 stl::set이 O (1)의 조회가있는 해시 테이블이라고 생각한다는 것입니다. O (1)은 아니며 갖고 있지도 않습니다. 룩업을위한 O (log (n))를 가지고 있습니다. 그 다음에는 이진 트리와 해시 테이블에 대해 읽은 다음 데이터 구조를 더 잘 이해할 수 있습니다.

Answer 4

hash_set을 사용하면 hash_set을 사용하여 해시 함수를 제공해야하지만 집합에는 정의하기 쉽고 네이티브 형식에 대해 미리 정의 된 비교 함수 ('<') 만 필요합니다.

Answer 5

아무도 아직 질문의 다른 부분에 답변을했다고 생각하지 않습니다.

hash_set 또는 unordered_set을 사용하는 이유는 일반적으로 O (1) 조회 시간입니다. 일반적으로 구현에 따라 해시를 더 큰 해시 배열에 복사해야하거나 해시 버킷에 수천 개의 항목이 포함될 수 있기 때문에 일반적으로 말합니다.

집합을 사용하는 이유는 집합의 가장 큰 또는 가장 작은 구성원이 필요한 경우가 많기 때문입니다. 해시에는 순서가 없으므로 가장 작은 항목을 빨리 찾을 방법이 없습니다. 나무는 순서가 있으므로 가장 크거나 작은 나무는 매우 빠릅니다. O (log n), 끝점에 대한 포인터를 보유하고 있다면 O (1).