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