某日二師兄參加XXX科技公司的C++工程師開發崗位第27面： > 面試官：用過`std::set/std::map`嗎？ > > 二師兄：用過。 > > 面試官：能介紹一下二者嗎？ > > 二師兄：`std::set`是一個有序的集合，其中的元素是唯一的，即每個元素只能出現一次。一般用於去重和自動排 ...
某日二師兄參加XXX科技公司的C++工程師開發崗位第27面：
面試官：用過
std::set/std::map嗎？二師兄：用過。
面試官：能介紹一下二者嗎？
二師兄：
std::set是一個有序的集合，其中的元素是唯一的，即每個元素只能出現一次。一般用於去重和自動排序。二師兄：
std::map同樣是有序組合，只不過它不止有key，每個key還對用一個value。其中key是唯一，不可重覆，但是value卻沒有限制。key/value也被稱為鍵值對。面試官：知道他們底層使用什麼數據結構存儲數據的嗎？
二師兄：兩者都是使用紅黑樹作為底層的數據結構。紅黑樹是一種自動平衡的二叉樹，它確保插入、刪除和查找操作的時間複雜度都是
O(log n)。面試官：
set/map對於key的類型有什麼要求嗎？二師兄：因為
set/map被稱為有序容器，所以對插入進去的key有排序的要求。一般需要為類型實現<比較方法，以下代碼無法通過編譯：
#include <iostream>
#include <set>
struct Foo
{
Foo(int v):val(v){}
int val;
};
int main(int argc, char const *argv[])
{
std::set<Foo> iset;
iset.insert(Foo(1024));
iset.insert(Foo(42));
for(auto it = iset.begin(); it != iset.end(); ++it)
{
std::cout << it->val << std::endl;
}
return 0;
}
二師兄：此時需要為
Foo類型實現bool operator<(const T&, const T&)函數，才能通過編譯：
bool operator<(const Foo& lhs,const Foo& rhs) {return lhs.val < rhs.val;}
面試官：按照你的方法，可以實現從小到大的排序。如何實現從大到小的排序？
二師兄：
set/map類模板的第二個模板參數可以傳入比較類型，預設比較類型是std::less<_Key>，我們可以傳入std::greater<T>，此時需要實現bool operator>(const T&, const T&)函數。二師兄：還有一種方法是手寫一個仿函數，重載
bool operator()(const T, const T) const函數用於比較兩者的大小：
struct Comp
{
bool operator()(const Foo& lhs, const Foo& rhs) const
{
return lhs.val > rhs.val;
}
};
std::set<Foo,Comp> iset;
面試官：可以修改
map中的key嗎？二師兄：不可以。因為
map中的key是const的。強制修改（取地址，const_cast轉非const指針，解引用賦值）會造未知的錯誤。面試官：當
map中不存在某個key時，對map使用map[key]操作會有什麼後果？二師兄：會在
map中增加一個鍵值對，鍵名為key，值是傳入的value類型的預設值。面試官：如果不希望刪除重覆的
key，有什麼辦法？二師兄：STL中提供了
std::multiset和std::multimap兩個容器，可以存入key相同的多個元素。面試官：在
std::multimap中如何通過key查找value？二師兄：
multimap提供了equal_range方法，此方法返回一個pair，分別對應2個迭代器。通過迴圈迭代器來獲取key對應的所有value。
#include <iostream>
#include <map>
int main() {
std::multimap<int, std::string> mmap;
mmap.insert(std::make_pair(1, "1"));
mmap.insert(std::make_pair(2, "2"));
mmap.insert(std::make_pair(3, "3"));
mmap.insert(std::make_pair(1, "1"));
auto range = mmap.equal_range(1);
for (auto it = range.first; it != range.second; ++it) {
std::cout << it->second << std::endl;
}
return 0;
}
面試官：最後一個問題，你覺得單純的查詢而言，是
vector快還是map快？二師兄：當然是
map快，因為vector的查詢的時間複雜度是O(n)，而map是O(logn)。面試官：好的，今天面試結束了，回去等通知吧。
讓我們看看最後一個問題：
單純的查詢而言，是
vector快還是map快？
這裡二師兄的是標準答案，實際上當數據量特別大的時候，的確map是更好的選擇。
但當數據量沒那麼大的時候（少於1000條記錄），vector要比map查詢速度快。原因我們在之前的面試文章中講過，vector記憶體連續，緩存更友好。map底層是紅黑樹，記憶體並不連續。
當數據量小的時候，演算法的優勢沒有抵消緩存的劣勢，所以vector在數據量小的時候更勝一籌。
“紙上得來終覺淺，絕知此事要躬行”。小伙伴們，一起努力吧！
關註我，帶你21天“精通”C++！（狗頭）
