乐趣区

关于c++:C面试八股文知道stdunorderedsetstdunorderedmap吗

jiezi

某日二师兄加入 XXX 科技公司的 C ++ 工程师开发岗位第 27 面：

面试官：晓得 std::unordered_set/std::unordered_map 吗？

二师兄：晓得。两者都是 C ++11 引入的新容器，和 std::set 和std::map性能相似，key惟一，unordered_map的 value 可变。

二师兄：不同于 set/map，unordered_set/unordered_map 都是无序容器。

面试官：那你晓得它们底层怎么实现的吗？

二师兄：两者底层应用哈希表实现，因而插入、删除和查找操作的均匀工夫复杂度为常数工夫O(1)。

面试官：既然均匀复杂度是 O(1)，那么是不是能够取代set 和map了？

二师兄：这里是均匀的工夫复杂度。哈希表插入、删除和查找操作的最差工夫复杂度是 O(n)，要比set/map 的O(log n)大。

面试官：那你感觉哪些场景适宜set/map，哪些场景适宜unordered_set/unordered_map？

二师兄：set/map实用于须要有序存储和疾速查找的场景，而 unordered_set/unordered_map 实用于须要疾速插入和查找的场景。

面试官：unordered_set/unordered_map对于 key 的类型有什么要求吗？

二师兄：因为 unordered_set/unordered_map 底层采纳哈希表，所以在应用自定义类型作为 key 的时候，须要通知编译器如何计算此类型的 hash 值，同时还要通知编译器如何判断两个自定义类型的对象是否相等。以下代码无奈通过编译：

#include <iostream>
#include <unordered_set>
struct Foo
{
    std::string str;
    int val;
};
int main(int argc, char const *argv[])
{
    std::unordered_set<Foo> uset;
    uset.insert({"42",42});
    uset.insert({"1024",1024});
    return 0;
}

二师兄：此时须要为 Foo 类型实现 bool operator==(const Foo& o) const 函数和 size_t operator()(const Foo& f) const 仿函数，能力通过编译：

#include <iostream>
#include <unordered_set>
struct Foo
{
    std::string str;
    int val;
    bool operator==(const Foo& o) const
    {return str == o.str && val == o.val;}
};
struct Hash
{size_t operator()(const Foo& f) const
    {return std::hash<std::string>()(f.str) ^ std::hash<int>()(f.val);
    }
};
int main(int argc, char const *argv[])
{
    std::unordered_set<Foo,Hash> uset;
    uset.insert({"42",42});
    uset.insert({"1024",1024});
    return 0;
}

二师兄：当然咱们也能够应用 std::function 或者 lambda 来代替仿函数，目标都是为了使得编译器晓得如何计算自定义类型的哈希值。

面试官：用过 unordered_multiset/unordered_multimap 吗？

二师兄：没用过。然而应该和 multiset/multimap 相似，只是底层也采纳 hash 表实现。

面试官：好的，明天的面试就完结了，请回去等音讯吧。

对于明天面试官的体现，小伙伴们能给几分呢？不是面试官要放水，面完 set/map 之后再面unordered_set/unordered_map，真的没有那么多好问题，因为两者太像了。。。

好了，明天的面试到这里就完结了，让咱们期待今天面试官的体现吧~

关注我，带你 21 天“精通”C++！（狗头）

退出移动版