某日二師兄參加XXX科技公司的C++工程師開發崗位第27面： > 面試官：知道`std::unordered_set/std::unordered_map`嗎？ > > 二師兄：知道。兩者都是C++11引入的新容器，和`std::set`和`std::map`功能類似，`key`唯一，`unorde ...
某日二師兄參加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++！（狗頭）
