关于c++:C面试八股文stdvector和stdlist如何选择

49次阅读

共计 2076 个字符,预计需要花费 6 分钟才能阅读完成。

某日二师兄加入 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 并没有记录。

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 指针指向的对象,而不须要挪动元素的地位,所以不会导致迭代器生效。

面试官:listvector 相比,有哪些劣势?什么状况下应用list,什么状况下应用vector

二师兄:次要有 2 点劣势:1.list在随机插入数据不会导致数据的搬移。2.list随机删除也不会导致数据搬移。所以在频繁的随机插入 / 删除的场景应用list,其余场景应用vector

面试官:你晓得 std::sort 和 list 成员函数 sort 有什么区别吗?

二师兄:std::sort是 STL 算法的一部分。它排序的容器须要有随机拜访迭代器,所以只能反对 vectordequelist成员函数 sort 用于 list 排序,工夫复杂度是O(N*logN)

面试官:forward_list理解吗?晓得如何实现的吗?

二师兄:std::forward_list是 C ++11 引入的新容器之一。它的底层是单向链表,引入它的次要目标是为了达到手写链表的性能。同时节俭了局部内存空间。(只有一根指针)

面试官:listpop_front/pop_back 的时候须要留神哪些问题?

二师兄:须要判断 listsize()不能为 0,如果list 为空,pop_front/pop_back会导致coredump

面试官:你晓得 list 的成员函数 insertforward_list的成员函数的 insert_after 有什么区别?

二师兄:两者都能够向特定地位增加元素。不同的是 insert 把元素插入到以后迭代器前,而 insert_after 把元素插入到以后迭代器后。

面试官:以下代码的输入是什么?

#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

面试官:遍历两个元素数目雷同的 vectorlist,哪个效率高?

二师兄:vectorlist 的遍历效率都是O(N),效率应该是一样的。

面试官:好的,回去等告诉吧。

让咱们看以下二师兄今日的体现:

以下代码的输入是什么?

这里实际上会输入 Segmentation fault,起因是因为当从listerase这个 node,这个nodeprevnext 指针被清空,而 ++it 是通过以后的 nodenext指针去找下一个node,解援用一个空指针,导致coredump

erase函数返回下一个无效迭代器,所以能够把 if(0 == *it % 2) li.erase(it) 批改为 if(0 == *it % 2) it = li.erase(it) 来解决这个问题。

遍历两个元素数目雷同的 vectorlist,哪个效率高?

这里二师兄答复的倒是没有故障,然而没有思考到缓存问题。实际上因为 vector 底层采纳数组存储数据,所以它的空间局部性更好,对缓存更敌对(Cache-friendly),所以遍历 vector 的效率要高于遍历list

最初多啰嗦一点,如果你没有特地的理由抉择其余容器,应用 vector 是最好的抉择。

二师兄今日的面试旅程完结了,感激各位小伙伴的关注和点赞。为了保障面试品质,当前不肯定能保障日更。文章中有任何技术性问题,请留言反馈,在此感激!

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

正文完
 0