设为首页 收藏本站
查看: 544|回复: 1

[经验分享] C++面试八股文:std::vector和std::list,如何选择?

[复制链接]
累计签到:34 天
连续签到:2 天
发表于 2025-1-17 11:44:35 | 显示全部楼层 |阅读模式
本帖最后由 jinchanchanwaji 于 2025-1-17 11:45 编辑

某日二师兄参加XXX科技公司的C++工程师开发岗位第24面:
面试官:list用过吗?
二师兄:嗯,用过。
面试官:请讲一下list的实现原理。
二师兄:std::list被称为双向链表,和C中手写双向链表本质上没有大的区别。list对象中有两个指针,一个指向上一个节点(node),一个指向下一个节点(node)。
二师兄:与手写双向链表不同的是,list中有一个base node,此node并不存储数据,从C++11开始,此node中包含一个size_t类型的成员变量,用来记录list的长度。
二师兄:所以说从C++11开始,size()的时间复杂度是O(1),在此之前是O(N)。
面试官:是每个node都包含一个记录长度的成员变量吗?
二师兄:不是,GCC中的实现只有在header node上记录了长度信息,其他node并没有记录。

[C#] 纯文本查看 复制代码
struct _List_node_base
{
    _List_node_base* _M_next;
    _List_node_base* _M_prev;
    ...
};
struct _List_node_header : public _List_node_base
{
#if _GLIBCXX_USE_CXX11_ABI
      std::size_t _M_size;
#endif
...
};
面试官:添加和删除元素会导致迭代器失效吗?
二师兄:并不会,因为在任意位置添加和删除元素只需要改变prev/next指针指向的对象,而不需要移动元素的位置,所以不会导致迭代器失效。
面试官:list和vector相比,有哪些优势?什么情况下使用list,什么情况下使用vector?
二师兄:主要有2点优势:1.list在随机插入数据不会导致数据的搬移。2.list随机删除也不会导致数据搬移。所以在频繁的随机插入/删除的场景使用list,其他场景使用vector。
面试官:你知道std::sort和list成员函数sort有什么区别吗?
二师兄:std::sort是STL算法的一部分。它排序的容器需要有随机访问迭代器,所以只能支持vector和deque。list成员函数sort用于list排序,时间复杂度是O(N*logN)。
面试官:forward_list了解吗?知道如何实现的吗?二师兄:std::forward_list是C++11引入的新容器之一。它的底层是单向链表,引入它的主要目的是为了达到手写链表的性能。同时节省了部分内存空间。(只有一根指针)
面试官:list在pop_front/pop_back的时候需要注意哪些问题?
二师兄:需要判断list的size()不能为0,如果list为空,pop_front/pop_back会导致coredump。
面试官:你知道list的成员函数insert和forward_list的成员函数的insert_after有什么区别?
二师兄:两者都可以向特定位置添加元素。不同的是insert把元素插入到当前迭代器前,而insert_after把元素插入到当前迭代器后。面试官:以下代码的输出是什么?

[C++] 纯文本查看 复制代码
#include <iostream>
#include <list>
int main(int argc, char const *argv[])
{
    std::list<int> li = {1,2,3,4,5,6};
    for(auto it = li.begin(); it!= li.end(); ++it)
    {
        if(0 == *it % 2) li.erase(it);
    }
    for(auto& i : li) std::cout << i << " ";
    std::cout << std::endl;
}
二师兄:应该是1 3 5。
面试官:遍历两个元素数目相同的vector和list,哪个效率高?
二师兄:vector和list的遍历效率都是O(N),效率应该是一样的。
面试官:好的,回去等通知吧。

让我们看以下二师兄今日的表现:
以下代码的输出是什么?

这里实际上会输出Segmentation fault,原因是因为当从list中erase这个node,这个node的prev和next指针被清空,而++it是通过当前的node的next指针去找下一个node,解引用一个空指针,导致coredump。
erase函数返回下一个有效迭代器,所以可以把if(0 == *it % 2) li.erase(it)修改为if(0 == *it % 2) it = li.erase(it)来解决这个问题。
遍历两个元素数目相同的vector和list,哪个效率高?

这里二师兄回答的倒是没有毛病,但是没有考虑到缓存问题。实际上因为vector底层采用数组存储数据,所以它的空间局部性更好,对缓存更友好(Cache-friendly),所以遍历vector的效率要高于遍历list。
最后多啰嗦一点,如果你没有特别的理由选择其他容器,使用vector是最好的选择。


运维网声明 1、欢迎大家加入本站运维交流群:群②:261659950 群⑤:202807635 群⑦870801961 群⑧679858003
2、本站所有主题由该帖子作者发表,该帖子作者与运维网享有帖子相关版权
3、所有作品的著作权均归原作者享有,请您和我们一样尊重他人的著作权等合法权益。如果您对作品感到满意,请购买正版
4、禁止制作、复制、发布和传播具有反动、淫秽、色情、暴力、凶杀等内容的信息,一经发现立即删除。若您因此触犯法律,一切后果自负,我们对此不承担任何责任
5、所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其内容的准确性、可靠性、正当性、安全性、合法性等负责,亦不承担任何法律责任
6、所有作品仅供您个人学习、研究或欣赏,不得用于商业或者其他用途,否则,一切后果均由您自己承担,我们对此不承担任何法律责任
7、如涉及侵犯版权等问题,请您及时通知我们,我们将立即采取措施予以解决
8、联系人Email:admin@iyunv.com 网址:www.yunweiku.com

所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其承担任何法律责任,如涉及侵犯版权等问题,请您及时通知我们,我们将立即处理,联系人Email:kefu@iyunv.com,QQ:1061981298 本贴地址:https://www.yunweiku.com/thread-1005672-1-1.html 上篇帖子: C++面试八股文:C++中,设计一个类要注意哪些东西? 下篇帖子: C++面试八股文:std::array如何实现编译器排序?
累计签到:34 天
连续签到:2 天
 楼主| 发表于 2025-1-17 11:46:17 | 显示全部楼层
<顺便吆喝一句,民族企业大厂,前后端测试捞人,全国各地都有岗位,感兴趣的来!→https://jsj.top/f/o38ijj>

运维网声明 1、欢迎大家加入本站运维交流群:群②:261659950 群⑤:202807635 群⑦870801961 群⑧679858003
2、本站所有主题由该帖子作者发表,该帖子作者与运维网享有帖子相关版权
3、所有作品的著作权均归原作者享有,请您和我们一样尊重他人的著作权等合法权益。如果您对作品感到满意,请购买正版
4、禁止制作、复制、发布和传播具有反动、淫秽、色情、暴力、凶杀等内容的信息,一经发现立即删除。若您因此触犯法律,一切后果自负,我们对此不承担任何责任
5、所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其内容的准确性、可靠性、正当性、安全性、合法性等负责,亦不承担任何法律责任
6、所有作品仅供您个人学习、研究或欣赏,不得用于商业或者其他用途,否则,一切后果均由您自己承担,我们对此不承担任何法律责任
7、如涉及侵犯版权等问题,请您及时通知我们,我们将立即采取措施予以解决
8、联系人Email:admin@iyunv.com 网址:www.yunweiku.com

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

扫码加入运维网微信交流群X

扫码加入运维网微信交流群

扫描二维码加入运维网微信交流群,最新一手资源尽在官方微信交流群!快快加入我们吧...

扫描微信二维码查看详情

客服E-mail:kefu@iyunv.com 客服QQ:1061981298


QQ群⑦:运维网交流群⑦ QQ群⑧:运维网交流群⑧ k8s群:运维网kubernetes交流群


提醒:禁止发布任何违反国家法律、法规的言论与图片等内容;本站内容均来自个人观点与网络等信息,非本站认同之观点.


本站大部分资源是网友从网上搜集分享而来,其版权均归原作者及其网站所有,我们尊重他人的合法权益,如有内容侵犯您的合法权益,请及时与我们联系进行核实删除!



合作伙伴: 青云cloud

快速回复 返回顶部 返回列表