面试官:知道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值,同时还要告诉编译器如何判断两个自定义类型的对象是否相等。以下代码无法通过编译:
二师兄:此时需要为Foo类型实现bool operator==(const Foo& o) const函数和size_t operator()(const Foo& f) const仿函数,才能通过编译:
二师兄:当然我们也可以使用std::function或者lambda来代替仿函数,目的都是为了使得编译器知道如何计算自定义类型的哈希值。对于今天面试官的表现,小伙伴们能给几分呢?不是面试官要放水,面完set/map之后再面unordered_set/unordered_map,真的没有那么多好问题,因为两者太像了。。。
面试官:用过unordered_multiset/unordered_multimap吗?
二师兄:没用过。但是应该和multiset/multimap类似,只是底层也采用hash表实现。
面试官:好的,今天的面试就结束了,请回去等消息吧。
关注我,带你21天“精通”C++!(狗头)
欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) | Powered by Discuz! X3.4 |