ToB企服应用市场:ToB评测及商务社交产业平台

标题: C++面试八股文：知道std::unordered_set/std::unordered_map吗？ [打印本页]
作者: 钜形不锈钢水箱    时间: 2023-6-28 22:07
标题: C++面试八股文：知道std::unordered_set/std::unordered_map吗？
某日二师兄参加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值，同时还要告诉编译器如何判断两个自定义类型的对象是否相等。以下代码无法通过编译：
  1. #include <iostream>
  2. #include <unordered_set>
  3. struct Foo
  4. {
  5.     std::string str;
  6.     int val;
  7. };
  8. int main(int argc, char const *argv[])
  9. {
  10.     std::unordered_set<Foo> uset;
  11.     uset.insert({"42",42});
  12.     uset.insert({"1024",1024});
  13.     return 0;
  14. }
复制代码
二师兄：此时需要为Foo类型实现bool operator==(const Foo& o) const函数和size_t operator()(const Foo& f) const仿函数，才能通过编译：
  1. #include <iostream>
  2. #include <unordered_set>
  3. struct Foo
  4. {
  5.     std::string str;
  6.     int val;
  7.     bool operator==(const Foo& o) const
  8.     {
  9.         return str == o.str && val == o.val;
  10.     }
  11. };
  12. struct Hash
  13. {
  14.     size_t operator()(const Foo& f) const
  15.     {
  16.         return std::hash<std::string>()(f.str) ^ std::hash<int>()(f.val);
  17.     }
  18. };
  19. int main(int argc, char const *argv[])
  20. {
  21.     std::unordered_set<Foo,Hash> uset;
  22.     uset.insert({"42",42});
  23.     uset.insert({"1024",1024});
  24.     return 0;
  25. }
复制代码
二师兄：当然我们也可以使用std::function或者lambda来代替仿函数，目的都是为了使得编译器知道如何计算自定义类型的哈希值。
面试官：用过unordered_multiset/unordered_multimap吗？
二师兄：没用过。但是应该和multiset/multimap类似，只是底层也采用hash表实现。
面试官：好的，今天的面试就结束了，请回去等消息吧。
对于今天面试官的表现，小伙伴们能给几分呢？不是面试官要放水，面完set/map之后再面unordered_set/unordered_map，真的没有那么多好问题，因为两者太像了。。。
好了，今天的面试到这里就结束了，让我们期待明天面试官的表现吧~
关注我，带你21天“精通”C++！（狗头）

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4