c++ set unordered_set区别

爱被打了一巴掌 2022-05-14 10:56 220阅读 0赞

`c++ std`中`set`与`unordered_set`区别和`map`与`unordered_map`区别类似：

1.  `set`基于红黑树实现，红黑树具有**自动排序的功能**，因此map内部所有的数据，在任何时候，都是有序的。
2.  `unordered_set`基于哈希表，数据插入和查找的时间复杂度很低，几乎是常数时间，而代价是消耗比较多的内存，**无自动排序功能**。底层实现上，使用一个下标范围比较大的数组来存储元素，形成很多的桶，利用`hash`函数对`key`进行映射到不同区域进行保存。

更详细的区别，如下图：

![这里写图片描述][70]

见 [stackoverflow][] .

##### 示例: #####

`set`:  
Input : 1, 8, 2, 5, 3, 9  
Output : 1, 2, 3, 5, 8, 9

`Unordered_set`:  
Input : 1, 8, 2, 5, 3, 9  
Output : 9 3 1 8 2 5 (顺序依赖于 hash function)

**下面在给出一个以`vector<int>`为`key`的示例，对比下`set`与`unordered_set`：**

set<vector<int>> 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

因为`vector` 重载了 `operator<`，因此可以作为`set`的`key`.

但是如果直接使用`unordered_set<vector<int>> s`;则报错，因为`vector`没有`hash` 函数，需要自己定义一个，可以定义一个类型下面这样的`hash`函数：

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;
        }
    };

接下来这样使用：

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

或者模板特化`struct hash<std::vector<int>>`

namespace std {
        template<>
        struct hash<std::vector<int>> {
            size_t operator()(const 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;
            }
        };
    }
    
    // usage example
    void test_unordered_set(){
        unordered_set<std::vector<int>> s;
        s.insert({
       1, 2});
        s.insert({
       1, 3});
        s.insert({
       1, 2});
        for(const auto& vec:s)
            cout<<vec<<endl;
        //    1 3
        //    1 2
    
        std::hash<int> hasher;
        cout<<"hasher(99): "<<hasher(99)<<" ,hasher(77): "<<hasher(77)<<endl;
        // hasher(99): 99 ,hasher(77): 77
    }

我的博客即将搬运同步至腾讯云+社区，邀请大家一同入驻：[https://cloud.tencent.com/developer/support-plan?invite\_code=3ez16n7773c48][https_cloud.tencent.com_developer_support-plan_invite_code_3ez16n7773c48]

参考：  
[https://www.geeksforgeeks.org/set-vs-unordered\_set-c-stl/][https_www.geeksforgeeks.org_set-vs-unordered_set-c-stl]  
[https://stackoverflow.com/a/52203931/6329006][stackoverflow]  
[https://stackoverflow.com/a/29855973/6329006][https_stackoverflow.com_a_29855973_6329006]

[STL map, hash\_map ， unordered\_map区别、对比][STL map_ hash_map _ unordered_map]

[70]: /images/20220514/5aec121b21844f5a837398215fa0f85e.png
[stackoverflow]: https://stackoverflow.com/a/52203931/6329006
[https_cloud.tencent.com_developer_support-plan_invite_code_3ez16n7773c48]: https://cloud.tencent.com/developer/support-plan?invite_code=3ez16n7773c48
[https_www.geeksforgeeks.org_set-vs-unordered_set-c-stl]: https://www.geeksforgeeks.org/set-vs-unordered_set-c-stl/
[https_stackoverflow.com_a_29855973_6329006]: https://stackoverflow.com/a/29855973/6329006
[STL map_ hash_map _ unordered_map]: https://blog.csdn.net/haluoluo211/article/details/80877558