某日二師兄參加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++！（狗頭）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/556223.html
標籤：其他
下一篇：返回列表