V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
csfreshman
V2EX  ›  程序员

请教 stl 中 unordered_set 使用问题

  •  
  •   csfreshman · 2021-05-04 00:14:30 +08:00 · 1496 次点击
    这是一个创建于 1289 天前的主题,其中的信息可能已经有所发展或是发生改变。

    完整可编译代码:

    #include <set>
    #include <vector>
    #include <iostream>
    #include <unordered_set>
    
    using namespace std;
    
    int main()
    {
        vector<int> ans;
        set<vector<int>> res;
        //unordered_set<vector<int>> foo;
        return 0;
    }
    

    如果放开注释会报错,看了 unordered_set,实在没发现哪里有问题?

    发现原因: 刷 leetcode 时使用 set 去重结果,想到之前看到一篇文章(如果有错欢迎纠正):map unordered_map,map 插入元素自动排序,底层实现是红黑树,而 unordered_map 底层实现则时哈希表,可以用来去重,这里我类比到 set,想优化一下,发现编译报错。

    ####end 感谢各位指点

    10 条回复    2021-05-07 23:30:57 +08:00
    csfreshman
        1
    csfreshman  
    OP
       2021-05-04 00:15:47 +08:00
    换了个 docker 编译,加上-std=c++17 编译通过了…………
    codyfeng
        2
    codyfeng  
       2021-05-04 08:14:58 +08:00 via Android
    unordered_set 应该要求元素有 hash,在 https://en.cppreference.com/w/cpp/utility/hash 没有看到 std::hash<std::vector<int>>的 specialization 。

    表示很好奇为何加上-std=c++17 编译通过
    caokeck
        3
    caokeck  
       2021-05-04 08:53:00 +08:00
    同好奇,我这里开 C++17 也并不能编译通过
    csfreshman
        4
    csfreshman  
    OP
       2021-05-04 10:24:28 +08:00
    @codyfeng @caokeck 好奇的人又多了两个,昨天刷题想把 set 改成 unordered_set 加快速度,发现过不了,本地 docker 环境下升级了 gcc 添加 c++17 就可以通过的,力扣和 leetcode.com 上都编不过……
    sunznx
        5
    sunznx  
       2021-05-04 10:58:26 +08:00
    不是 `unordered_set<int> foo;` 吗
    mingl0280
        6
    mingl0280  
       2021-05-04 13:14:05 +08:00 via Android   ❤️ 1
    unordered_set 内的元素不能被修改,你加了--std=c++17 可能是你容器里的环境有方言……
    BrettD
        7
    BrettD  
       2021-05-05 01:01:37 +08:00 via iPhone
    你容器里的编译器是什么版本
    changnet
        8
    changnet  
       2021-05-05 11:25:48 +08:00
    ```cpp
    struct MyHash
    {
    std::size_t operator()(vector<int>& v) const
    {
    return 1;
    }
    };
    unordered_set<vector<int>, MyHash> foo;
    ```
    `vector<int>`是一个自定义的类型,默认没有 hash 函数,没有 equal 函数,需要自己定义。没定义它就会提示你`use
    of delete function ... unordered_set() = default`,意思是这个无参的默认构建已经被标记为 delete 状态,不允许使用
    yulon
        9
    yulon  
       2021-05-05 17:59:01 +08:00
    惊了,你把 set 当啥用了,为什么会塞 vector 进去,难道查找的时候还要用 vector 去查吗?

    set 就是没有 value 只有 key 的 map,或者说 value & key 一体,是用来快速确认某个数据是否存在的。

    你如果是要一个可以遍历的容器,直接用 vector 、list 之类的。
    csfreshman
        10
    csfreshman  
    OP
       2021-05-07 23:30:57 +08:00
    @yulon 力扣官方题给的答案这么写的……,我很无辜呀老铁。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1061 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 51ms · UTC 20:02 · PVG 04:02 · LAX 12:02 · JFK 15:02
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.