某日二师兄参加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
在数据量小的时候更胜一筹。
“纸上得来终觉浅,绝知此事要躬行”。小伙伴们,一起努力吧!
标签:std,map,面试官,set,const,key,师兄 From: https://blog.51cto.com/binarch/6568064关注我,带你21天“精通”C++!(狗头)