某日二师兄参加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
#include
struct Foo
{
std::string str;
int val;
};
int main(int argc, char const *argv[])
{
std::unordered_set 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
#include
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()(f.str) ^ std::hash()(f.val);
}
};
int main(int argc, char const *argv[])
{
std::unordered_set 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++!(狗头)
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net