왜 누군가가 unorder_set 대신 set을 사용합니까?

왜 누군가가 unorder_set 대신 set을 사용합니까?

---

C ++ 0x는 다른 곳에서도 unordered_set사용할 수있는 것을 소개 boost합니다. 내가 이해하는 unordered_set것은 O(1)조회 복잡도 가있는 해시 테이블입니다 . 반면에 조회 복잡성이 set있는 나무 log(n)일뿐입니다. 왜 지구상에서 누군가 set대신에 사용 unordered_set하겠습니까? 즉 set더 이상 필요 합니까?

---

세트의 항목을 반복하려는 사람의 경우 순서가 중요합니다.

---

정렬되지 않은 세트는 몇 가지 방법으로 O (1) 평균 액세스 시간을 지불해야합니다.

• set사용 적은 메모리 보다 unordered_set같은 수의 요소를 저장하도록한다.
• A의 원소의 소수 , A의 조회를 set할 수있는 빠른 에서 조회보다 unordered_set.
• 많은 작업이 빠르게에서 비록 평균 경우 에 unordered_set, 그들은 종종이 보장되는 더 나은 최악의 복잡성을 위해 set(예를 들어 insert).
• 그건 set 종류의 요소는 당신이 순서에 액세스 그들에게 원하는 경우 유용합니다.
• 당신은 할 수 사전 식 비교 다른 set과들 <, <=, >과 >=. unordered_set이러한 작업을 지원할 필요는 없습니다.

---

해시 테이블보다 트리를 선호 할 때마다.

예를 들어, 해시 테이블은 최악의 경우 "O (n)"입니다. O (1)이 평균 사례입니다. 나무는 최악의 경우 "O ( log n)"입니다.

---

std :: set은 Standard C ++의 일부이고 unorder_set은 그렇지 않기 때문입니다. C ++ 0x는 표준이 아니며 Boost도 아닙니다. 우리 중 많은 사람들에게 이식성은 필수적이며 이는 표준을 고수한다는 의미입니다.

---

스위프 라인 알고리즘을 고려하십시오. 이 알고리즘은 해시 테이블에서 완전히 실패하지만 균형 트리에서 아름답게 작동합니다. 스위프 라인 알고리즘의 구체적인 예를 제공하려면 fortune의 알고리즘을 고려하십시오. http://en.wikipedia.org/wiki/Fortune%27s_algorithm

---

다음과 같은 경우에 세트를 사용하십시오.

1. 우리는 순서가 지정된 데이터 (명확한 요소)가 필요합니다.
2. 데이터를 인쇄 / 액세스해야합니다 (정렬 된 순서로).
3. 우리는 요소의 선임자 / 후임자가 필요합니다.

다음 경우에 unorder_set을 사용하십시오.

1. 고유 한 요소 집합을 유지해야하며 순서가 필요하지 않습니다.
2. 단일 요소 액세스가 필요합니다. 즉 순회가 없습니다.

예 :

세트:

입력 : 1, 8, 2, 5, 3, 9

출력 : 1, 2, 3, 5, 8, 9

정렬되지 않은 _ 세트 :

입력 : 1, 8, 2, 5, 3, 9

출력 : 9 3 1 8 2 5 (이 순서는 해시 함수의 영향을 받음)

주로 차이점 :

참고 : 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://www.geeksforgeeks.org/set-vs-unordered_set-c-stl/ https://stackoverflow.com/a/29855973/6329006

---

One more thing, in addition to what other people already mentioned. While the expected amortized complexity for inserting an element to an unordered_set is O(1), every now and then it will take O(n) because the hash-table needs to be restructured (the number of buckets needs to change) - even with a 'good' hash function. Just like inserting an element in a vector takes O(n) every now and then because the underlying array needs to be reallocated.

Inserting in a set always takes at most O(log n). This might be preferable in some applications.

---

Pardon me, one more thing worth noticing about the sorted property:

If you want a range of data in container, for example: You stored time in set, and you want time from 2013-01-01 to 2014-01-01.

For unordered_set it is impossible.

Of course, this example would be more convincing for usage cases between map and unordered_map.

---

Off hand, I would say it is convenient to have things in a relationship if you're looking to convert it into a different format.

It is also possible that whilst one is faster to access, the time to build the index or the memory used when creating and/or accessing it is greater.

---

If you want to have things sorted, then you would use set instead of unordered_set. unordered_set is used over set when ordering stored does not matter.

---

g++ 6.4 stdlibc++ ordered vs unordered set benchmark

I benchmarked this dominant Linux C++ implementation to see the difference:

The full benchmark details and analysis have been given at: What is the underlying data structure of a STL set in C++? and I will not repeat them here.

"BST" means "tested with std::set and "hash map" means "tested with std::unordered_set. "Heap" is for std::priority_queue which I analyzed at: Heap vs Binary Search Tree (BST)

As a quick summary:

• the graph clearly shows that under these conditions, hashmap insertion were always a lot faster when there are more than 100k items, and the difference grows as the number of items increases

  The cost of this speed boost is that you are not able to efficiently traverse in order.

• 곡선은 순서 std::set가 BST 기반이며 std::unordered_set해시 맵 기반 임을 분명히 나타냅니다 . 참조 답변에서 GDB 단계를 통해 코드를 디버깅한다는 것을 추가로 확인했습니다.

mapvs에 대한 비슷한 질문 unordered_map: 사소한 키의 경우 unorder_map보다 map을 사용하는 이점이 있습니까?

참고 URL : https://stackoverflow.com/questions/1349734/why-would-anyone-use-set-instead-of-unorder-set