主题:C++面试八股文:用过std::set/std::map吗
某日二师兄参加XXX科技公司的C++工程师开发岗位第27面:
[mw_shl_code=cpp,true]#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;
}[/mw_shl_code]
[mw_shl_code=cpp,true]struct Comp
{
bool operator()(const Foo& lhs, const Foo& rhs) const
{
return lhs.val > rhs.val;
}
};
std::set<Foo,Comp> iset;[/mw_shl_code]
[mw_shl_code=cpp,true]#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;
}[/mw_shl_code]
让我们看看最后一个问题:
单纯的查询而言,是vector快还是map快?
这里二师兄的是标准答案,实际上当数据量特别大的时候,的确map是更好的选择。
但当数据量没那么大的时候(少于1000条记录),vector要比map查询速度快。原因我们在之前的面试文章中讲过,vector内存连续,缓存更友好。map底层是红黑树,内存并不连续。
当数据量小的时候,算法的优势没有抵消缓存的劣势,所以vector在数据量小的时候更胜一筹。
“纸上得来终觉浅,绝知此事要躬行”。小伙伴们,一起努力吧!