C ++에서 set과 unordered_set의 차이점은 무엇입니까?

C ++에서 set과 unordered_set의 차이점은 무엇입니까?

---

이 좋은 질문을 보았습니다.이 질문은 비슷하지만 전혀 동일하지는 않습니다. 이것은 접근 자 / 뮤 테이터가 동기화되어 있기 때문에 해시 테이블 구현이 다른 Java에 대해 이야기하기 때문에 HashMap과 Hashtable의 차이점은 무엇입니까?

그래서 C ++에서 set과 unordered_set 구현의 차이점은 무엇입니까? 이 질문은 당연히 다른 C ++ 컨테이너에 대해 map vs unordered_map 등으로 확장 될 수 있습니다.

다음은 내 초기 평가입니다.

set : 표준은 명시 적으로 트리로 구현하도록 요청하지 않지만, 찾기 / 삽입을위한 작업에 대한 시간 복잡성 제약 조건은 항상 트리로 구현됨을 의미합니다. 일반적으로 높이 균형이 잡힌 RB 트리 (GCC 4.8에서 볼 수 있음)입니다. 높이가 균형을 이루기 때문에 find ()에 대해 예측 가능한 시간 복잡성이 있습니다.

장점 : 콤팩트 (다른 ​​DS와 비교)

단점 : 액세스 시간 복잡도는 O (lg n)

unorder_set : 표준은 명시 적으로 트리로 구현하도록 요청하지 않지만, 찾기 / 삽입 작업에 대한 시간 복잡도 제약 조건은 항상 해시 테이블로 구현됨을 의미합니다.

장점 :

1. 더 빠름 (검색을 위해 상각 된 O (1) 약속)
2. tree-DS에 비해 기본 프리미티브를 스레드로부터 안전한 것으로 쉽게 변환

단점 :

1. O가 보장되지 않는 조회 (1) 이론상 최악의 경우는 O (n)입니다.
2. 나무만큼 콤팩트하지 않습니다. (실용 상 부하 계수는 1이 아닙니다)

참고 : 해시 테이블에 대한 O (1)은 충돌이 없다는 가정에서 비롯됩니다. 부하 계수가 .5 인 경우에도 매초마다 변수가 삽입되면 충돌이 발생합니다. 해시 테이블의로드 팩터는 해당 요소에 액세스하는 데 필요한 작업 수에 반비례한다는 것을 알 수 있습니다. 더 많은 작업, 희소 해시 테이블을 줄입니다. 저장된 요소의 크기가 포인터와 비슷한 경우 오버 헤드가 상당히 큽니다.

편집 : 대부분의 질문에 충분한 답변이 포함되어 있기 때문에 질문을 "성능 분석을위한 맵 / 세트 간의 차이점을 놓쳤습니까?"로 변경하고 있습니다.

---

나는 당신이 일반적으로 자신의 질문에 대답했다고 생각합니다.

나무만큼 콤팩트하지 않습니다. (실용 상 부하 계수는 1이 아닙니다)

반드시 사실은 아닙니다. 유형에 대한 트리의 각 노드 (빨강-검정 트리라고 가정) T는 최소한 2 * pointer_size + sizeof(T) + sizeof(bool). 이는 3 * pointer size트리가 parent각 트리 노드에 대한 포인터를 포함하는지 여부에 따라 달라질 수 있습니다 .

이것을 해시 맵과 비교하십시오 load factor < 1. 당신이 말했듯이 각 해시 맵에 대해 낭비되는 배열 공간이 있습니다 . 그러나 해시 맵이 연결을 위해 단일 연결 목록을 사용한다고 가정하면 (실제로는 그렇지 않을 이유가 없습니다) 삽입 된 각 요소는 sizeof(T) + pointer size.

이 분석은 정렬에 사용되는 추가 공간에서 발생할 수있는 모든 오버 헤드를 무시합니다.

T크기가 작은 요소 (기본 유형)의 경우 포인터의 크기와 기타 오버 헤드가 지배적입니다. > 0.5예를 들어 로드 팩터에서는 std::unordered_set실제로 동등한 것보다 적은 메모리를 사용할 수 있습니다 std::set.

또 다른 큰 빠진 점은 a를 통해 반복 std::set하면 주어진 비교 함수를 기반으로 가장 작은 std::unordered_set것부터 가장 큰 순서로 순서가 보장 된다는 사실입니다.를 반복 하면 "무작위"순서로 값이 반환됩니다.

---

또 다른 차이점은 (성능과 관련이 없지만) set삽입은 반복자를 무효화하지 않는 반면 unordered_set삽입은 재해시를 트리거 할 수 있다는 것입니다. 실제로는 실제 요소에 대한 참조가 유효하기 때문에 매우 사소한 문제입니다.

---

Yuushi는 이미 공간 효율성 및 기타 사항을 잘 다루고 있습니다. 제가 언급 할 질문의 몇 가지 다른 부분 ...

해시 테이블에 대한 O (1)은 충돌이 없다는 가정에서 비롯됩니다.

그건 사실이 아니야. O (1)이 의미하는 바는 첫 번째 조회 시도가 항상 성공한다는 것이 아니라 값의 수가 증가함에 따라 증가하는 것이 아니라 평균적으로 일정한 횟수의 시도가 필요하다는 것입니다. 예를 들어, unordered_set또는 ... _map를 사용하면 구성 max_load_factor시 기본값이 1.0으로 설정되고, 좋은 해시 함수를 사용하여 부하 계수가 이에 가까워지면 하나의 버킷에 해시 되는 평균 요소 수는 값 수에 관계없이 약 2 개가됩니다. 테이블에.

부하 계수가 .5 인 경우에도 매초마다 변수가 삽입되면 충돌이 발생합니다.

사실이지만 직관적으로 예상하는 것만 큼 심각하지는 않습니다. 1.0로드 팩터에서 평균 체인 길이가 2 인 것은 나쁘지 않습니다.

해시 테이블의로드 팩터는 해당 요소에 액세스하는 데 필요한 작업 수에 반비례한다는 것을 알 수 있습니다. 더 많은 작업, 희소 해시 테이블을 줄입니다.

확실히 상관 관계가 있습니다 (역이 아닙니다).

---

어떤 경우 set에는 더 편리합니다.

예를 들어 vector키로 사용 :

set<vector<int>> s;
s.insert({1, 2});
s.insert({1, 3});
s.insert({1, 2});

for(const auto& vec:s)
    cout<<vec<<endl;   // I have override << for vector
// 1 2
// 1 3 

그 이유는 그 이유 vector<int>에있을 수 set있기 때문에 vector무시 operator<.

그러나 사용하는 경우 벡터에 해시 함수가 없기 때문에에 unordered_set<vector<int>>대한 해시 함수를 만들어야 vector<int>하므로 다음과 같이 정의해야합니다.

struct VectorHash {
    size_t operator()(const std::vector<int>& v) const {
        std::hash<int> hasher;
        size_t seed = 0;
        for (int i : v) {
            seed ^= hasher(i) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }
        return seed;
    }
};

vector<vector<int>> two(){
    //unordered_set<vector<int>> s; // error vector<int> doesn't  have hash function
    unordered_set<vector<int>, VectorHash> s;
    s.insert({1, 2});
    s.insert({1, 3});
    s.insert({1, 2});

    for(const auto& vec:s)
        cout<<vec<<endl;
    // 1 2
    // 1 3
}

어떤 경우 unordered_set에는 더 복잡 하다는 것을 알 수 있습니다 .

Mainly cited from: https://stackoverflow.com/a/29855973/6329006

More difference between unordered_set and set see this: https://stackoverflow.com/a/52203931/6329006

ReferenceURL : https://stackoverflow.com/questions/16075890/what-is-the-difference-between-set-and-unordered-set-in-c