经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
C++面试八股文:用过std::set/std::map吗?
来源:cnblogs  作者:二进制架构  时间:2023/6/28 8:50:05  对本文有异议

某日二师兄参加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有排序的要求。一般需要为类型实现<比较方法,以下代码无法通过编译:

  1. #include <iostream>
  2. #include <set>
  3. struct Foo
  4. {
  5. Foo(int v):val(v){}
  6. int val;
  7. };
  8. int main(int argc, char const *argv[])
  9. {
  10. std::set<Foo> iset;
  11. iset.insert(Foo(1024));
  12. iset.insert(Foo(42));
  13. for(auto it = iset.begin(); it != iset.end(); ++it)
  14. {
  15. std::cout << it->val << std::endl;
  16. }
  17. return 0;
  18. }

二师兄:此时需要为Foo类型实现bool operator<(const T&, const T&)函数,才能通过编译:

  1. 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函数用于比较两者的大小:

  1. struct Comp
  2. {
  3. bool operator()(const Foo& lhs, const Foo& rhs) const
  4. {
  5. return lhs.val > rhs.val;
  6. }
  7. };
  8. std::set<Foo,Comp> iset;

面试官:可以修改map中的key吗?

二师兄:不可以。因为map中的keyconst的。强制修改(取地址,const_cast转非const指针,解引用赋值)会造未知的错误。

面试官:当map中不存在某个key时,对map使用map[key]操作会有什么后果?

二师兄:会在map中增加一个键值对,键名为key,值是传入的value类型的默认值。

面试官:如果不希望删除重复的key,有什么办法?

二师兄:STL中提供了std::multisetstd::multimap两个容器,可以存入key相同的多个元素。

面试官:在std::multimap中如何通过key查找value

二师兄:multimap提供了equal_range方法,此方法返回一个pair,分别对应2个迭代器。通过循环迭代器来获取key对应的所有value

  1. #include <iostream>
  2. #include <map>
  3. int main() {
  4. std::multimap<int, std::string> mmap;
  5. mmap.insert(std::make_pair(1, "1"));
  6. mmap.insert(std::make_pair(2, "2"));
  7. mmap.insert(std::make_pair(3, "3"));
  8. mmap.insert(std::make_pair(1, "1"));
  9. auto range = mmap.equal_range(1);
  10. for (auto it = range.first; it != range.second; ++it) {
  11. std::cout << it->second << std::endl;
  12. }
  13. return 0;
  14. }

面试官:最后一个问题,你觉得单纯的查询而言,是vector快还是map快?

二师兄:当然是map快,因为vector的查询的时间复杂度是O(n),而map是O(logn)

面试官:好的,今天面试结束了,回去等通知吧。

让我们看看最后一个问题:

单纯的查询而言,是vector快还是map快?

这里二师兄的是标准答案,实际上当数据量特别大的时候,的确map是更好的选择。

但当数据量没那么大的时候(少于1000条记录),vector要比map查询速度快。原因我们在之前的面试文章中讲过,vector内存连续,缓存更友好。map底层是红黑树,内存并不连续。

当数据量小的时候,算法的优势没有抵消缓存的劣势,所以vector在数据量小的时候更胜一筹。

“纸上得来终觉浅,绝知此事要躬行”。小伙伴们,一起努力吧!

关注我,带你21天“精通”C++!(狗头)

原文链接:https://www.cnblogs.com/binarch/p/17510199.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号